This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

For what size boards are knight tours possible?

competition/games/chess/knight.tour.s

A tour exists for boards of size 1x1, 3x4, 3xN with N >= 7, 4xN with N >= 5,

and MxN with N >= M >= 5. In other words, for all rectangles except 1xN

(excluding the trivial 1x1), 2xN, 3x3, 3x5, 3x6, 4x4.

With the exception of 3x8 and 4xN, any even-sized board which allows a tour

will also allow a closed (reentrant) tour.

On an odd-sided board, there is one more square of one color than

of the other. Every time a knight moves, it moves to a square of

the other color than the one it is on. Therefore, on an odd-sided

board, it must end the last move but one of the complete, reentrant

tour on a square of the same color as that on which it started.

It is then impossible to make the last move, for that move would end

on a square of the same color as it begins on.

Here is a solution for the 7x7 board (which is not reentrant).

------------------------------------ | 17 | 6 | 33 | 42 | 15 | 4 | 25 | ------------------------------------ | 32 | 47 | 16 | 5 | 26 | 35 | 14 | ------------------------------------ | 7 | 18 | 43 | 34 | 41 | 24 | 3 | ------------------------------------ | 46 | 31 | 48 | 27 | 44 | 13 | 36 | ------------------------------------ | 19 | 8 | 45 | 40 | 49 | 2 | 23 | ------------------------------------ | 30 | 39 | 10 | 21 | 28 | 37 | 12 | ------------------------------------ | 9 | 20 | 29 | 38 | 11 | 22 | 1 | ------------------------------------

Here is a solution for the 5x5 board (which is not reentrant).

-------------------------- | 5 | 10 | 15 | 20 | 3 | -------------------------- | 16 | 21 | 4 | 9 | 14 | -------------------------- | 11 | 6 | 25 | 2 | 19 | -------------------------- | 22 | 17 | 8 | 13 | 24 | -------------------------- | 7 | 12 | 23 | 18 | 1 | --------------------------

Here is a reentrant 2x4x4 tour:

0 11 16 3 15 4 1 22

19 26 9 24 8 23 14 27

10 5 30 17 31 12 21 2

29 18 25 6 20 7 28 13

A reentrant 4x4x4 tour can be constructed by splicing two copies.

It shouldn't be much more work now to completely solve the problem of which 3D

rectangular boards allow tours.

Warnsdorff's rule: at each stage of the knight's tour, choose the

square with the fewest remaining exits:

1 12 23 44 3 14 25 22 43 2 13 24 35 4 11 28 45 40 47 26 15 42 21 48 27 34 5 36 29 10 41 46 39 16 33 20 49 8 31 18 37 6 9 30 19 38 7 32 17

Mr. Beverley published in the Philosophical Magazine in 1848 this

knight's tour that is also a magic square:

1 30 47 52 5 28 43 54 48 51 2 29 44 53 6 27 31 46 49 4 25 8 55 42 50 3 32 45 56 41 26 7 33 62 15 20 9 24 39 58 16 19 34 61 40 57 10 23 63 14 17 36 21 12 59 38 18 35 64 13 60 37 22 11

References:

``The Construction of Magic Knight Tours,'' by T. H. Willcocks,

J. Rec. Math. 1:225-233 (1968).

"Games Ancient and Oriental and How to Play Them"

by Edward Falkener published by Dover in 1961 (first published 1892)

"Mathematical Magic Show", Martin Gardner, ch. 14

competition/games/chess/mutual.stalemate.p

What's the minimal number of pieces in a legal mutual stalemate?

competition/games/chess/mutual.stalemate.s

6. Here are three mutual stalemate positions. Black is lower case

in the diagrams.

W Kh8 e6 f7 h7 B Kf8 e7 --+--+--+--+--+ | | k| | K| --+--+--+--+--+ | p| P| | P| --+--+--+--+--+ | P| | | | --+--+--+--+--+ | | | | | W Kb1 B Ka3 b2 b3 b4 a4 | | | +--+--+-- | p| p| +--+--+-- | k| p| +--+--+-- | | p| +--+--+-- | | K| +--+--+-- W Kf1 B Kh1 Bg1 f2 f3 h2 | | | | --+--+--+--+ | p| | | --+--+--+--+ | p| | p| --+--+--+--+ | K| b| k| --+--+--+--+

Continue to: