Problems

Evaluate $a(4,4)$ for the function $a(m,n)$, which is defined for integers $m,n\ge 0$ by $$\begin{array}{rl}a(0,n)& =n+1\text{, if }n\ge 0;\\ a(m,0)& =a(m-1,1)\text{, if }m>0;\\ a(m,n)& =a(m-1,a(m,n-1))\text{, if }m>0\text{, and }n>0.\end{array}$$

Show that a knight’s tour is impossible on a $3\times 3$ grid.

Show that two queens together can attack every square on a $4\times 4$ grid, but one queen on her own cannot do it. This type of problem is called ‘queen’s domination’.

How many queens can you place on a $4\times 4$ grid so that none of them attack each other?

Show an knight’s tour on a $5\times 6$ chessboard. That is, a path where a knight starts at one square, and then visits every square exactly once, making only moves legal to a knight.

Show how five queens can dominate a standard $8\times 8$ chessboard. That is, each square is attacked by some queen.

How many independent queens can you place on a $5\times 5$ grid? That is, so none of them attack each other.

How many ways can you place $8$ rooks independently on a chessboard? That is, so that none of them attack each other.

Why are there no closed knight’s tours on an $n\times n$ grid when $n$ is odd? A knight’s tour is closed if you can get to the first square from the last square by a knight’s move.

Show how to place fourteen dominating bishops on a standard $8\times 8$ chessboard. That is, every square either contains a bishop, or is attacked by some bishop.