[Solved]: Knight's tour from all starting positions

Problem Detail: 

Is it true that for all $n\geq 5$, there is a knight's tour of an $n\times n$ chessboard beginning at every square?

For example, is it correct, that there is no solution for a $5\times5$ board, with start position $(5,4)$?

Asked By : user1511417

Answered By : Yuval Filmus

The Wikipedia article links to several useful papers. According to the paper Solution of the knight's Hamiltonian path problem on chessboards, there is no such tour; see Theorem 3.1(ii). They show that a knight's tour on the 5x5 board always starts or ends at a corner. It's also easy to see that both endpoint squares have the same color. Since the (5,4) square has a different color than the corners, no knight's tour starts at (5,4).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35840

3.2K people like this

 Download Related Notes/Documents