Update: A second attempt at a write up.
After Reilly solved a 3x3 square picture puzzle using Prolog I made a flippant remark that it would be interesting to solve using SQL and well, here goes...
First, create a table and populate it with the pieces:
# table of all pieces in all possible rotations
CREATE TABLE rotated_pieces (
piece_id INTEGER, # unique piece id
rotation INTEGER, # 0 - top, 1 - left, 2 - bottom, 3 - right
top CHAR(10), # animal at top edge
top_head CHAR(10), # head or tail at top edge
`right` CHAR(10),
right_head CHAR(10),
bottom CHAR(10),
bottom_head CHAR(10),
`left` CHAR(10),
left_head CHAR(10));
# unrotated pieces (top)
INSERT INTO rotated_pieces
(piece_id, rotation,
top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head)
VALUES (1, 0, 'cheetah', 'tail', 'tiger', 'tail', 'lion', 'head', 'tiger', 'head'),
(2, 0, 'lion', 'tail', 'lion', 'head', 'tiger', 'tail', 'cheetah', 'head'),
(3, 0, 'tiger', 'tail', 'lion', 'head', 'panther', 'head', 'tiger', 'tail'),
(4, 0, 'panther', 'tail', 'cheetah', 'head', 'panther', 'tail', 'lion', 'tail'),
(5, 0, 'tiger', 'head', 'tiger', 'head', 'cheetah', 'head', 'lion', 'tail'),
(6, 0, 'panther', 'tail', 'panther', 'head', 'cheetah', 'tail', 'tiger', 'head'),
(7, 0, 'panther', 'head', 'cheetah', 'tail', 'cheetah', 'head', 'lion', 'tail'),
(8, 0, 'panther', 'tail', 'lion', 'head', 'panther', 'head', 'cheetah', 'tail'),
(9, 0, 'cheetah', 'head', 'tiger', 'head', 'panther', 'head', 'lion', 'tail');
Then, rotate each of those pieces so we have all 36 variations:
# rotate (top --> left)
INSERT INTO rotated_pieces (piece_id, rotation, top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head)
SELECT piece_id, rotation+1,
`right` AS top, right_head AS top_head,
bottom AS `right`, bottom_head AS right_head,
`left` AS bottom, left_head AS bottom_head,
top AS `left`, top_head AS left_head
FROM rotated_pieces;
# rotate (top --> bottom, left --> right)
INSERT INTO rotated_pieces (piece_id, rotation, top, top_head, `right`, right_head, bottom, bottom_head, `left`, left_head)
SELECT piece_id, rotation+2,
bottom AS top, bottom_head AS top_head,
`left` AS `right`, left_head AS right_head,
top AS bottom, top_head AS bottom_head,
`right` AS `left`, right_head AS left_head
FROM rotated_pieces;
Then, it's a pretty simple query to return the result. The code is messed up by the WHERE clause which ensures that each piece is used only once in the solution, if there's a neater way to do this I'd like to know.
# find solution
SELECT A.piece_id AS A, A.rotation AS Ar, B.piece_id AS B, B.rotation AS Br, C.piece_id AS C, C.rotation AS Cr,
D.piece_id AS D, D.rotation AS Dr, E.piece_id AS E, E.rotation AS Er, F.piece_id AS F, F.rotation AS Fr,
G.piece_id AS G, G.rotation AS Gr, H.piece_id AS H, H.rotation AS Hr, I.piece_id AS I, I.rotation AS Ir
FROM rotated_pieces A
INNER JOIN rotated_pieces B ON (A.`right` = B.`left` AND A.right_head != B.left_head)
INNER JOIN rotated_pieces C ON (B.`right` = C.`left` AND B.right_head != C.left_head)
INNER JOIN rotated_pieces D ON (A.bottom = D.top AND A.bottom_head != D.top_head)
INNER JOIN rotated_pieces E ON (D.`right` = E.`left` AND D.right_head != E.left_head
AND B.bottom = E.top AND B.bottom_head != E.top_head)
INNER JOIN rotated_pieces F ON (E.`right` = F.`left` AND E.right_head != F.left_head
AND C.bottom = F.top AND C.bottom_head != F.top_head)
INNER JOIN rotated_pieces G ON (D.bottom = G.top AND D.bottom_head != G.top_head)
INNER JOIN rotated_pieces H ON (G.`right` = H.`left` AND G.right_head != H.left_head
AND E.bottom = H.top AND E.bottom_head != H.top_head)
INNER JOIN rotated_pieces I ON (H.`right` = I.`left` AND H.right_head != I.left_head
AND F.bottom = I.top AND F.bottom_head != I.top_head)
WHERE A.piece_id != B.piece_id AND A.piece_id != C.piece_id AND A.piece_id != D.piece_id
AND A.piece_id != E.piece_id AND A.piece_id != F.piece_id AND A.piece_id != G.piece_id
AND A.piece_id != H.piece_id AND A.piece_id != I.piece_id
AND B.piece_id != C.piece_id AND B.piece_id != D.piece_id AND B.piece_id != E.piece_id
AND B.piece_id != F.piece_id AND B.piece_id != G.piece_id AND B.piece_id != H.piece_id
AND B.piece_id != I.piece_id AND C.piece_id != D.piece_id AND C.piece_id != E.piece_id
AND C.piece_id != F.piece_id AND C.piece_id != G.piece_id AND C.piece_id != H.piece_id
AND C.piece_id != I.piece_id
AND D.piece_id != E.piece_id AND D.piece_id != F.piece_id AND D.piece_id != G.piece_id
AND D.piece_id != H.piece_id AND D.piece_id != I.piece_id
AND E.piece_id != F.piece_id AND E.piece_id != G.piece_id AND E.piece_id != H.piece_id
AND E.piece_id != I.piece_id
AND F.piece_id != G.piece_id AND F.piece_id != H.piece_id AND F.piece_id != I.piece_id
AND G.piece_id != H.piece_id AND G.piece_id != I.piece_id
AND H.piece_id != I.piece_id;
This returns 4 rows, the first is our solution:
2,1, 1,0, 6,0, 8,3, 9,3, 7,2, 5,3, 3,0, 4,0
The remaining 3 are the same solution with the entire board rotated:
6,1, 7,3, 4,1, 1,1, 9,0, 3,1, 2,2, 8,0, 5,0 4,2, 3,2, 5,1, 7,0, 9,1, 8,1, 6,2, 1,2, 2,3 5,2, 8,2, 2,0, 3,3, 9,2, 1,3, 4,3, 7,1, 6,3
I would argue the SQL version is clearer, but the Prolog version is slightly terser and should be easier to extend to a 4x4 puzzle.
