In 1976, my father returning from Switzerland, handed me the following puzzle:
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.
Force 5 manual starting moves as:
After running the rest of the algorithm:
Unstacking for the rest of moves: