Scheme Boston: Notes from December, 2002 meeting

Notes by Ed Kademan <kademan@phz.com>

The fourth meeting of Scheme Boston took place at Northeastern University Tuesday night December 17, 2002. Approximately 10 people showed up to hear Ken Williams give a talk on using Scheme to find the solutions to the little blue cube puzzle.

The little blue cube puzzle consists of six flat jigsaw-like pieces with crenellations along the sides that fit together to form a cube. A complete description of the puzzle and of its solution---and of that of several others like it---is at www.snafooz.com.

The particular puzzle Ken had was the level-4 version.

Also, the particular tool Ken used to solve the puzzle was the amb Teach Yourself Scheme in Fixnum Days.

The amb macro simulates a nondeterministic search strategy by implementing a tree of possibilities using Scheme continuations and explicit backtracking. It takes several arguments and pseudo-ambiguously chooses to evaluate whichever one does the right thing. For example, an initial expression of the form

(amb)

signifies failure. An initial expression of the form

(amb exp1)

signifies failure only if the evaluation of exp1 does. Further, an expression of the form

(amb exp1 exp2)

signifies a failure only if both exp1 and exp2 do. If only one of them fails amb will choose to evaluate the successful one. If they both succeed amb will be indifferent as to which one to evaluate and will pick one in a way that the programmer can usefully think of as random. The actual mechanism is not random of course. In all cases the macro first tries to evaluate exp1, and if that fails turns to exp2. However amb differs from or in that subsequent calculations can cause this current amb expression to reconsider its choice. If exp1 succeeds locally but the program as a whole fails as a result, control will return to the choice point and amb will try exp2 instead. The programmer can imagine that amb has perfect foreknowledge and only ever follows those paths that lead to successful outcomes.

In principle nondeterministic programming requires little more than finding a suitable way of encoding the features of the problem and then asserting those characteristics that a solution must satisfy. This is the first way Ken tried to solve the cube puzzle. Each puzzle piece has its own unique contour and so is identifiable, and each piece can occupy a particular face of the cube in 8 potential orientations. (There are 4 symmetric rotations as a square---upright, lying on the left side, lying on the right side, and upside down---times 2 reflections---facing out or facing in.) Thus the total number of ways one might use a particular piece is 48---6 faces times 8 orientations. Imagine initially that any piece can occupy any face in any way, even if that piece already occupies some other face already. This makes the total number of potential solutions (expt 48 6) or 12,230,590,464. To find the true solutions write a program that entertains the possibility that there might be this many but that then throws out all of those that are nonsensical.

So Ken's initial program had amb choosing orientations and pieces for each face followed by assertions that the pieces all be distinct and actually fit together. But this program ran for 20 hours without finding a solution. So he wrote another version that gave amb some guidance. The program put a cube together one piece at a time by ambiguously choosing a piece and orientation for the front, then ambiguously choosing another piece and orientation for an adjacent side under the constraint that it fit the first one, then choosing yet another piece and orientation to form a corner under the constraint that this new piece fit the previous two, and so on. This program ran in a few seconds and found all the solutions (16 as it happens).

Ken closed by pointing out that it would be possible to extend this educational exercise in several different ways. One could try using composite pieces instead of single pieces one at a time, and could consider the other more elaborate puzzles on the snafooz web site. He also mentioned that this was one of his first programming efforts in Scheme---he had been working on it practically right up until the time of the presentation---and felt that the style could use some improving. In the discussion participants pointed out that the literature describes more general and powerful nondeterministic tools than the version of amb Ken used and that for this particular type of problem Prolog---which is optimized for pattern matching and unification---would probably be a more natural fit. (And in fact it would probably lead to a program very much like the one Ken wrote.)

The Scheme-Boston meetings are moving to Monday night so the next one will be January 20th. The guys from Northeastern who were in attendance volunteered to get someone to talk about interfacing Scheme with PostgreSQL.