Kagen Schaefer - Puzzle Prime

King’s Route

A chess king starts on one cell of a chessboard and takes a non-intersecting tour, passing through each square once, and ending up on the initial square. Show that the king has made no more than 36 diagonal moves.

SOLUTION

The king must visit the 28 perimeter squares in order; otherwise, he will create a portion of the board which is inaccessible for him. However, he can not travel from one square to a neighboring one using only diagonal moves. Therefore, he must make at least 28 horizontal/vertical moves and at most 64 – 28 = 36 diagonal moves.