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.

Photo of the puzzle solution.

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

Photo of 9 tiles in a row with annotated numbers.

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.

Photo of two tiles with matching lion-head and lion-tail

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.

Photo of one random, incorrect permutation of the nine tiles placed in a grid then annotated with the letters A-to-I and arrows for rows and columns.

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

Photo of grid and rotating tile, annotated with symbols Ar-to-Ir..

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

Photo of a row with matching animals and annotated tiles and edges.

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

Photo of a column with matching animals and annotated tiles and edges.

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

Photo of the puzzle solution annotated with tile numbers and rotations.

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

Tom's solution using SQL