How should a rook move across the chessboard to visit each square exactly once and make the fewest number of turns?

#
We will say that a rook moves along a horizontal (or vertical) line if during its move it moves from one square of this horizontal (vertical) to another. Suppose that the rook has made a tour of the chessboard, visiting each square exactly once. Let's show that during the tour, the rook must either move along each vertical at least once or move along each horizontal at least once. Indeed, suppose there is a vertical along which the rook never moved. This means that each square of this vertical (on all these squares the rook, by condition, has been) the rook passed, moving "across" the vertical, i.e., along the corresponding horizontal. Therefore, the rook moved at least once along each horizontal. Let's assume, for definiteness, that the rook moved at least once along each vertical. On each vertical (except, perhaps, the one from which the tour starts and the one on which it ends), the rook must enter and after moving along the vertical - exit from it. At the same time, entry and exit are necessarily accompanied by turns. Thus, the total number of turns is not less than

$$
6 \cdot 2+1+1=14
$$

(6 verticals with "entry" and "exit", the initial vertical only with "exit", the final one - only with "entry").

Thus, it is impossible to make fewer than 14 turns. At the same time, tours containing exactly 14 turns do exist.

Submit a comment