109 competition/games/chess/knight.tour.p
Description
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.
109 competition/games/chess/knight.tour.p
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:
My Books
