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.

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:

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.

See also

• What Is an Integer Linear Program
• Thank You MSV Incognito
• Trip to Poland