4
$\begingroup$

On an 8 x 8 chessboard consider two squares to be adjacent if and only if they share a common side. All paths below will consist of steps which join one square to an adjacent one. Under these conditions it is easy to construct a Hamiltonian cycle of the chessboard but quite another matter to find Hamiltonian paths with specified boundary conditions. Suppose A and B are two squares of opposite colors. A little bit of experimentation will (probably) convince one that while it seems to be possible to find a Hamiltonian path from A to B$\,$,$\,$ the amount of guesswork involved can be aggravating. Is there any way to improve on trial and error?

Questions:

1) Is it always true that there is a Hamiltonian path joining A to B (as above)?

2) If so, can one give a systematic procedure to find it or at least cut the guesswork to a minimum?

Thanks

$\endgroup$
  • $\begingroup$ Have you tried doing a construction by induction on board sizes that are powers of $2$? Something extremely similar to math.stackexchange.com/a/461273/30402 should work, after a finite amount of legwork to handle different cases. $\endgroup$ – Erick Wong Mar 10 '16 at 0:41

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.