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.

Answer 2

This was originally a comment to Martin B's post, but it grew a bit, so I'm posting it as an "answer".

Firstly, the problem of enumerating all possible Hamiltonian Paths is quite similar to the #P complexity class --- NP's terrifying older brother. Wikipedia, as always, can explain. It is for this reason that I hope you don't really need to know every path, but just most. If not, well, there's still hope if you can exploit the structure of your graphs.

(Here's a fun way of looking at why enumerating all paths is really hard: Let's say you have 10 paths for the graph, and you think you're done. And evil old me comes over and says "well, prove to me that there isn't an 11th path". Having an answer that could both convince me and not take a while to demonstrate --- that would be pretty impressive! Proving that there doesn't exist any path is co-NP, and that's also quite hard. Proving that there only exists a certain number, that sounds very hard. Its late here, so I'm a bit fuzzy-headed, but so far I think everything I've said is correct.)

Anyways, my google-fu seems particularly weak on this subject, which is surprising, so I don't have a cold answer for you, but I have some hints?

• Firstly, if each node has at most 2 outgoing edges, then the number of edges are linear in the number of vertices, and I'm pretty sure that that means its a "sparse" graph, which are typically happier to deal with. But Hamiltonian path is exponential in the number of edges, so there's no really easy way out. :)
• Secondly, if the structure of your graph lends itself to this, it may be possible to break the problem up into smaller chunks. Min-cut and strongly-connected-components come to mind. The basic idea would be, ideally, finding that your big graph is in fact, really, 4 smaller graphs with just a few connecting edges between the smaller graphs. Running your HamPath algorithm on those smaller chunks would be considerably faster, and the hope would be that it would be somewhat easy to piece together the sub-graph-paths into the whole-graph-paths. Coincidentally, these are great tongue-twisters. The downside is that these algorithms are a bit difficult to implement, and will require a lot of thought and care to use properly (in the combining of the HamPaths). Furthermore, if your graphs are in fact quite thoroughly connected, this whole paragraph was for naught! :)

So those were just a few ideas. If there is any other aspect of your graph (a particular starting point is required, or a particular ending point, or additional rules about what node can connect to which), it may be quite helpful! The border between NP-complete problems and P (fast) algorithms is often quite thin.

Hope this helps, -Agor.

Answer 3

I would start with a trivial path through the grid, then randomly select locations on the board (using the input seed to seed the random number generator) and perform "switches" on the path where possible. e.g.:

------  to:    --\/--
------         --/\--

With enough switches you should get a random-looking path.