Experimenally finding optimal algorithms for constructing knight's tours.
Two things to note here:
- This project is largely based on a short paper: DOI: 10.1109/CEC.2004.1331065
- It's still work in progress.
The knight's tour is series of moves of a chess knight that visits all squares on the board exactly once. It's a classical combinatorics problem.
Many algorithms and heuristics have been developed to solve this problem.
I implemented depth-first search, with a backtracking approach. I'm currently writing different algorithms to solve the problem of knigh's tour.
The important key insight was: For each step, always visit the square with the minimum number of onward moves first. This increases performance tremendously when compared with random selection. This is called [Warnsdorff's rule](
This simple priority queue idea has made all the difference, reducing the total runtime from a 10 seconds to 50ms (!)
- It's a plain java project. Just clone it and open it in your IDE.
- Locate the class demoSearch. This is the driver class. You can set the starting position (x,y) of the Knight. Default board size is 8x8. This, too can be changed.
- To see the visualization, use ChessBoard class. This is experimental. There are some issues with saving the image.
- For backtracking: Replace List candidates with a Priority Queue? Might be even faster, because this approach does not need to sort the List. However, since the list.length will never exceed 8, it's unlikely to have any significant effect.