Tuesday, June 21, 2011

SQL: 3x3 Square Picture-Puzzle Solution

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.

1 comment:

Tom said...

Oh, and I forgot to time it: ~0.8 seconds, so it's not even slow :)