4
$\begingroup$

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once.

I noticed something strange, though: when the size of the chessboard is odd, about $50/60\%$ of the starting positions, at least for small numbers, return a wrong path, while for even sized boards about $1\%$ return a wrong result.

Actually the errors increase more the board increases in size. On this plot you can see the different behaviour for even and odd sized boards: enter image description here

I wonder if there is a theoretical (maybe heuristic) reason for this difference.

$\endgroup$
2
  • $\begingroup$ Reviewing/checking your code is off-topic here (and probably everywhere on the Stack Exchange network). $\endgroup$
    – D.W.
    Dec 9 '21 at 6:32
  • $\begingroup$ @D.W. I didn't want that someone checked my code, I added it so that one can reproduce what I found and maybe dig up if necessary... Afterall It turned out to not be necessary so I delete it $\endgroup$
    – Tortar
    Dec 9 '21 at 12:22
4
$\begingroup$

For odd-sized boards, a knight's tour must start and end on the same color as the corner squares of the board. It follows that for about half (50%) of starting squares, there is no possible knight's tour and the search is bound to fail, explaining your error rate.

In contrast, for an even-sized board, the knight can start on either color. I didn't read your code in detail, but I can confidently conjecture that this explains the pattern you observed!

  • For example, consider a 7x7 board, and assume the corner squares are black. Then there are 25 black squares, and 24 white squares. Any knight's tour alternates between black and white squares, but it must visit more black squares than white squares. So in order to visit all 49 squares, it has to start on a black square.

  • On the other hand, consider a 6x6 board. There are 18 black squares, and 18 white squares. A knight's tour here alternates between black and white squares, but it my start on either color

I suspect that if you fix this and always start the knight's tour on the same color, you will see a more similar range of error rates for even- and odd-sized boards.


Edit: We can be a bit more precise about the error rate. If $n$ is odd, then $\frac{n^2 + 1}{2}$ squares are black, and $\frac{n^2 - 1}{2}$ squares are white, out of $n^2$ squares total. So the error rate for a random starting square is at least $$ \frac{(n^2 - 1)/2}{n^2} = \frac{1}{2} - \frac{1}{2n^2}, $$ which is actually a bit less than 50% if $n$ is small.

$\endgroup$
4
  • 1
    $\begingroup$ I was expecting something more esoteric because the rule is a magic one (at least for me), but in the end it is a really simple reason! Thank you $\endgroup$
    – Tortar
    Dec 9 '21 at 0:46
  • $\begingroup$ Anyway adressing your point of equal range, your answer explains also why "the slope" of the line of the even-sized boards is about twice the one for odd-sized boards : there are just ~50% of them in respect to the even one for which the rule applies! $\endgroup$
    – Tortar
    Dec 9 '21 at 0:50
  • 2
    $\begingroup$ @Tortar True! good observation, I didn't notice that. $\endgroup$
    – 6005
    Dec 9 '21 at 0:54
  • $\begingroup$ Nice answer! See here also: cs.meta.stackexchange.com/q/657/472 $\endgroup$
    – Juho
    Dec 9 '21 at 5:46

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.