I am working on two algorithms. The first needs to be able to take a randomly sized grid of squares, only some of which can be used. I need an algorithm to find the path among the squares that will hit the most of them without ever crossing the same square twice. My Idea for this algorithm was to use a minimax search where the evaluation func simply was the ply. Then I could find the best line. Any better more efficient ideas? My second algorithm was to take 2 points on a like board, and figure out if you can draw a line connecting them only using squares once, and not using any disabled squares. This needs to be very efficient. Thanks for any help!

Your grid of squares is basically a graph. Each square is a node in the graph and the connections between the squares denote the graph edges.

If a path exists that connects two nodes and visits every node exactly once, it is known as a Hamilton path (or tour, or circuit)


That should get you started.


(Edited by mod to make link clickable)

[Edited by - Timkin on September 14, 2004 8:58:33 PM]