In 1976, my father returning from Switzerland,
handed me the following puzzle:
A 24, 3-color tiles puzzle totally scrambled
The requirements for its solution are typed on a single leaflet included in the
puzzle:
Problem #1:
Each pair of touching edges must be of the same color, and
The border of the rectangle, all the way round, must be of the same
color[*].
Problem #2:
Each pair of touching edges must be of the same color, and
The border of the rectangle must be divided in any arrangement between two
colors[**].
Where:
[*] Any color may be chosen for the border.
[**] Any two colors may be chosen for the
border.
I was 12 at the time, so I rejected it immediately as hard to solve. A somewhat
premature and uneducated decision that left it sitting and collecting dust on my
bookshelf until 2010, when I started wondering how to implement a brute force algorithm
that would solve it, under the auspices of the relatively advanced and compact syntax
used by Maple. This puzzle is a variation[5] of the colored tiles domino problem using
3-color Wang tiles. The resulting code[1] manages to find a solution in some cases, but
gets stuck on others depending on some initial helping push and its surrounding
configuration. Turns out it's an undecidable problem[2], so the code in the link needs a little startup
kick to pick up.
A quick Maple 9 implementation
To avoid ambiguity with moves, we reqire a duplicate coordinate grid p to the left,
identical to the one on the right q, so we can describe any possible move as moving
from board p to q. Any possible move then, can be described as (n,p[r1,c1],q[r2,c2]),
with (c,r)= (column, row) source p board and destination q board and n∈{1,2,3,4}
describing a clockwise (or counterclockwise) rotation by angle θ=n*π/2 modulo
2*π around the center of each tile.
The rest of the algorithm is pretty forward. We first choose an encoding for the
board based on the three colors and angles, so we can have something to compare with
after we make or backtrack a move. Then one simply generates a sequence of moves and
picks the one that has the highest potential in terms of matching colors through an
evaluation function, by recursive descent[3]. The latter neccesitates using a stack of
course.
A particular "soft shuffle" initial configuration
Above initial configuration with Maple
Force 5 manual starting moves as:
(1,4,4,4,6)
(1,2,3,1,6)
(0,4,3,1,2)
(1,4,2,2,2)
(1,4,1,3,2)
After the 5 manual moves above, to steer towards a possible solution towards a black
border
After running the rest of the algorithm:
"Solution found at depth: 1516, in time: 91.641 secs."
Unstacking for the rest of moves:
(3, 3, 5, 4, 5)
(2, 2, 5, 4, 4)
(2, 3, 6, 4, 3)
(0, 3, 4, 3, 6)
(0, 1, 6, 3, 5)
(2, 2, 1, 3, 4)
(0, 4, 5, 3, 3)
(2, 3, 3, 2, 6)
(3, 2, 6, 2, 5)
(2, 1, 5, 1, 5)
(0, 1, 4, 2, 4)
(2, 2, 4, 1, 4)
(0, 1, 3, 2, 3)
(1, 1, 1, 1, 3)
(0, 4, 6, 4, 1)
(2, 3, 2, 3, 1)
(3, 1, 2, 2, 1)
(0, 3, 1, 1, 1)
(0, 2, 2, 4, 2)
(1, 4, 1, 3, 2)
(1, 4, 2, 2, 2)
(0, 4, 3, 1, 2)
(1, 2, 3, 1, 6)
(1, 4, 4, 4, 6)
Solution for Problem #1 with black border color choice
Notes
Download a Maple 18 classic worksheet to test some of the above code, here.
Undecidable in this context means a machine will not halt if it tries to find an
algorithm that solves this puzzle for ANY possible startup constraint. Hence the
conundrum. Haven't tested many other cases but in general this means that the
algorithm above may either fail to find a solution or may run forever. Try it, by
changing the initial manual moves.
Similar to the standard implementation for most chess engines that use a
generator and a position evaluation function that filters in only the best move. For
details, see here.
For a different tile shape (and color) puzzle, consult this document.
An extension of the 11 tiles, 4 colors domino problem, which is impossible to solve with a border, since it can only tile the plane aperiodically. The puzzle on this page is solvable with a single color border and any such solution obviously gives a periodic plane tiling. Also see this Quora answer.
