The 24 Colored Tile Puzzle

In 1976, my father returning from Switzerland, handed me the following puzzle:

wang puzzle scrambled
A 24, 3-color tiles puzzle totally scrambled

The requirements for its solution are typed on a single leaflet included in the puzzle:

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.


wang puzzle weak shuffle
A particular "soft shuffle" initial configuration
wang puzzle weak shuffle maple
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)
wang puzzle weak shuffle maple
After the 5 manual moves above, to steer towards a possible solution towards a black border

After running the rest of the algorithm:

solved by maple
"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)
wang puzzle solved
Solution for Problem #1 with black border color choice
Notes
  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.