# Prolog: 3x3 Square Picture-Puzzle Solution

2011-06-19 Reilly Beacom

I came accross a puzzle on a family weekend and decided it would be a fun challenge to ask my computer to solve it.

The aim of the puzzle is to find a 3x3 grid arrangement of the 9 tiles where the animals' heads and tails match between each adjacent tile.

This was also an exercise to refresh my memory of Prolog from my Comp Sci degree.

Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.

Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations.

## Prolog Solution

### Tiles

My first step was to describe the tiles to Prolog.

I randomly arranged the tiles in a list and give each one an identification number (writing on the back in pencil).

(The order of the list does not matter and the solution to the puzzle was not yet known.)

The format is: tile(number, top, right, bottom, left).

```
tile(1, cheetah_tail, tiger_tail, lion_head, tiger_head).
tile(2, lion_tail, lion_head, tiger_tail, cheetah_head).
tile(3, tiger_tail, lion_head, panther_head, tiger_tail).
tile(4, panther_tail, cheetah_head, panther_tail, lion_tail).
tile(5, tiger_head, tiger_head, cheetah_head, lion_tail).
tile(6, panther_tail, panther_head, cheetah_tail, tiger_head).
tile(7, panther_head, cheetah_tail, cheetah_head, lion_tail).
tile(8, panther_tail, lion_head, panther_head, cheetah_tail).
tile(9, cheetah_head, tiger_head, panther_head, lion_tail).
```

### Matching

A computer and Prolog have no understanding of animals, lions, heads or tails. So I needed to state (as facts) the valid matches between heads and tails.

You can read the fact
`match(lion_head, lion_tail).`

as "a match is between lion-head and lion-tail" or "lion-head and lion-tail is a match".

I listed all the correct matches for the puzzle.

```
match(lion_head, lion_tail).
match(lion_tail, lion_head).
match(cheetah_head, cheetah_tail).
match(cheetah_tail, cheetah_head).
match(panther_head, panther_tail).
match(panther_tail, panther_head).
match(tiger_head, tiger_tail).
match(tiger_tail, tiger_head).
```

### The Game Grid

To desctibe the 3x3 grid to Prolog, I identified each
*position*
(not tile) in the grid with the letters A-to-I.

Each tile in each position can also be rotated (relative to my tile descriptions at the start): up, down, left, and right.

In my code below, the variable-set
`[A, B, C, D, E, F, G, H, I]`

represents every possible permutation of the 9 tiles. (The
`permutation`

clause is provided by SWI-Prolog.)

The variable-set
`[Ar, Br, Cr, Dr, Er, Fr, Gr, Hr, Ir]`

("r" for rotation) represents every possible rotation of every tile in its row or column.

I reduced the grid into a description of rows and columns.

```
grid([A, B, C, D, E, F, G, H, I], [Ar, Br, Cr, Dr, Er, Fr, Gr, Hr, Ir]) :-
permutation([1 ,2 ,3 ,4 ,5 ,6, 7, 8, 9], [A, B, C, D, E, F, G, H, I]),
row(A, B, C, Ar, Br, Cr),
row(D, E, F, Dr, Er, Fr),
row(G, H, I, Gr, Hr, Ir),
col(A, D, G, Ar, Dr, Gr),
col(B, E, H, Br, Er, Hr),
col(C, F, I, Cr, Fr, Ir).
```

### Grid Row

The solution to the puzzle has rows (and columns) where the animals' heads and tails match (A-B and B-C as pictured).

I reduced the row into a match between tiles A-B and tiles B-C. Since match-left-to-right is logically identical for both, the B-C match reuses the same rule.

```
row(A, B, C, Ar, Br, Cr) :-
match_left_to_right(A, B, Ar, Br),
match_left_to_right(B, C, Br, Cr).
```

My
`match_left_to_right`

rule states that there is a match if the right-edge (AB) of the left rotated-tile (A) matches the left-edge (BA) of the right rotated-tile (B).

(Remember, I definied the
`match`

facts at the start. I introduced
`rotated_tile`

here but define it later.)

```
match_left_to_right(A, B, Ar, Br) :-
rotated_tile(A, _, AB, _, _, Ar),
rotated_tile(B, _, _, _, BA, Br),
match(AB, BA).
```

### Grid Column

Columns are the same as rows but rotated from horizonal to vertical. (For simplicity, the code-structure of rows is repeated.)

```
col(A, B, C, Ar, Br, Cr) :-
match_above_to_below(A, B, Ar, Br),
match_above_to_below(B, C, Br, Cr).
match_above_to_below(A, B, Ar, Br) :-
rotated_tile(A, _, _, AB, _, Ar),
rotated_tile(B, BA, _, _, _, Br),
match(AB, BA).
```

### Tile Orientation

Finally, I needed to tell Prolog that any given tile,
`Tile`

,
can be rotated to any one of 4 orientations:
,
`up`

,
`right`

,
`down`

and
`left`

. (See the last param in
`rotated_tile`

.)

```
rotated_tile(Tile, Top, Right, Bottom, Left, up) :- tile(Tile, Top, Right, Bottom, Left).
rotated_tile(Tile, Top, Right, Bottom, Left, right) :- tile(Tile, Right, Bottom, Left, Top).
rotated_tile(Tile, Top, Right, Bottom, Left, down) :- tile(Tile, Bottom, Left, Top, Right).
rotated_tile(Tile, Top, Right, Bottom, Left, left) :- tile(Tile, Left, Top, Right, Bottom).
```

### Result

Having described the facts and rules of the puzzle to Prolog, I simply asked for the solution. (It took my computer less than 3 seconds.)

```
?- grid(Tiles, Rotations).
Tiles = [2, 1, 6, 8, 9, 7, 5, 3, 4],
Rotations = [left, up, up, right, right, down, right, up, up] ;
```

So, reading the output left-to-right (or A-to-I), the tile in grid position A is number 2, rotated left, the tile in grid position B is number 1, rotated up, and so on...

(Below is a photo of the output, arranged in real life.)

### All the code

```
% tile(number, top, right, bottom, left).
tile(1, cheetah_tail, tiger_tail, lion_head, tiger_head).
tile(2, lion_tail, lion_head, tiger_tail, cheetah_head).
tile(3, tiger_tail, lion_head, panther_head, tiger_tail).
tile(4, panther_tail, cheetah_head, panther_tail, lion_tail).
tile(5, tiger_head, tiger_head, cheetah_head, lion_tail).
tile(6, panther_tail, panther_head, cheetah_tail, tiger_head).
tile(7, panther_head, cheetah_tail, cheetah_head, lion_tail).
tile(8, panther_tail, lion_head, panther_head, cheetah_tail).
tile(9, cheetah_head, tiger_head, panther_head, lion_tail).
match(cheetah_head, cheetah_tail).
match(cheetah_tail, cheetah_head).
match(lion_head, lion_tail).
match(lion_tail, lion_head).
match(panther_head, panther_tail).
match(panther_tail, panther_head).
match(tiger_head, tiger_tail).
match(tiger_tail, tiger_head).
% A B C
% D E F
% G H I
% Ar Br Cr
% Dr Er Fr
% Gr Hr Ir
grid([A, B, C, D, E, F, G, H, I], [Ar, Br, Cr, Dr, Er, Fr, Gr, Hr, Ir]) :-
permutation([1 ,2 ,3 ,4 ,5 ,6, 7, 8, 9], [A, B, C, D, E, F, G, H, I]),
row(A, B, C, Ar, Br, Cr),
row(D, E, F, Dr, Er, Fr),
row(G, H, I, Gr, Hr, Ir),
col(A, D, G, Ar, Dr, Gr),
col(B, E, H, Br, Er, Hr),
col(C, F, I, Cr, Fr, Ir).
row(A, B, C, Ar, Br, Cr) :-
match_left_to_right(A, B, Ar, Br),
match_left_to_right(B, C, Br, Cr).
match_left_to_right(A, B, Ar, Br) :-
rotated_tile(A, _, AB, _, _, Ar),
rotated_tile(B, _, _, _, BA, Br),
match(AB, BA).
col(A, B, C, Ar, Br, Cr) :-
match_above_to_below(A, B, Ar, Br),
match_above_to_below(B, C, Br, Cr).
match_above_to_below(A, B, Ar, Br) :-
rotated_tile(A, _, _, AB, _, Ar),
rotated_tile(B, BA, _, _, _, Br),
match(AB, BA).
rotated_tile(Tile, Top, Right, Bottom, Left, up) :- tile(Tile, Top, Right, Bottom, Left).
rotated_tile(Tile, Top, Right, Bottom, Left, right) :- tile(Tile, Right, Bottom, Left, Top).
rotated_tile(Tile, Top, Right, Bottom, Left, down) :- tile(Tile, Bottom, Left, Top, Right).
rotated_tile(Tile, Top, Right, Bottom, Left, left) :- tile(Tile, Left, Top, Right, Bottom).
```

## Responses

Last update: 2012-03-18