0
$\begingroup$

I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;

$\endgroup$
  • 1
    $\begingroup$ Is $n$ large enough? A solution doesn't exist for $n < 5$. $\endgroup$ – Juho Dec 9 '19 at 13:43
  • $\begingroup$ n = 10 in my case $\endgroup$ – agamjain14 Dec 9 '19 at 13:53
  • $\begingroup$ For context, wikipedia: Warnsdorff's rule $\endgroup$ – Hendrik Jan Dec 9 '19 at 19:23
2
$\begingroup$

In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack.

So let us consider the $n \times n$ chessboard now. Warnsdorff's rule (nor any other method) won't find a solution for $n < 5$ as a solution exists precisely when $n \geq 5$. Given that $n \geq 5$, an efficient algorithm based on Warnsdorff's rule is described in [1, Proposition 2.2]. Other independently discovered algorithms that work in linear time are known as well (see e.g., [2]).


[1] Conrad, Axel, Tanja Hindrichs, Hussein Morsy, and Ingo Wegener. "Solution of the knight's Hamiltonian path problem on chessboards." Discrete Applied Mathematics 50, no. 2 (1994): 125-134.

[2] Parberry, Ian. "An efficient algorithm for the Knight's tour problem." Discrete Applied Mathematics 73, no. 3 (1997): 251-260.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.