DEC 31, 2011

# Solving One Tough Puzzle

This year for Christmas, Emilie's grandparents got each family member a different puzzle or game. One in particular that really caught my eye was Emilie's sister's gift: a three-by-three puzzle that claims to have "300,000 wrong ways, but only one right way to assemble."

The puzzle is called "One Tough Puzzle" (available from Amazon and others) and consists of 9 puzzle pieces, each with four interlocks (two in and two out). The interlocks are shaped like each of the four suits in a conventional deck of cards, so a positive heart interlock can link with a negative heart interlock, and so on. Below is a picture of what the puzzle pieces more or less look like.

Image credit: Official Product Page

To solve the puzzle, one must arrange the pieces such that they form a three by three square when interlocked. The outer edges don't necessarily have to be neat or uniform in any way, but the box does specify that there will be six interlocks protruding from the edge of the finished puzzle. Because of this lack of an edge, the puzzle offers basically no hints as to whether or not you're headed down the right path, making it especially frustrating and probably near impossible for someone without tons of time on his or her hands.

After a lot of trying, I did solve it (though not necessarily by conventional means). So, for the impatient (or the Google searchers), here's the solution (assuming your puzzle pieces match the ones I worked with):

``````H: Heart
C: Club
D: Diamond
D       S
+---|---+---|---+---|---+
|   S   |       |       |
-H      -D      -H      -S
|       |   H   |   C   |
+---|---+---|---+---|---+
|   S   |       |       |
-C      -S      -C      -D
|       |   H   |   D   |
+---|---+---|---+---|---+
|   H   |       |       |
-D      -D      -C      -H
|       |   C   |   C   |
+---|---+---|---+---|---+
``````

For the more curious, I'll talk a little bit about how I solved it. If you're only here for the solution, bail out now.

First of all, I should make it clear that I didn't just try different combinations by hand until I found the solution. I'm not nearly patient enough, and I don't think that would even be all that much fun. Instead, I wrote a small program (a script really) that tries all the possible arrangements until it finds a solution. This is obviously much faster than trying combinations by hand because no physical pieces are being moved, and a computer can think considerably faster than a human.

I wrote the script in JavaScript, the language used to add functionality to most web pages, so that anyone will be able to run it right here from this blog post. To that end, I've created a jsFiddle that you can test drive right here. I apologize about how primitive the interface is; it's really meant to be a proof of concept. If you'd like to create a better interface, feel free.

To use it, just set the interlocks on each of the pseudo pieces (the red squares at the top). `+` means the interlock is protruding, and `-` means it isn't. If your puzzle pieces are the same as mine, you shouldn't have to change a thing; just hit the `Solve` button. The solution to whatever you've entered will print below the `Solve` button, unless one can't be found.

EDIT: I've also added a second button, `Find Solutions with Flipped Pieces`, that will do exactly what it says. Any piece marked with an `F` in the solutions is a flipped version of another piece. (This one takes a few seconds to run)

Mobile Users: Use this link for full screen.

All of the code is available in a Gist (MIT License). If you'd like to tinker with it, you should probably do it from the Gist, not the jsFiddle. I've directly imported the solving functionality in the fiddle, so you can't really mess with it too much, but I have included an html page that has the same content as the fiddle in the Gist.

To play with it, clone the Gist, run the tests, and open the demo:

``````\$ git clone git://gist.github.com/1544631.git onetoughpuzzle
\$ cd onetoughpuzzle
\$ open tests.html
\$ open playground.html
``````

If you're curious about the algorithm used, I'll talk about that now. At the core of the script is a function called `solvePuzzle` that does all the state exploration and real solving. It employs a depth-first search using a stack to keep track of states to be explored. By state, I mean the following:

• A partially filled board (filled left to right, top to bottom) with valid pieces placed in specific orientations.
• The remaining pieces not yet used on the board.

The algorithm, in plain English, looks like this:

• Create a new state that is just the empty board with all of the pieces remaining to be placed.
• Add it to the workspace (states to be explored next, represented by a stack).
• Repeat the following until a solution is found:
• Pop (remove) the first state in the workspace.
• Using this state, evaluate each piece remaining to be placed one at a time:
• If the piece can fit in the next available space on the board in any of its four rotated orientations, create a new state with that piece placed in each valid orientation and add that to the workspace.

If a state is ever removed from the workspace and found to be a valid solution, the algorithm exits successfully. If, however, the workspace is ever depleted of states, no solution exists for the puzzle and the algorithm exits unsuccessfully. The actual code for the algorithm is below.

``````var solvePuzzle = function(pieces) {
// Helper function that removes the first element of an array, if there is one.
var shortened = function(ary) { return ary.length <= 1 ? [] : ary.slice(1); }

var board = new Board();
var workspace = [];

// Push initial empty board state
workspace.push(new State(board, pieces));

while (true) {

// Base case that will be triggered if a solution is not found
if (workspace.length <= 0) return null;

// Retrieve the top state on the workspace
var state = workspace.pop();

var board = state.board;
var pieces = state.pieces;

// Base case that will be triggered when the board is filled
if (board.isFull()) return board;

for (var i = 0; i < pieces.length; i++) {
// Retrieve one of the remaining pieces
var piece = pieces[i];

// Strip that piece out of the pices left over
var nextPieces = pieces.slice(0, i).concat(pieces.slice(i + 1, pieces.length));

// Generate rotations of the retrieved piece
var piece2 = piece.rotated();
var piece3 = piece2.rotated();
var piece4 = piece3.rotated();

// If any rotation of the piece fits in the next available space,
// create the state with that piece added to the board and push
// it onto the workspace stack
if (board.canFitNextPiece(piece)) workspace.push(new State(board.withNextPiece(piece), nextPieces))
if (board.canFitNextPiece(piece2)) workspace.push(new State(board.withNextPiece(piece2), nextPieces));
if (board.canFitNextPiece(piece3)) workspace.push(new State(board.withNextPiece(piece3), nextPieces));
if (board.canFitNextPiece(piece4)) workspace.push(new State(board.withNextPiece(piece4), nextPieces));
}
}
}
``````

There's obviously quite a bit more code that defines the models for pieces and boards, as well as a test suite I used while writing the logic. I can't promise that it's bulletproof, so please let me know if you find any mistakes.

I had a lot of fun working on this problem, and I hope it was at least half of an interesting read, even if search algorithms are old news to you.

Cheers, and Happy New Year!