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
The
signifies failure. An initial expression of the form
signifies failure only if the evaluation of
signifies a failure only if both
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
So Ken's initial program had
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
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.
amb
Teach Yourself Scheme in Fixnum Days.
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)
(amb exp1)
exp1 does.
Further, an expression of the form
(amb exp1 exp2)
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.
(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.
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).
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.)