Professor Halfbrain and the fantasy knight

Question

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?

Ivo Beckers · Accepted Answer

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

Julian Rosen · 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).

Professor Halfbrain and the fantasy knight

2 Answers

Add your own answers!

Ask a Question

	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

	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

	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