# Knight's tour chess

whats the algorithim for the knights tour chess problem; it involves starting at a given square on a chess board and then moving to all other squares on the board until all squares have been moved to only once…

For each move, there are between 0 and 8 choices for the next move, and most of the time this number will be closer to 8 than 0. If we assume only 2 possible moves for each position, there would be 2 to the 63rd (or about 10 to the 20th) paths, about the same number required to solve the Towers of Hanoi puzzle.Searching a million paths per second would still require a few million years to find a solution! There are programs out there that will do it for you. There is Warnsdorf’s heuristic, and SolveForm.

SolveFrom works by counting how many next moves would be available for each valid potential move from the current location. This list of potential moves is sorted by the “next move count” and the smallest one selected. A move is made and a recursive call to SolveFrom is made with this new location. If the call returns true, we leave the move in place and exit with a result of true. If the function fails, the move is retracted and the next potential move is tried. If there are no more to try, we exit with the result set to false.

This from a quick Google Search.

You may find these pages interesting:

http://www.markkeen.com/knight.html

http://www.mathworld.com/KnightsTour.html