# Professor Halfbrain and the fantasy knight

Professor Halfbrain owns a $99\times99$ board for fantasy chess, whose rows are numbered consecutively from $1$ to $99$ and whose columns are also numbered consecutively from $1$ to $99$. A fantasy knight can jump from a square in the $k$-th column to any square in the $k$-th row (and can jump to no other square); note that if the knight can jump from square $x$ to square $y$, then this does not mean that it can also jump from square $y$ to square $x$.

The professor claims that there exists a closed fantasy knight tour on the chessboard that makes the knight visit every square exactly once, and in the end takes it back to its starting square.

Question: Is Halfbrain's claim indeed true, or has the professor once again made one of his mathematical blunders?

## 2 Answers

Yes there is a solution with a very simple strategy:

Start in (1,1).
Always go the right most square that's unvisited

I'll try to illustrate it. I checked it by hand on an 9x9 board and a very nice pattern emerges that makes it clear it works on any X by X board.

\begin{array}{c|cccc} \ &1&2&3&4&5&6&7&8&9\\ \hline 1 & 1 & 79 & 74 & 67 & 58 & 47 & 34 & 19 & 2\\ 2 & 81 & 80 & 77 & 72 & 65 & 56 & 45 & 32 & 17\\ 3 & 78 & 76 & 75 & 70 & 63 & 54 & 43 & 30 & 15\\ 4 & 73 & 71 & 69 & 68 & 61 & 52 & 41 & 28 & 13\\ 5 & 66 & 64 & 62 & 60 & 59 & 50 & 39 & 26 & 11\\ 6 & 57 & 55 & 53 & 51 & 49 & 48 & 37 & 24 & 9\\ 7 & 46 & 44 & 42 & 40 & 38 & 36 & 35 & 22 & 7\\ 8 & 33 & 31 & 29 & 27 & 25 & 23 & 21 & 20 & 5\\ 9 & 18 & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 3\\ \end{array}

Let $(x,y)$ be the square in row $x$, column $y$, so that a fantasy knight can move from $(x,y)$ to $(y,z)$. A closed tour is described by a cyclic sequence $$x_0,x_1,x_2,\ldots,x_{99^2-1},x_{99^2}=x_0,$$ where the knight moves from $(x_0,x_1)$ to $(x_1,x_2)$, then to $(x_2,x_3)$, and so on up to $(x_{99^2-1},x_0)$, then finally back to $(x_0,x_1)$. Each square is visited exactly once, so this is an example of a de Bruijn sequence (specifically a $99$-ary de Bruijn sequence of order $2$). De Bruijn sequences are known to exist (the Wikipedia article describes a construction), so Halfbrain's claim is true.

Some other puzzles on this site have answers involving de Bruijn sequences (I found this, this, this, and this).