Lab: Beyond Program Correctness

In the reading today, we introduced the Rook's Tour problem as an example of inductive reasoning outside of program correctness:

Chess is played on a $n\times n$ board (with $n=8$ usually). There are a variety of pieces in chess, each of which move in a different way. For these claims, we will consider two pieces:

• The rook which can move any number of squares in a cardinal (non-diagonal) direction.
• The knight which moves in a L-shaped pattern: 2 squares horizontally, 1 square vertically or 2 squares vertically, 1 square horizontally.

Furthermore, we will consider two problems (really, thought experiments because these specific situations never arise in a real chess game) when only one such piece is on the board.

• The walk is a sequence of moves for a single piece that causes the piece to visit every square of the board. It is ok if the piece visits the same square multiple times.
• A tour is a walk with the additional property that the piece visits every square exactly once. In a tour, a piece cannot visit the same square multiple times.

When considering walks and tours, we are free to initially place our piece on the board at any position. In addition, we only consider a square visited if the piece ends its movement on that square. With these things in mind, use induction to prove the following fact:

Claim (Rook's Tours). There exists a rook's tour for any chessboard of size $n\ge 1$.

(Hint: we need an object to perform induction over. What inductively defined structures are present in the claim?)

We'll focus on the Rook's Tour for our lab. Likely, you came up with a solution that "works," but the proof was difficult! We will discuss this discrepancy in class and collaboratively develop a proof (and corresponding algorithm) that works with our inductive reasoning principle!

Additional problem: Knight's Walk

The other problem alluded to in the description is a Knight's Walk.

Claim (Knight's Walk). There exists a rook's tour for any chessboard of size $n\ge 4$.

While seemingly more complicated because of how knight's move, this proof is a relatively straightforward induction. Feel free to give it a shot!