In chess, a knight at position hr, ci can move in an L-shaped pattern to any of eight positions: moving over one row and up/down two columns (hr ± 1, c ± 2i), or two rows over and one column up/down...

In chess, a knight at position hr, ci can move in an L-shaped pattern to any of eight positions: moving over one row and up/down two columns (hr ± 1, c ± 2i), or two rows over and one column up/down (hr ± 2, c ± 1i). (See Figure 5.10.) A knight’s walk is a sequence of legal moves, starting from a square of your choice, that visits every square of the board. Prove by induction that there exists a knight’s walk for any n-by-n chessboard for any n ≥ 4. (A knight’s tour is a knight’s walk that visits every square only once. It turns out that knight’s tours exist for all even n ≥ 6, but you don’t need to prove this fact.)