Prove that:-

$\bullet$A (open or closed) knight's tour is not possible on a $4\times4$ chess board.

$\bullet$A (open or closed) knight's tour exists on a $8\times8$ chess board.

I want a constructive proof for $8\times8$ board, not just a possible solution. I know that the question boils down to finding a hamiltonian path in Knights' graph.

  • 1
    $\begingroup$ A concrete solution is a constructive proof that a solution exists -- the best and most constructive imaginable. $\endgroup$ – Henning Makholm Nov 14 '16 at 15:30
  • $\begingroup$ @HenningMakholm While I agree with you, I think he wants some insight into why it exists for some dimensions and not for others. What works in $8\times 8$ that fails in $4\times 4$? $\endgroup$ – Arthur Nov 14 '16 at 15:31
  • $\begingroup$ Here is a paper (Schwenk, Math. Mag. 64(5) 325-332, 1991) that seems to solve the general problem. Unfortunately it's behind a spamwall. $\endgroup$ – Henning Makholm Nov 14 '16 at 15:36
  • $\begingroup$ Have a look at the Wikipedia article on the knight's tour. For the general rectangular case, see the article Which Rectangular Chessboards Have a Knight's Tour? by Schwenk. $\endgroup$ – Théophile Nov 14 '16 at 15:36
  • $\begingroup$ Linked. $\endgroup$ – Alex Ravsky Nov 15 '16 at 9:23

Your Answer

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

Browse other questions tagged or ask your own question.