The 24-tile Puzzle

The 24 magnetic tile puzzle was bought by the author's father in 1976^[1]. The object of the puzzle is variable. Two objectives are shown in the instructions to the left. The simplest objective is to place all the tiles so that their touching colors are the same.

Analysis

We have 3 colors, black, red and yellow. This suggests an encoding of each tile as the list [a,b,c,d], with a the color of the bottom of the tile, b the color of the right side of the tile, c the color of the upper side of the tile and d the color of the left side of the puzzle. For example, the tile at the bottom left of the image (tile at square (1,1)) would be encoded as [1,3,2,3].

This encoding induces an equivalence relation rot(c,r), where c and r are the column and row resp., which rotates a given tile around the square center. Under rot(c,r) the puzzle breaks into 3 equivalence classes: The first class consists of the all black, all red and all yellow tiles (3, located at (2,2), (4,5) and (1,6)), which are invariant under any rot(c,r) with 1 value. The second class consists of tiles symmetric around the vertical and horizontal (3, located at (4,1), (1,4) and (4,3)), which are invariant under rot(c,r)=180° with 2 values. The third class consists of the rest of the tiles, which are invariant only under rot(c,r)=360° with 4 values.

Select 3 positions out of 24 for the first class, 3 out of 21 for the second class and the rest for the last class, giving an enumeration of all possible puzzle states as:

We can use Maple to build a graphical representation of the puzzle:

Unsolved puzzle representation using Maple

If the colors are represented as a=1=black, b=2=red, c=3=yellow, then each tile can be uniquely identified by its base-3 value, for example as: [a,b,c,d]=(a-1)(b-1)(c-1)(d-1)₃=v, and rot(c,r) gives a total of: 18*4+3*2+3*1=81=3⁴ values, so we can encode the puzzle uniquely using a string of length 24 in base 81, as:

Unique puzzle state encoding

For example, using this encoding,

> enc(p);
117782535294698141274684082857347227980565352
> convert(enc(p),base, 81);
[23,45,43,70,58,80,68,0,24,34,51,77,6,37,26,65,16,63,10,19,60,36,40,1]

which can easily be seen to be a unique representation of the puzzle's starting position as shown on the first picture, starting from the bottom left tile, (1,1).

Solving the Puzzle

One set of moves found by the author, gives:

Solved puzzle representation using Maple

Encoding the moves as the list [rot,c1,r1,c2,r2] and dumping the stack at the end of the worksheet^[2], reveals all the moves in reverse:

If we decide to solve it using Maple, it will be a little tricky: We have to build a generator of all available moves, then encode each new move using the above board encoding and keep looking for moves which do not give already gotten encodings.

The equivalence classes found above help with a brute force solution because they filter out certain rotations in the move generator^[3], so we can use brute-force on the enumeration with backtracking, until a solution is found.

Here's the result after running Maple for 1567.8 secs = 26.31 mins on the author's mobile Athlon @1.8 GHz:

Solved puzzle representation using brute-force @depth=8061

Dumping the stack after the search, gives:

The reader can tweak the Maple worksheet algorithm (by changing the variable border:=true;) to search for solutions which satisfy the two stricter conditions described on the left side of the puzzle in the first picture.

Here's the solution for objective #2, found by Maple with a little help, after making the first 10 moves manually:

Solved puzzle representation using brute-force @depth=1516

Dumping the stack after the search, gives:

The combinatorial enumeration above, enumerates all configurations. When a border is observed, as above, the resultant shape is a plane-tiling. Can you enumerate all configurations for the simplest solution (touching faces same)? Can you enumerate all plane-tilings (touching faces plus border)? Are there good chances Maple can find such a solution by brute-force? Can you see what the second condition will give?

Notes

1. If you don't have the puzzle, it is fairly easy to construct using any geometry program. Here's a EucliDraw dynamic document with the specified colors, which can be put to specified size, printed on paper and then cut using scissors.
2. Download a Maple 9 classic worksheet, which solves the puzzle, here.
3. In is unnecessary for example to look for any rotations of the tiles in the first class, while for the second class it is sufficient to only consider rotations by 90°.

Back to Mathematics