I'm preparing for a test next week about graph theory. One of the example exercises is about proving that a closed knight's tour exists on an 8-by-8 chess board by only using basic theorems such as Ore's theorem or some other not too complex way. I know that it is possible to construct a knights tour, but I think that that's the right way to proof this theorem as we only have half an hour to solve the question and finding a knights tour by hand (no computers) isn't that simple.

This problem is equivalent to finding a Hamiltonian cycle in a graph representing all of the knight's legal moves between all the squares.

  • $\begingroup$ You didn't explicitly mention it, but uf course $8+8\ll 64$ means that we have to look for something completely different than Ore ... $\endgroup$ – Hagen von Eitzen Jun 24 '17 at 8:41
  • $\begingroup$ Actually, it seems that the knight's tour problem is one where finding a solution by hand is comparatively simple: Warnsdorf's rule is just a heuristic, but happens to work herer and help find a tour in linear time ... $\endgroup$ – Hagen von Eitzen Jun 24 '17 at 8:54

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.