Writing a Klondike Puzzle Solver
“Back from the Klondike” is a puzzle invented by Sam Lloyd, and first published in 1898. It looks like this:
You start in the middle (the “3” inside a heart), and can move in any of the eight compass directions (north, west, south, east, northwest, northeast, southwest, or southeast). The distance you may move is indicated by the number on the square, so your first move, starting from the middle, is always exactly three steps. You win when your last step takes you just outside the circle. (That is, you are not allowed to step outside the circle, unless it is on your last step.)
It’s a kind of maze, then, isn’t it? You move from place to place, along well-defined passages, going from some start point to an exit. But it’s a specialized maze, too, because each “corridor” is unidirectional. That is to say, just because you can move from cell A to cell B, does not necessarily imply that you can move from cell B to cell A! It depends on what the number is on cell B.
Traditional mazes are bidirectional. Corridors allow traffic in both directions, freely. With such a traditional maze, we might use any number of techniques to solve it, including using Dijkstra’s algorithm. (I describe this very technique in my book, Mazes for Programmers.)
It turns out, though, that Dijkstra’s works just as well on unidirectional mazes as it does on bidirectional mazes. It’s very straightforward, in fact. I’ll show you how it works.
We’ll do this in two steps.
- Convert the puzzle into a graph (with explicit connections between cells, or nodes).
- Run Dijkstra’s algorithm on the graph.
We’re going to rely on several classes to realize this.
Node- represents a single cell in the graph, with connections to neighbors.
Graph- a collection of
Field- represents the puzzle itself, where connections between nodes are implied by the number on each node.
Solution- computes and encapsulates a solution to the puzzle.
Once we have these four classes, the program itself looks like this:
We instantiate a new
Field instance, reading the puzzle itself from a text file, and then we instantiate a new
Solution instance, to tell us each of the steps from the center to the goal.
grid.txt file is just a simple textual representation of the puzzle. The underscore character is used to represent all “out of bounds” locations, “x” is used to show possible goals, and digits represent valid cells. The file I’m using is (more or less) the original puzzle given by Sam Lloyd (with one correction–see the Wikipedia article).
Let’s start with the
Field class, then. It has a class method called
from_file, which accepts the name of a file and instantiates and initializes a new
Field instance accordingly:
In other words, the out of bounds locations are mapped to
nil, goal locations are mapped to
:goal, and everything else is an integer from 1 to 9.
The constructor is simple, just creating a two-dimensional array in which we’ll eventually store our field data:
Field instances need to look and act like a hash, with row/column as the key. We’d also like to be able to iterate over all of the entries in the field. The following methods ought to do the trick:
Lastly, we’ll add a method to tell us whether a span of cells (from some starting location to an ending location) is valid. A span is valid if every cell along its length is within the field (excepting possibly the last cell, which may be a goal position).
There. That will let us represent a puzzle. The next step is to convert a field like this, into a graph. And in order to convert it into a graph, we need to be able to represent such a data structure.
At it’s core, a graph is just a collection of nodes, so we’ll start with those. A
Node looks like this:
distance attribute will be used later, by the solution phase; we just initialize it to a very large number to start. Also by default, the node does not represent a goal node.
Now, we can define a
There are many ways this might be implemented; I opted for a sparse grid using nested hashes, instead of a two-dimensional array. Go with whatever floats your boat. (Also, I might have prefered to abstract the “row/column” location information–using a trick I learned from the inimitable Corey Haines–but for the sake of keeping things simple, I’m using row/column directly here.)
Now, we have enough to convert a
Field into a
Graph. The following class method on
Graph ought to do the trick. (It’s kind of a beast. Corey, forgive me…)
It’s really not so bad…just a lot of conditions. We need to check the distance recorded at each position in the field, determine whether we can safely move from that position in each of the eight possible directions, and if so, assign the corresponding node in the graph as a neighbor of the current node.
Once that’s all set, we’ve finished the first step! We’ve converted a Klondike puzzle into a graph. All that remains is to process that graph and find a solution to the puzzle. For this, we’ll bring in our
Solution class. (For simplicity’s sake, this implementation will only look for a single solution. Finding all possible solutions is left as an exercise blah blah blah.)
It starts simple enough–the constructor accepts a field, and a starting position, creates a graph from the field, and stores the root (the node in the graph where the puzzle begins). The internal method
#_compute_solution is then called to do the actual work of Dijkstra’s algorithm. It looks like this:
If you aren’t familiar with Dijkstra’s algorithm, here is a slightly simplified version in a nutshell. You start at some position (the
root, here), and add it to a stack (
frontier). The algorithm then loops for as long as there are any cells in that stack. Each iteration looks at each of those cells, checks all neighbors of each one, and if the neighbor has not yet been visited (or has been visited, but was assigned a greater distance from the root), we update that neighbor’s
distance attribute, store the current node and the direction we took to get here (for pathfinding purposes), and then (if the neighbor isn’t a goal position) we add that neighbor to a new list of frontier cells (
new_frontier). If, however, the neighbor was a goal, we save it as the goal (again, for pathfinding). After that internal loop, the new frontier list replaces the old frontier list, and the outer loop repeats.
When all is said and done, every cell will have been visited and assigned a distance value (how far it is from the
root). We can use this information to present a solution path through the puzzle, which is just what the following
#path method does:
We start at the goal, and as long as that node isn’t the
root (where the puzzle started), we prepend the
previous_dir value that we saved (telling which direction was taken to get to that node), and then make the node’s
previous_node the current node. This repeats, all the way back to the root.
And that’s it!
So, what’s the answer to Lloyd’s “Back from the Klondike” puzzle? Let’s see…
That is to say, from the center of the puzzle, move three steps to the southwest, then southwest again, then northeast three times, then southwest three times, and then northwest.
(It turns out that you can also win by going southeast at the very end, as well, but those are the only two possible solutions to this particular puzzle.)
The full implementation, as well as the
grid.txt used to represent Sam Lloyd’s original puzzle, are available in this gist.
And now we’re done! Or…are we? This suggests an interesting problem. How might we randomly generate these Klondike-style puzzles? Hmmm! Stay tuned for a future blog post on the topic…