I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;
$\begingroup$
$\endgroup$
3
-
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
Add a comment
|
$\begingroup$
$\endgroup$
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]).
