Problem Detail: Is it true that for all $ngeq 5$, there is a knight’s tour of an $ntimes n$ chessboard beginning at every square? For example, is it correct, that there is no solution for a $5times5$ 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 5×5 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
