The puzzle

My roomate bought me a kid puzzle, from the second hand shop.
The puzzle consists in putting the puzzle pieces in a 3x3 grid, such that all the animals on the edges match.
It might look like an easy puzzle, but once, trying to solve the puzzle with my friends, we took a good 30 min to try to solve the puzzle. I already gave up on the puzzle after 5 min of trial, after I realized there are \(9! \cdot 4^9\) (95126814720) possible formation of the puzzle.
So I decided to code a program that would solve the problem.
I decided to program a solver of the puzzle using Integer Programming.

Solving the puzzle with Integer Programming

Values

There are 8 possible animal part on the edges of the tiles, them being:

Jaguar front → \(JF\)
Jaguar back → \(JB\)
Panther front → \(PF\)
Panther back → \(PB\)
Tiger front → \(TF\)
Tiger back → \(TB\)
Lion front → \(LF\)
Lion back → \(LB\)

I gave each animal part a representative values such that matching values add up to \(0\) but non matching values do not add up to \(0\).
e.g.
\(JF + JB = 0 \)
\(JF + TB \neq 0 \)

In my implementation, I used the following values.

	Tiger	Lion	Panther	Jaguar
Front	1	2	3	4
Back	-1	-2	-3	-4

Tile

All possible tiles

   JB        JF        LF        TF        TB        PF        LB        PB        PB                                                        
TF  0 TB  JB  1 LB  LB  2 TB  TF  3 JF  TB  4 LF  TF  5 LB  PB  6 PB  JB  7 LF  TF  8 PF                                                      
   LF        PF        JF        LB        PF        JF        JF        PF        JB

The variable \(tile_{i,rot}\)

The variable \( tile_{i,rot} \) is a variable that stores the \(i\)th tile with a rotation of \(rot \cdot 90° \) degree clockwise.
e.g.
\(left(tile_{0,0}) = TF = 1\)
\(top(tile_{1,1}) = JB = -4\)
It is obvious that the following properties hold.
\(left(tile_{i,rot}) = top(tile_{i,rot + 1})\)
\(top(tile_{i,rot}) = right(tile_{i,rot + 1})\)
\(right(tile_{i,rot}) = bottom(tile_{i,rot + 1})\)
\(bottom(tile_{i,rot}) = left(tile_{i,rot + 1})\)

The Variables of the ILP

\(t_{i,rot,pos}\) are the integer program variables.
\(i\) stands for the \(i\)th tile, \(rot\) stands for the \(rot \cdot 90° \) degree clockwise rotation that the tile will be configured in, and \(pos\) stands for the position of the tile in a 3x3 configuration, if each position is indexed the following way:

0	1	2
3	4	5
6	7	8

The Constraints of the ILP

For each tile, one state only must exist

\(\forall{i}{\sum_{rot}{\sum_{pos}{t_{i,rot,pos}}}} = 1\)

For each slot, one tile only must exist

\(\forall{pos}{\sum_{i}{\sum_{rot}{t_{i,rot,pos}}}} = 1\)

Side matching

\( \sum_{i}{\sum_{rot}{right(tile_{i,rot}) \cdot t_{i,rot,0}}} + \sum_{i}{\sum_{rot}{left(tile_{i,rot}) \cdot t_{i,rot,1}}} = 0\)

\( \sum_{i}{\sum_{rot}{right(tile_{i,rot}) \cdot t_{i,rot,1}}} + \sum_{i}{\sum_{rot}{left(tile_{i,rot}) \cdot t_{i,rot,2}}} = 0\)

\( \sum_{i}{\sum_{rot}{right(tile_{i,rot}) \cdot t_{i,rot,3}}} + \sum_{i}{\sum_{rot}{left(tile_{i,rot}) \cdot t_{i,rot,4}}} = 0\)

\( \sum_{i}{\sum_{rot}{right(tile_{i,rot}) \cdot t_{i,rot,4}}} + \sum_{i}{\sum_{rot}{left(tile_{i,rot}) \cdot t_{i,rot,5}}} = 0\)

\( \sum_{i}{\sum_{rot}{right(tile_{i,rot}) \cdot t_{i,rot,6}}} + \sum_{i}{\sum_{rot}{left(tile_{i,rot}) \cdot t_{i,rot,7}}} = 0\)

\( \sum_{i}{\sum_{rot}{right(tile_{i,rot}) \cdot t_{i,rot,7}}} + \sum_{i}{\sum_{rot}{left(tile_{i,rot}) \cdot t_{i,rot,8}}} = 0\)

Top and bottom matching

\( \sum_{i}{\sum_{rot}{bottom(tile_{i,rot}) \cdot t_{i,rot,0}}} + \sum_{i}{\sum_{rot}{top(tile_{i,rot}) \cdot t_{i,rot,3}}} = 0\)

\( \sum_{i}{\sum_{rot}{bottom(tile_{i,rot}) \cdot t_{i,rot,1}}} + \sum_{i}{\sum_{rot}{top(tile_{i,rot}) \cdot t_{i,rot,4}}} = 0\)

\( \sum_{i}{\sum_{rot}{bottom(tile_{i,rot}) \cdot t_{i,rot,2}}} + \sum_{i}{\sum_{rot}{top(tile_{i,rot}) \cdot t_{i,rot,5}}} = 0\)

\( \sum_{i}{\sum_{rot}{bottom(tile_{i,rot}) \cdot t_{i,rot,3}}} + \sum_{i}{\sum_{rot}{top(tile_{i,rot}) \cdot t_{i,rot,6}}} = 0\)

\( \sum_{i}{\sum_{rot}{bottom(tile_{i,rot}) \cdot t_{i,rot,4}}} + \sum_{i}{\sum_{rot}{top(tile_{i,rot}) \cdot t_{i,rot,7}}} = 0\)

\( \sum_{i}{\sum_{rot}{bottom(tile_{i,rot}) \cdot t_{i,rot,5}}} + \sum_{i}{\sum_{rot}{top(tile_{i,rot}) \cdot t_{i,rot,8}}} = 0\)

The program and the solution

The program can be found here.
The output of the program is:

   JF       PF       LB   
TF  3 LB LF  7 JB JF  2 LF
   TF       PB       TB   
   TB       PF       TF   
PF  4 TB TF  5 LB LF  0 JB
   LF       JF       TB   
   LB       JB       TF   
PB  6 PB PF  1 JF JB  8 PB
   JF       LB       PF

Which translates to the following configuration.

Fun Fact

You can still play the game if you lose any piece with a 2x4 formation.

All the possible 8 pieces out of the 9 pieces have a solution with a 2x4 formation.

Solve a Kid Puzzle With an Over Engineered Solution