Yesterday I posted the solution to a puzzle in response to one created by Reilly. The solution is fine, but I explained it badly. The explanation just describes the finished code, which is all well and good, but it doesn't elucidate the steps I took to get there and isn't likely to help anyone as a result.
The following steps are much closer to what I actually did:
1. While reading Reilly's Prolog version I realized that SQL could probably solve the puzzle by generating a list of all the possible combinations of pieces (either by a join or in a temporary table) and then filtering those in some way to remove invalid solutions.
2. I left it at that for a while, but a few thoughts popped into my head during the day on the structure of a "pieces" table and an INSERT statement that could generate the 4 possible rotations of each piece. I also ran the numbers in my head and realized there were 4^9 = 2^18 = 262,144 combinations which is not many at all really.
3. I initially ran into a bit of a dead end imagining how a SELECT statement would generate all the combinations of pieces, but decided to just start writing it out and see where that led.
This was the crucial step: Starting with the desired result and working backwards.
So, I started with what I wanted: A list of piece numbers and rotations in each position of the puzzle:
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
Then I started joining tables together to match the constraints of the puzzle (i.e. the animals on the adjacent edges match head-to-tail.) At this point I didn't know what fields were going to be in the table, or what it would be called, so I just made them up so the SELECT statement read nicely. First, I'll show the overall structure and come back to the "matches" bits:
FROM rotated_pieces A INNER JOIN rotated_pieces B ON -- A.right matches B.left -- INNER JOIN rotated_pieces C ON -- B.right matches C.left -- INNER JOIN rotated_pieces D ON -- A.bottom matches D.top -- INNER JOIN rotated_pieces E ON -- D.right matches E.left AND B.bottom matches E.top -- INNER JOIN rotated_pieces F ON -- E.right matches F.left AND C.bottom matches F.top -- INNER JOIN rotated_pieces G ON -- D.bottom matches G.top -- INNER JOIN rotated_pieces H ON -- G.right matches H.left AND E.bottom matches H.top -- INNER JOIN rotated_pieces I ON -- H.right matches I.left AND F.bottom matches I.top --
My "matches" criteria was initially something like:
( (A.right = B.left AND A.right_head = 'head' AND B.left_head = 'tail') OR (A.right = B.left AND A.right_head = 'tail' AND B.left_head = 'head'))
This makes sure the animals are the same and it's either head-tail or tail-head.
That seemed like it might work which was a pretty good sign I was on the right track. I wasn't sure how many combinations this would match, so decided to leave a WHERE clause for later. I was hoping this would be a unique solution, or there may be just a couple and I could pick the proper solution out by hand. Either way, that was a problem for later.
4. From this sketch of a SELECT statement I was able to come up with an appropriate table structure for rotated_pieces:
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));
And then I started on an INSERT statement to populate the table with the piece layouts:
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');
While I was doing this I copy/pasted Reilly's equivalent bit of Prolog code and it was a simple text transformation between the two languages, another very good sign:
Prolog:
tile(1, cheetah_tail, tiger_tail, lion_head, tiger_head).
SQL:
(1, 0, 'cheetah','tail', 'tiger','tail', 'lion','head', 'tiger','head'),
5. At this point, I realized that the "matches" criteria could be simplified a lot:
A.right = B.left AND A.right_head != B.left_head
6. Now I was able to write out the "rotation" function I'd envisioned earlier in the day and realized I wasn't going to need a "pieces" table at all, this program was only going to need the 36 rotated_pieces records, another good sign that I was on the right track.
# 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;
7. Finally, I had all the code sketched out. I checked the syntax for a few things since I'd just been doing it off the top of my head and then executed it. After escaping `right` and `left` as they're keywords (not necessarily the best choice of field names...) the CREATE TABLE and INSERT statements ran. I did a sanity check of the rotated_pieces table and it looked good.
The result of my SELECT statement was disappointing though. As I sort of suspected, there are lots of solutions if you allow a piece to be used more than once and the SELECT returned 1272 rows.
8. I couldn't think of a neat way to check for duplicates so ended up just writing a WHERE clause to do it by brute force:
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;
9. This had the desired result and I got back 4 rows.
'A', 'Ar', 'B', 'Br', 'C', 'Cr', 'D', 'Dr', 'E', 'Er', 'F', 'Fr', 'G', 'Gr', 'H', 'Hr', 'I', 'Ir' 2, 1, 1, 0, 6, 0, 8, 3, 9, 3, 7, 2, 5, 3, 3, 0, 4, 0 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
The first row clearly matched Reilly's solution, but it wasn't immediately obvious what the other 3 rows were. After reformatting them into a 3x3 grid and staring for a little while I picked out the pattern of pieces 2-1-6 around the edges and realized it was the whole board being rotated. So there was a single solution after all.
2, 1, 6, 8, 9, 7, 5, 3, 4 6, 7, 4, 1, 9, 3, 2, 8, 5 4, 3, 5, 7, 9, 8, 6, 1, 2 5, 8, 2, 3, 9, 1, 4, 7, 6
10. The next step was to pretend I knew all that from the beginning and write it up in the previous blog post. Later that evening I thought again and realized that wasn't so truthful and that I should have another shot at writing it up.
Postscript: The ugly WHERE clause was still bugging me and I realized that it could be improved by making some kind of function involving all of the piece ids and checking the answer e.g. if they all add to 45 then that's a solution. Unfortunately, addition isn't a uniquely identifying function, and neither is multiplication or addition of 2^piece_id. What will work though is changing the piece ids to prime numbers and multiplying them all together. Keeping the first digit the same the ids are now:
11, 23, 31, 41, 53, 61, 71, 83, 97
The product of these primes has no other factors and we don't care about the order since multiplication is cummutative, so to ensure each piece appears only once the WHERE can now simply be:
WHERE A.piece_id * B.piece_id * C.piece_id
* D.piece_id * E.piece_id * F.piece_id
* G.piece_id * H.piece_id * I.piece_id
= 11*23*31*41*53*61*71*83*97;
