Next: Elementary first order formulations Up: CREATIVE SOLUTIONS TO Previous: The mutilated checkerboard

# Pinning down the ideas, English first

Actually solving a problem involves both a creative part and a routine part. It is sometimes possible to separate the creative part from the routine part. Consider the Minsky solution. We can tell a person,

Starting with the diagonal next to an excluded square, compute how many dominoes project from each diagonal to the next diagonal.

This proved to be adequate for a sample of one veterinarian. This is a kind of program, but it doesn't need a termination condition, because the termination is apparent to the problem solver. It is harder to tell whether it is close to the form in which the solution was discovered, although it looks close.

When we consider expressing the creative idea to a computer program, it would be most convenient to tell it a fact or to tell it an executable program. I know of no-one who has tried to make computer programs that can accept a fragment of a program as above as the non-routine part of the solution to the problem.

Here's a try at expressing concisely the idea of the Winograd solution. It seems to be longer and to involve more than one idea.

Starting with the top row, compute the parity of the number of dominoes projecting down out of each row. Consider the parity of the sum. Repeat going horizontally starting with the left column. Compute the parity of the total number of dominoes compared to the sum of the two parities.

According to a 1999 personal communication, the idea can be expressed more concisely. Winograd got the idea as a result of seeing a movie about the Socratic method in mathematics education. A student said something like, ``An odd number of dominoes project down from the top row and an odd number down from the second row to the third ...''. At this point the teacher interrupted the student and led him by the Socratic method to the standard solution. Winograd wondered whether the student's original idea could be pushed through, and this led to the solution.

Looking at it this way, the creative idea seems to be

Note that an odd number of dominoes project from the top row to the second and continue from there.

Presumably not everyone would be able to push the argument through, because at some point you have to notice that although you get no contradiction from determining that there are an odd number of vertical dominoes, you also get an odd number of horizontal dominoes and an even number of dominoes altogether. Thus the notion of creative solution seems to depend on the ability available to push an idea through.

Winograd idea can also be pushed through when two squares of the same color are removed any where on the board. If one starts at the top and computes the successive parities, there is a jog in parity when an excluded square is encountered. Taking into account the jog one gets an answer as to the parity of the number of vertical dominoes. For some pairs of excluded squares, the parity turns out to be even. However, the parity turns out, it will be the same going horizontally.

The Winograd idea can then be expressed more abstractly.

Successively compute the parity of the number of vertical dominoes projecting from each row to the next.

The Stefanuk solution seems to involve two ideas. The first is to label the squares starting from an arbitary square. The second is like the Minsky solution, namely

Starting with n=1, compute how many dominoes project from the set of squares labelled n to the squares labelled n+1.

In this section I have striven for concise expressions of the creative idea. The reason is to establish that there is one idea in each of the cases. Obviously it will be easier to make computers come up with creative solutions if the idea of the solution is just one thing--whatever kind of thing that may be.

Next: Elementary first order formulations Up: CREATIVE SOLUTIONS TO Previous: The mutilated checkerboard

John McCarthy
Mon Mar 29 15:20:19 PST 1999