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:
  1. Each pair of touching edges must be of the same color, and
  2. The border of the rectangle, all the way round, must be of the same color[*].
• Problem #2:
  1. Each pair of touching edges must be of the same color, and
  2. 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 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. (1,4,4,4,6)
2. (1,2,3,1,6)
3. (0,4,3,1,2)
4. (1,4,2,2,2)
5. (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:

1. (3, 3, 5, 4, 5)
2. (2, 2, 5, 4, 4)
3. (2, 3, 6, 4, 3)
4. (0, 3, 4, 3, 6)
5. (0, 1, 6, 3, 5)
6. (2, 2, 1, 3, 4)
7. (0, 4, 5, 3, 3)
8. (2, 3, 3, 2, 6)
9. (3, 2, 6, 2, 5)
10. (2, 1, 5, 1, 5)
11. (0, 1, 4, 2, 4)
12. (2, 2, 4, 1, 4)
13. (0, 1, 3, 2, 3)
14. (1, 1, 1, 1, 3)
15. (0, 4, 6, 4, 1)
16. (2, 3, 2, 3, 1)
17. (3, 1, 2, 2, 1)
18. (0, 3, 1, 1, 1)
19. (0, 2, 2, 4, 2)
20. (1, 4, 1, 3, 2)
21. (1, 4, 2, 2, 2)
22. (0, 4, 3, 1, 2)
23. (1, 2, 3, 1, 6)
24. (1, 4, 4, 4, 6)

Solution for Problem #1 with black border color choice

1. Download a Maple 18 classic worksheet to test some of the above code, here.
2. 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.
3. 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.
4. For a different tile shape (and color) puzzle, consult this document.