Rook tour on the chess board Prove that a rook can visit the entire chess board in 15 moves, but not in 14 moves or less. A jumped over square is considered visited, as well as start and end squares. This is a question from an elementary graph theory book. It's in a chapter dedicated to Eulerian and Hamiltonian paths. Such a route is a Hamiltonian path, but how does one calculate the number of rook moves on a Hamiltonian path?

Here's one solution that is pretty much unrelated to graph theory. Not sure if it's the solution intended by the book author.

The rook must move along either all verticals or all horizontals. (Not necessarily entire verticals and horizontals, just some interval on each one). Indeed, assume that there is a horizontal that the rook didn't move along; then it moved through each one of its squares along the corresponding vertical.

Assume w.l.o.g. that it moved along all verticals. It must enter each vertical except the first one and exit each vertical except the last one. Each entry and exit is a turn. Thus there are at least 14 turns, and at least 15 moves.