Made an app for solving the Knight's tour problem [1] for various board sizes (n =m<=24). A knight's tour is a sequence of moves by a knight on a chessboard such that each square on the board is visited once and only once a.k.a a Hamiltonian path. A method for finding such paths is using a heuristic deviced by H. Warnsdorff called Warnsdorff's Rule. Using the heuristic we can solve the problem in linear time but sometimes it fails to produce a complete path due to the undeterministic nature of the heuristic.
There are several ways we can improve the success rate of Warnsdorff's Rule:
- Second-level tiebreaking by Ira Pohl [2]. "For each tie move, sum the number of moves available to it at the next level and pick the one yielding a minimum."
- Move-orderings by Squirell and Cull [3]. Use predefined lists of move-orderings to break ties. You can find move-orderings in the their paper that will give you a complete tour on every board with 10 <= n, m < 300.
