# Professor Halfbrain and the fantasy knight

Professor Halfbrain owns a 99×99 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 𝑘-th column to any square in the 𝑘-th row (and can jump to no other square); note that if the knight can jump from square 𝑥 to square 𝑦, then this does not mean that it can also jump from square 𝑦 to square 𝑥.

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.

1 2 3 4 5 6 7 8 9
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

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).