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.
```