Problem of the Month (August 2005)

One of the best-known recreational math puzzles of all time is finding a knight tour of all 64 squares on a 8×8 chessboard:

This month, we investigate trivial knight tours (TNTs), knight tours with the property that the only squares on the tour which are a knight's move apart are neighbours on the tour. Thus after the first knight move, all further knight moves in the loop are determined. The problem is to find the longest such tour for a given board.

Jonathan Welton, who suggested this problem, has found TNTs on square chessboards from 3×3 to 10×10, and shown them to be maximal by exhaustive search:

length 8

length 10

length 16

length 20

length 22

length 32

length 40

length 48

What are the maximal TNTs on larger square boards? What about rectangular boards? What about paths instead of cycles?

What are the maximal trivial tours for other chess pieces: rooks, bishops, kings, and queens? What about other "fairy chess" pieces?

ANSWERS

Knights

Maximum Length of Trivial Knight
Tour of m × n Rectangles

m \ n	3	4	5	6	7	8	9	10
3	8
4	10	10
5	10	10	16
6	10	10	16	20
7	12	14	16	22	22
8	14	16	18	22	26	32
9	14	18	20	28	30	34	40
10	18	20	22	32	34	38	44	48
11	18	22	24	34	38	42
12	22	22	28	34	40
13	22	26	30	40
14	24	28	30	44
15	26	30	32	46
16	28	30	36
17	30	32	38
18	32	36	40
19	34	38
20	36	40

Jonathan Welton
Dave Langers

Here are the smallest known 3-regular and 4-regular realizations for knights:

(Tino Jonker)

In 2009, Jonathan Welton found the disjoint tours below that have 24 knights on a 7×7 board and a 4×12 board:

Queens

Maximum Length of Trivial Queen
Tour of m × n Rectangles

m \ n	1	2	3	4	5	6	7	8	9	10
2	0	3
3	3	4	4
4	3	4	4	6
5	3	4	6	6	7
6	3	4	6	8	8	9
7	3	4	6	8	9	10	11
8	3	4	6	8	10	11	12	13
9	3	4	6	8	10	12	13	14	14
10	3	4	6	8	10	12	14	14	16	16
11	3	4	6	8	10	12	14	15	16
12	3	4	6	8	10	12	14	16

Dave Langers

Ed Pegg suggested that we look for other graphs besides cycles, the only connected 2-regular graphs. The next natural candidates are the disconnected 2-regular graphs. Here are the smallest known boards that a queen can realize for the disconnected 2-regular graphs of size 6 through 9.

(Dave Langers)

Here are the smallest known boards that a queen can realize for the 3-regular graphs of size 4, 6, 8, and 10. Can anyone improve these?

(Dave Langers)

(Daniele Degiorgi)

(Dave Langers)

Here is the smallest known realization for the Heawood graph, and the dodecahedron graph:

(Geoff Exoo)

Geoff Exoo showed that all 3-regular graphs with 14 vertices can also be realized by queens. I conjecture that all 3-regular graphs can be realized this way.

Here is the smallest known 4-regular realization for queens, and the smallest known realization for the 4-cube. What are some other 4 regular graphs?

(Geoff Exoo)

Dave Langers asks "For small n, what is the smallest board that contains a cycle of winding number (the number of revolutions you turn while you follow the cycle) n?"

Kings

On an n×n chessboard, the maximum tours are apparently vertical zig-zags, and have length 2(n–5)_⌊(n+5)/4_⌋ + 12, for n≥4. Can anyone prove this? What is the formula for an m×n chessboard?

Kings have a trivial 3-regular configuration on a 2×2 board, but the next smallest connected 3-regular graph I found was on a 7×5 board. Is there one in between these two? It's clear that kings can only produce planar regular graphs.

Bishops

The problem for bishops is easier. On an m×n chessboard, the maximum tour apparently has length 2n–4, for m=n≥4, and 2((m–1)/4 + (n–1)/4) if m≠n. Can anyone prove this? It is easy to prove that bishops do not admit 3-regular configurations.

Rooks

The problem for rooks is trivial. On an m×n chessboard, the maximum tour has length 2 min{m,n}, and each optimal tour either contains 2 rooks in each row or 2 rooks in each column. Rooks also do not admit 3-regular configurations.

Fairy Chess Pieces

Amazons

Amazons move either like a queen or knight.

Maximum Length of Trivial Amazon
Tour of m × n Rectangles

m \ n	1	2	3	4	5	6	7	8
2	0	3
3	3	3	3
4	3	4	4	5
5	3	4	4	6	6
6	3	4	4	6	8	8
7	3	4	6	6	8	9	9
8	3	4	6	7	9	10	11	12
9	3	4	6	7	9	10
10	3	4	8	7	9	11
11	3	4	8	7	10

Archbishops

Archbishops move either like a bishop or knight.

Maximum Length of Trivial Archbishop
Tour of m × n Rectangles

m \ n	2	3	4	5	6	7	8
3	6	6
4	6	6	6
5	6	6	6	8
6	6	7	7	12	13
7	8	8	8	12	16	16
8	8	10	10	14	16	18	20
9	10	11	11	16	18
10	12	12	12	18
11	12	14	14

Empresses

Empresses move either like a rook or knight.

Maximum Length of Trivial Empress
Tour of m × n Rectangles

m \ n	1	2	3	4	5	6	7
2	0	4
3	3	4	4
4	3	4	4	5
5	3	4	5	6	8
6	3	4	6	7	9	11
7	3	4	6	8	10	12	14
8	3	4	6	8	10	12	14

Fivers

Fivers move to a square exactly 5 units away, either 5 squares horizontally or vertically, or as the hypotenuse of a 3-4-5 triangle.

Maximum Length of Trivial Fiver
Tour of m × n Rectangles

m \ n	4	5	6	7
6	0	8	12
7	0	16	20	28
8	0	18	24
9	18	18	26
10	18	20
11	18	22

Squirrels

Squirrels move 2 squares either horizontally or vertically, and 0, 1, or 2 squares in a perpendicular direction.

Maximum Length of Trivial Squirrel
Tour of m × n Rectangles

m \ n	2	3	4	5	6	7
3	4	4
4	4	4	7
5	4	5	7	8
6	4	6	8	10	12
7	4	7	12	14	14	16
8	4	8	12	14	16	18

Zebras

Zebras move 3 squares either horizontally or vertically, and 2 squares in a perpendicular direction.

Maximum Length of Trivial Zebra
Tour of m × n Rectangles

m \ n	4	5	6
5	0	16
6	0	22	26
7	10	24	26
8	10	26

Giraffes

Giraffes move 4 squares either horizontally or vertically, and 1 square in a perpendicular direction.

Maximum Length of Trivial Giraffe
Tour of m × n Rectangles

m \ n	3	4	5	6	7
5	0	0	16
6	0	0	18	18
7	0	0	20	30	32
8	0	0	22	30
9	4	4	26

Double Kings

Double Kings make 2 king moves.

Maximum Length of Trivial Double King
Tour of m × n Rectangles

m \ n	1	2	3	4	5	6
2	0	3
3	3	3	3
4	3	3	3	4
5	3	3	3	6	8
6	3	3	3	6	8	8
7	3	3	3	8	10	10
8	3	3	3	10	12	12

Sparklers

Sparklers move either 1 space horizontally or vertically, or 2 spaces diagonally.

Maximum Length of Trivial Sparkler
Tour of m × n Rectangles

m \ n	2	3	4	5	6	7
2	4
3	4	6
4	4	8	8
5	4	10	10	16
6	4	10	14	16	17
7	4	12	14	18	19	22
8	4	14	16	20	22
9	4	14	20	22

Oxen

Oxen move 3 spaces horizontally or vertically, and 0 or 1 spaces in a perpendicular direction.

Maximum Length of Trivial Ox
Tour of m × n Rectangles

m \ n	2	3	4	5	6
4	4	4	6
5	4	4	8	12
6	4	4	8	15	20
7	4	4	11	16	22
8	4	4	12
9	4	4	16
10	4	6

Guenter Stertenbrink found a piece (that moves distance √5 or √8) that can realize the Petersen Graph on a 4×4 board:

m \ n	3	4	5	6	7	8	9	10
3	8
4	10	10
5	10	10	16
6	10	10	16	20
7	12	14	16	22	22
8	14	16	18	22	26	32
9	14	18	20	28	30	34	40
10	18	20	22	32	34	38	44	48
11	18	22	24	34	38	42
12	22	22	28	34	40
13	22	26	30	40
14	24	28	30	44
15	26	30	32	46
16	28	30	36
17	30	32	38
18	32	36	40
19	34	38
20	36	40

m \ n	1	2	3	4	5	6	7	8	9	10
2	0	3
3	3	4	4
4	3	4	4	6
5	3	4	6	6	7
6	3	4	6	8	8	9
7	3	4	6	8	9	10	11
8	3	4	6	8	10	11	12	13
9	3	4	6	8	10	12	13	14	14
10	3	4	6	8	10	12	14	14	16	16
11	3	4	6	8	10	12	14	15	16
12	3	4	6	8	10	12	14	16

m \ n	3	4	5	6	7	8	9	10
3	8
4	10	10
5	10	10	16
6	10	10	16	20
7	12	14	16	22	22
8	14	16	18	22	26	32
9	14	18	20	28	30	34	40
10	18	20	22	32	34	38	44	48
11	18	22	24	34	38	42
12	22	22	28	34	40
13	22	26	30	40
14	24	28	30	44
15	26	30	32	46
16	28	30	36
17	30	32	38
18	32	36	40
19	34	38
20	36	40

m \ n	1	2	3	4	5	6	7	8	9	10
2	0	3
3	3	4	4
4	3	4	4	6
5	3	4	6	6	7
6	3	4	6	8	8	9
7	3	4	6	8	9	10	11
8	3	4	6	8	10	11	12	13
9	3	4	6	8	10	12	13	14	14
10	3	4	6	8	10	12	14	14	16	16
11	3	4	6	8	10	12	14	15	16
12	3	4	6	8	10	12	14	16

Problem of the Month (August 2005)

ANSWERS

Fairy Chess Pieces

Other Questions

m \ n	3	4	5	6	7	8	9	10
3	8
4	10	10
5	10	10	16
6	10	10	16	20
7	12	14	16	22	22
8	14	16	18	22	26	32
9	14	18	20	28	30	34	40
10	18	20	22	32	34	38	44	48
11	18	22	24	34	38	42
12	22	22	28	34	40
13	22	26	30	40
14	24	28	30	44
15	26	30	32	46
16	28	30	36
17	30	32	38
18	32	36	40
19	34	38
20	36	40

m \ n	1	2	3	4	5	6	7	8	9	10
2	0	3
3	3	4	4
4	3	4	4	6
5	3	4	6	6	7
6	3	4	6	8	8	9
7	3	4	6	8	9	10	11
8	3	4	6	8	10	11	12	13
9	3	4	6	8	10	12	13	14	14
10	3	4	6	8	10	12	14	14	16	16
11	3	4	6	8	10	12	14	15	16
12	3	4	6	8	10	12	14	16