Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 24 down vote accepted

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}

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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