The Program

Excerpt from *The Panex Puzzle*,
Mark Manasse, Danny Sleator, Victor K. Wei, and Nick Baxter.

We have written a program (see source code) that finds the shortest sequence of moves that takes the puzzle from any position to any other position. Obviously the amount of time and space required by the program depends on the initial and final positions, as well as the available hardware (In 1983, the original program running on a VAX 11/750 with two megabytes (with up to six megabytes of virtual memory) was able to solve

Xin about an hour, and_{5}Xin under a day; but it could not solve_{6}Xbefore running out of memory.)_{7}Imagine a graph in which each node corresponds to a position (or configuration, state) of the puzzle, and there is an edge connecting two nodes if there is a move that takes one position into the other. If only the top

ktiles of each color are to be exchanged, then the graph needs only to contain a node for each configuration of2ktiles. (Moving pieces of size larger thankcannot help us solve the puzzle, therefore the graph need not contain nodes involving different positions of them.) This graph is undirected since the moves are reversible.A straightforward method of finding a way to get from an initial position to a final position is to generate the corresponding graph, and find the shortest path between the initial and final positions in this graph using Dijkstra's algorithm. The technique we used is just a refinement of this method.

The first refinement is based on the observation that all edges have unit length. Dijkstra's algorithm then works as follows. At any given time we have reached and marked all nodes that are at a distance

dor less from the initial position. We also maintain a list (called thec-list) of all those nodes that are at distance exactlydfrom the starting position. One phase of the algorithm has the effect of extending this distance tod+1. It works by probing all the nodes adjacent to nodes in the c-list. Those that are already marked are ignored, and those that are not marked are now marked, and placed in the new version of the c-list (called then-list). These newly marked nodes are exactly those that are not at distancedor less from the start and for which there is a path of lengthd+1from the start. Therefore, the shortest path to these nodes is of length exactlyd+1. This reaches all the nodes at distanced+1from the start, because a path to a node at distanced+1must go through a node at distanced. The process starts with only the initial node marked and in the c-list. The process terminates when the final node is marked.In order to reconstruct the shortest path, one additional data structure must be maintained. When we mark a node at distance

d+1, we update a pointer in that node to the node at distancedthat caused it to be marked. At the end we can reconstruct the shortest path by following these pointers from the final node to the initial node.One way to reduce the storage requirement is to do the computation in such a way that the full graph is never actually generated. The observation that makes this possible is the following: since the graph is undirected, it is the case that when we reach a node that has been reached before (a marked node in the above algorithm), that node is either on the c-list, or it was on the c-list at the previous phase. (We cannot otherwise reach a previously marked node, since such a path would have been traversed immediately after that node was first detected.) Thus, if we keep the old c-list around (we call it the

o-list), then we can determine if the newly reached node was "marked" simply by determining if it is in the c-list or o-list. The o-list is effectively a boundary that forces the search to go in the right direction.It is necessary to make the test to determine if a node is in the c-list or o-list more efficient than simply scanning these lists. Hashing is a natural way to do this. We keep a hash table that contains all the nodes of the o-list, c-list, and n-list. We also keep these nodes linked together to form the three lists. At the end of each phase the o-list is deleted from the hash table, the c-list becomes the o-list, and the n-list becomes the c-list. (We use separate chaining so that deletion from the table is efficient.) After hashing a node, we need to be able to tell which list that node is in. We do this by keeping a generation found in each node. If the nodes in the c-list are generation

g, then those in the o-list areg-1and those in the n-list areg+1. (We actually only need to keep this modulo 3.)A problem with the method of not keeping the whole graph is that it becomes difficult to reconstruct the solution. If time were not a consideration then we could run the algorithm until we found a path from start to finish and remember the node from which we reached the final one. This node is sure to be on a shortest path from start to finish. We then run the whole program again using the second to last node as our finishing node. The whole solution can be found by repeating this process

ntimes, where there arennodes on the shortest path.A much more efficient way to deal with this difficulty is to search from start and finish simultaneously. The node where the two searches meet is sure to be on a shortest path. This procedure is then recursively applied to find the shortest path from the starting position to the middle position, and then again to find the shortest path from the middle to the final position. With this trick, the time to construct a complete solution is at most

log(n)times the time required to find the middle position, wherenis the number of moves on the shortest path.Making the program search in both directions involves very small changes. We initialize the c-list to contain both the starting and finishing nodes, and we maintain a bit in each node indicating whether that node was found as a result of the search from the start or from the finish. The first common node is the midpoint (or one of a pair of midpoints).

One final trick to reduce the storage requirement takes advantage of the unique color and mirror symmetries of the puzzle. If

xis a position, letx'be the position obtained when the left and right columns ofxare swapped, andx*is that obtained if the colors of all the pieces are swapped. Note thatx*'andx'*are the same. Consider the set of nodes of the c-list that have been reached from the starting position (at a particular moment during the running of the program). This set of positions is closed under the*'operator, that is, ifxis in this set, then so isx*'. This is true for the following reason. Consider a sequence of moves that takes us form the starting position to a positionx. If we take every node in this sequence and apply the *' operator, then we get a legal sequence of positions from the starting position to positionx*'. (Note that the starting position is invariant under the *' operator.) Since the set in question contains all positions reachable in exactlydsteps from the starting position it must containx*'. By only storing one of the two symmetrical positions we can reduce the memory requirement by a factor of two.A similar redundancy occurs because the final position is the initial position with ' applied. This means that the set of nodes accessible from the starting position in

dmoves is the reflection of the set reachable indmoves from the final position. This means that we do not have to store the list of positions reachable from the final position indmoves, which reduces the storage requirement by another factor of two.Here is how we incorporate these ideas into the program to save space. Initially the c-list contains just the starting position. When we generate a position (say

x) adjacent to one in the c-list, we check ifx,x*,x', orx*'are in the hash table. If none of them are, then we just insertxinto the hash table (xandx*'are accessible from the starting position ind+1moves), and continue. Ifx'orx*is in the hash table thenxis the middle position of a solution; the program computes the number of moves (based on the generation numbers ofxand thex'orx*found, either2d+1or2d+2), and terminates.