Routing "paths" through a rectangular array

Question

I'm trying to create my own implementation of a puzzle game.

To create my game board, I need to traverse each square in my array once and only once.
The traversal needs to be linked to an adjacent neighbor (horizontal, vertical or diagonal).

I'm using an array structure of the form:

board[n,m] = byte
Each bit of the byte represents a direction 0..7 and exactly 2 bits are always set
Directions are numbered clockwise
0 1 2 
7 . 3
6 5 4 
Board[0,0] must have some combination of bits 3,4,5 set

My current approach for constructing a random path is:

 Start at a random position
 While (Squares remain)
    if no directions from this square are valid, step backwards
    Pick random direction from those remaining in bitfield for this square       
    Erase the direction to this square from those not picked
    Move to the next square

This algorithm takes far too long on some medium sized grids, because earlier choices remove areas from consideration.

What I'd like to have is a function that takes an index into every possible path, and returns with the array filled in for that path. This would let me provide a 'seed' value to return to this particular board.

Other suggestions are welcome..

Answer 1

Essentially, you want to construct a Hamiltonian path: A path that visits each node of a graph exactly once.

In general, even if you only want to test whether a graph contains a Hamiltonian path, that's already NP-complete. In this case, it's obvious that the graph contains at least one Hamiltonian path, and the graph has a nice regular structure -- but enumerating all Hamiltonian paths still seems to be a difficult problem.

The Wikipedia entry on the Hamiltonian path problem has a randomized algorithm for finding a Hamiltonian path that is claimed to be "fast on most graphs". It's different from your algorithm in that it swaps around a whole branch of the path instead of backtracking by just one node. This more "aggressive" strategy might be faster -- try it and see.

You could let your users enter the seed for the random number generator to reconstruct a certain path. You still wouldn't be enumerating all possible paths, but I guess that's probably not necessary for your application.