16
$\begingroup$

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?

$\endgroup$
25
$\begingroup$

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}

$\endgroup$
21
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.