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?

Answer 1

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

Answer 2

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