1,1

The simplest fairy chess pieces, going back to 9th-century Persia, are the fers -- a (1,1) leaper -- and the wazir -- a (1,0) leaper. (A king combines the moves of a fers and a wazir.) A fers-wazir tour visits every cell of a board exactly once, making fers and wazir moves alternately, and returns to the starting cell.

Such tours exist only when the number of rows is even and the number of columns is even.

For fixed m, these tours can be enumerated with the transfer-matrix method, so the numbers A(m,n) satisfy a linear recurrence.

D. E. Knuth, Hamiltonian paths and cycles, Section 7.2.2.4 of The Art of Computer Programming (to appear).

D. E. Knuth, Table of n, a(n) for n = 1..66

George Jelliss, Introducing Knight's Tours, has a 9th century example of a fers-knight tour due to As-Suli.

G.f. of column 2: z*(1 - 2*z - z^3)/((1 - z)*(1 - 3*z + z^2 - z^3)). - Filip Stappers, Apr 21 2025

Array begins: (example extended by Filip Stappers, Apr 21 2025)

2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

1, 2, 4, 9, 23, 62, 170, 469, 1297, 3590, 9940, 27525, ...

1, 4, 22, 124, 818, 6004, 46448, 367880, ...

1, 9, 124, 1620, 25111, 455219, 9103712, ...

1, 23, 818, 25111, 882130, 36979379, ...

1, 62, 6004, ...

1, 170, ...

1, ...

...

For m = 2 and n = 3, the A(2,3) = 4 solutions are the following 4-by-6 tours (a to b to ... to x):

.

a-x e-d i-h a w-v p-q s a w-v s-r p a w-v d-e g

X X X |X X X| |X X X| |X X X|

w b-c f-g j x b o u-t r x b t-u o q x b-c u h f

| | | | | | | |

v s-r o-n k e c n h-i k e c i-h n l q o-n t i k

X X X |X X X| |X X X| |X X X|

t-u p-q l-m d f-g m-l j d f-g j-k m p r-s m-l j

Cf. A383154 (the diagonal A(n,n)).

Cf. A339190 (the analog for king tours).

Sequence in context: A055652 A290084 A154844 * A351089 A133831 A325613

Adjacent sequences: A383150 A383151 A383152 * A383154 A383155 A383156

nonn,tabl

Don Knuth, Apr 18 2025

approved