# 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.