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 \ n345678910
38
41010
5101016
610101620
71214162222
8141618222632
914182028303440
101820223234384448
11182224343842
122222283440
1322263040
1424283044
1526303246
16283036
17303238
18323640
193438
203640
Jonathan Welton
Dave Langers

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


(Tino Jonker)

(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 \ n12345678910
203
3344
43446
534667
6346889
7346891011
8346810111213
934681012131414
103468101214141616
1134681012141516
12346810121416
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.

6
(Dave Langers)
7
(Dave Langers)
8
(Dave Langers)

(Dave Langers)
9
(Dave Langers)

(Dave Langers)

(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?

46
(Dave Langers)
8
(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)
10

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Daniele Degiorgi)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

(Dave Langers)

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


(Geoff Exoo)

(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 \ n12345678
203
3333
43445
534466
6344688
73466899
834679101112
93467910
103487911
11348710
Archbishops

Archbishops move either like a bishop or knight.
Maximum Length of Trivial Archbishop
Tour of m × n Rectangles
m \ n2345678
366
4666
56668
66771213
7888121616
88101014161820
91011111618
1012121218
11121414
Empresses

Empresses move either like a rook or knight.
Maximum Length of Trivial Empress
Tour of m × n Rectangles
m \ n12345678
204
3344
43445
534568
63467911
73468101214
83468101214
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 \ n45678
60812
70162028
801824
9181826
101820
111822

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 \ n234567
344
4447
54578
64681012
74712141416
84812141618
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 \ n4567
5016
602226
7102426
81026
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 \ n34567
50016
6001818
700203032
8002230
94426
Double Kings

Double Kings make 2 king moves.
Maximum Length of Trivial Double King
Tour of m × n Rectangles
m \ n123456
203
3333
43334
533368
6333688
733381010
8333101212
Sparklers

Sparklers move either 1 space horizontally or vertically, or 2 spaces diagonally.
Maximum Length of Trivial Sparkler
Tour of m × n Rectangles
m \ n234567
24
346
4488
54101016
6410141617
741214181922
8414162022
94142022
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 \ n234567
4446
544812
64481520
744111622
84412
94416
1046

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


Other Questions

What are best solutions for paths rather than cycles?

When is it possible to cover a board with distinct trivial tours? What is the smallest number of tours that suffices?


If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 6/7/09.