Fast algorithm to find closed knight's tour

Question

I'm learning about knight's tour algorithm. I implemented using recursive fine but it take a long time and almost not a closed tour.

Now, I'm currently finding a fast algorithm for finding closed tour. Can someone recommend me some algorithm?

Update: I have read somewhere a heuristic for find a closed knight tour like this: Min[F(x, y)] where F(x,y) is a set of f(x,y)=Min(x-1, n-x) + Min(y-1, n-y) and (x, y) is the position of next step and n is the size of chess board. But how do I use that heuristic?

Answer 1

I solved this problem today implementing a Depth First Search in the Knight Graph (the graph modelling the Knight's possible movements).

While I spent my whole afternoon wondering why Warnsdorff's heuristic was not enough, the problem was my starting point.

I was starting the DFS from the (0,0) position. It looks like the DFS is critically improved if you start somewhere in the middle, like (3,3). After changing this, the algorithm speed wen t from (no solutions within 1 hour) to (1 solution within 1 seconds).

I've tested your Min[F(x,y)] heuristic as well, and it worked seemingly with the same performance as Warnsdorff's rule (for a 8x8 table).

Answer 2

The knight's tour problem is in fact about finding a hamiltonian cycle in the corresponding graph, which is known to be NP-hard, so this problem also may be hard to solve.

However, there are several heuristics which allow you to perform a fast lookup. One of such heuristics is Warnsdorff's rule:

On each step to move to the square, from which the less possible moves are available. If there are several such squares, move to any one of them.

It's a very good heuristics, and for long time has been considered in fact as the solution for knight's path problem, and examples showing that the second part of the rule may lead to incorrect decision were found much later with computer usage.