We present
solutions of benchmark instances to the solitaire
computer game Atomix found with different heuristic search methods.
The problem is PSPACE-complete. An implementation of the heuristic
algorithm A* is presented that needs no priority queue, thereby having
very low memory overhead. The limited memory algorithm IDA* is handicapped
by the fact that, due to move transpositions, duplicates appear
very frequently in the problem space; several schemes of using memory
to mitigate this weakness are explored, among those, "partial" schemes
which trade memory savings for a small probability of not
finding an optimal solution. Even though the underlying search
graph is directed,
backward search is shown to be viable, since the branching factor can be
proven to be the same as for forward search.