IIh',l~--"El,t=+n,,~ut+l[,,.-~+am=:l'i"l<=4n+,~nnu,,~+.-1,+,<.--~ M i c h a e l

The Mathematical Knioht Noam D. Elkies Richard P. Stanley

This column is a place for those bits of contagious mathematics that travel from person to person in the community, because they are so

Kleber

and

Ravi Vakil,

u c h h a s b e e n said o f the affinity b e t w e e n m a t h e m a t i c s a n d chess: t w o d o m a i n s of h u m a n t h o u g h t w h e r e v e r y l i m i t e d sets of rules yield inexh a u s t i b l e depths, challenges, frustrat i o n s a n d beauty. Both fields s u p p o r t a v e n e r a b l e a n d b u r g e o n i n g t e c h n i c a l lite r a t u r e a n d attract m u c h m o r e t h a n t h e i r s h a r e of child prodigies. F o r all that, the i n t e r s e c t i o n of t h e t w o dom a i n s is n o t large. While c h e s s a n d m a t h e m a t i c s may favor s i m i l a r mindsets, t h e r e are few p l a c e s w h e r e a c h e s s p l a y e r or a n a l y s t c a n b e n e f i t f r o m a specific m a t h e m a t i c a l idea, s u c h as t h e s y m m e t l 7 o f t h e b o a r d a n d o f m o s t p i e c e s ' m o v e s ( s e e for i n s t a n c e [24]) o r t h e c o m b i n a t o r i a l g a m e t h e o r y o f B e r l e k a m p , Conway, a n d Guy (as in [4]). Still, w h e n m a t h e m a t i c s d o e s find a p p l i c a t i o n s in chess, s t r i k i n g a n d ins t r u c t i v e results often arise.

M

elegant, suprising, or appealing that one has an urge to pass them on. Contributions are most welcome.

Please send all submissions to the Mathematical Entertainments Editor, Ravi Vakil, Stanford University, Department of Mathematics, Bidg, 380, Stanford, CA 94305-2125, USA e-mail: [email protected],edu

22

Introduction This a r t i c l e s h o w s s e v e r a l m a t h e m a t i cal a p p l i c a t i o n s that f e a t u r e t h e knight a n d its c h a r a c t e r i s t i c (2,1) leap. It is b a s e d on p o r t i o n s of a b o o k t e n t a t i v e l y t i t l e d Chess and Mathematics, curr e n t l y in p r e p a r a t i o n b y t h e t w o aut h o r s o f t h i s article, w h i c h will c o v e r all a s p e c t s o f the i n t e r a c t i o n s b e t w e e n chess and mathematics. Mathematically, t h e c h o i c e of (2,1) a n d o f the 8 • 8 b o a r d m a y s e e m to b e a s p e c i a l c a s e o f no p a r t i c u l a r interest, a n d i n d e e d w e shall on o c c a s i o n i n d i c a t e v a r i a t i o n s a n d g e n e r a l i z a t i o n s involving o t h e r l e a p p a r a m e t e r s a n d b o a r d sizes. But long e x p e r i e n c e p o i n t s to t h e s t a n d a r d k n i g h t ' s m o v e and c h e s s b o a r d size as f e l i c i t o u s c h o i c e s n o t o n l y for t h e g a m e o f c h e s s b u t also for p u z z l e s a n d p r o b l e m s involving the b o a r d a n d pieces, including several of our examples. We will begin by c o n c e n t r a t i n g o n p u z z l e s s u c h as the knight's tour. Many o f t h e s e a r e clearly m a t h e m a t i c a l p r o b l e m s in a v e r y thin d i s g u i s e (for ins t a n c e , a c l o s e d knight's t o u r is a H a m i l t o n i a n circuit on a c e r t a i n g r a p h ~), a n d c a n b e solved o r at l e a s t b e t t e r

TIlE MATHEMATICAL INTELLIGENCER 9 2003 SPRINGER VERLAG NEW YORK

Editors

understood using the terminology and t e c h n i q u e s o f c o m b i n a t o r i c s . We also r e l a t e a few o f t h e s e i d e a s w i t h practical e n d g a m e t e c h n i q u e ( s e e D i a g r a m s lff., 10, 11). The l a t t e r h a l f o f t h e a r t i c l e s h o w s s o m e r e m a r k a b l e c h e s s p r o b l e m s feat u r i n g t h e k n i g h t or knights. Most "practical" c h e s s p l a y e r s h a v e little pat i e n c e for t h e a r t o f c h e s s p r o b l e m s , w h i c h h a s e v o l v e d a long w a y from its origins in i n s t r u c t i v e e x e r c i s e s . But the same formal concerns that may deter t h e o v e r - t h e - b o a r d p l a y e r give s o m e p r o b l e m s a p a r t i c u l a r a p p e a l to mathe m a t i c i a n s . F o r i n s t a n c e , w e will exhibit a position, constructed by P. O ' S h e a a n d p u b l i s h e d in 1989, w h e r e White, with o n l y king a n d knight, h a s j u s t o n e w a y to f o r c e m a t e in 48 (the c u r r e n t r e c o r d ) . We a l s o s h o w the l o n g e s t k n o w n legal g a m e o f c h e s s that is d e t e r m i n e d c o m p l e t e l y b y its last m o v e ( d i s c o v e r e d b y R 0 s l e r in 1 9 9 4 ) w h i c h h a p p e n s to b e c h e c k m a t e b y p r o m o t i o n to a knight. Algebraic notation We a s s u m e t h a t the r e a d e r is familiar w i t h t h e r u l e s o f chess, b u t w e a s s u m e v e r y little k n o w l e d g e of c h e s s strategy. (The r e a d e r w h o k n o w s , o r is willing to a c c e p t a s intuitively obvious, that king a n d q u e e n win a g a i n s t king, o r e v e n a g a i n s t king a n d k n i g h t if t h e r e is no i m m e d i a t e draw, will have n o difficulty f o l l o w i n g the analysis.) The r e a d e r will, h o w e v e r , h a v e to follow t h e n o t a t i o n for c h e s s m o v e s , e i t h e r b y visualizing t h e m o v e s o n t h e d i a g r a m o r b y s e t t i n g up the p o s i t i o n on the b o a r d . S e v e r a l n o t a t i o n s y s t e m s have b e e n used; t h e m o s t c o m m o n one n o w a d a y s , a n d t h e one w e u s e here, is " a l g e b r a i c n o t a t i o n , " so c a l l e d b e c a u s e o f t h e c o o r d i n a t e s y s t e m u s e d to n a m e t h e s q u a r e s o f t h e b o a r d . In the rem a i n i n g p a r a g r a p h s of this i n t r o d u c t o r y s e c t i o n w e outline this n o t a t i o n s y s t e m . R e a d e r s a l r e a d y fluent in algeb r a i c n o t a t i o n m a y safely s k i p to the n e x t section, A C h e s s E n d g a m e .

!

Each s q u a r e o n the 8 x 8 b o a r d is uniquely d e t e r m i n e d b y its r o w and c o l u m n , called "rank" a n d "file" respectively. The r a n k s are n u m b e r e d from 1 to 8, the files n a m e d b y letters a t h r o u g h h. In the initial array, r a n k s 1 a n d 2 are o c c u p i e d b y White's pieces a n d pawns, r a n k s 8 a n d 7 b y Black's; b o t h q u e e n s are o n the d-file, a n d both kings on the e-file. Thus, v i e w e d from w h i t e ' s side of the b o a r d (as are all the diagrams in this article), the r a n k s are n u m b e r e d front b o t t o m to top, the files from left to right. We n a m e a square by its c o l u m n followed b y the row; for instance, the White king in Diagram 1 below is at d2. E a c h of the six kinds of c h e s s m e n is r e f e r r e d to b y a single letter, usually its initial: K, Q, R, B, P are king, queen, rook, bishop, a n d p a w n (often l o w e r c a s e p is s e e n for pawn). We c a n n o t use the initial letter for the knight b e c a u s e K is a l r e a d y the king, so we use its p h o n e t i c initial, N for kNight. F o r i n s t a n c e , D i a g r a m 1 c a n be described as: White Kd2, Black Kal, Nf2, Pa2, Pc2. To n o t a t e a c h e s s m o v e we n a m e the piece a n d its d e s t i n a t i o n square, interpolating " x " if the m o v e is a capture. F o r p a w n m o v e s the P is u s u a l l y suppressed; for p a w n captures, it is replaced by the p a w n ' s file. T h u s in Diagrain 11, B l a c k ' s p a w n m o v e s are n o t a t e d a2 a n d a • b2 r a t h e r t h a n Pa2 a n d P • b2. We follow a m o v e b y "+" if it gives check, a n d b y 'T' or "?" if we regard it as p a r t i c u l a r l y s t r o n g or weak. In some cases 'T' is u s e d to indicate a thematic move, i.e., a m o v e that is essential to the "theme" or m a i n p o i n t of the problem. As a n aid to following the analysis, moves are n u m b e r e d consecutively, from the start of the g a m e or from the diagram. F o r i n s t a n c e , w e shall begin the d i s c u s s i o n of D i a g r a m 1 b y considering the p o s s i b i l i t y 1.KXc2 Nd3!. Here "1" i n d i c a t e s that t h e s e are White's a n d B l a c k ' s first m o v e s from the diagram; "K• m e a n s that the White king c a p t u r e s the u n i t o n c2; a n d "Nd3!" m e a n s t h a t the Black knight moves to the u n o c c u p i e d square d3, and that this is r e g a r d e d as a strong move (the p o i n t here b e i n g that Black p r e v e n t s 2.Kcl e v e n at the cost of letting White c a p t u r e the knight), w h e n

analysis begins with a Black move, we use " . . . " to r e p r e s e n t the p r e v i o u s White move; thus "1 . . . Nd3!" is the same first Black move. A few further r e f i n e m e n t s are n e e d e d to s u b s u m e p r o m o t i o n a n d castling, a n d to e n s u r e that every m o v e is uniquely specified by its notation. For instance, if Black w e r e to m o v e first in Diagram 1 a n d p r o m o t e d his c2p a w n to a q u e e n (giving check), we w o u l d write this as 1 . . . c l Q + , or m o r e likely 1 . . . c l Q + ? , b e c a u s e we shall see that after 2 . K x c l White c a n draw. Short a n d long castling are n o t a t e d 0-0 a n d 0-0-0 respectively. If the piece a n d d e s t i n a t i o n square do n o t specify the move uniquely, w e also give the dep a r t u r e square's file, rank, or both. A n e x t r e m e example: Starting from Diagram 9, "Nbl" u n i q u e l y specifies a move of the c3 knight. But to m o v e it to d5 we would w r i t e "Ncdh" ( b e c a u s e other knights on the b- a n d f-files could also r e a c h dh); to a4, "N3a4" (not "Nca4" b e c a u s e of the knight o n c5); a n d to e4, "Nc3e4" (why?). A Chess

n a t u r a l try is 1.KXc2, e l i m i n a t i n g o n e p a w n a n d i m p r i s o n i n g two of B l a c k ' s r e m a i n i n g t h r e e m e n in the c o r n e r . But 1 . . . Nd3! b r e a k s the b l o c k a d e (Diag r a m 2a). Black t h r e a t e n s n o t h i n g b u t c o n t r o l s the key square el. The rules of c h e s s do n o t allow White to p a s s the move; u n a b l e to go to el, the king m u s t move elsewhere and release Black's m e n . After 2.K• d3 (or a n y o t h e r m o v e ) K b l followed by 3 . . . alQ, B l a c k w i n s easily. Diagram 2a

Endgame

We begin by analyzing a relatively simple chess p o s i t i o n (Diagram 1). This may look like an e n d g a m e from actual play, b u t is a c o m p o s e d p o s i t i o n - - a n "endgame s t u d y " - - c r e a t e d (by NDE) to bring the key p o i n t into s h a r p e r focus.

Diagram 2b

Diagram 1

White to move

White, r e d u c e d to bare king, c a n do n o better t h a n draw, a n d e v e n that with difficulty: Black will surely w i n if either p a w n safely p r o m o t e s to a queen. A

R e t u r n i n g to Diagram 1, let us try ins t e a d 1.Kcl! This still locks in the Black K a l a n d Pa2, a n d p r e p a r e s to c a p t u r e the Pc2 n e x t move, for i n s t a n c e 1 . . . N d 3 + 2.K• arriving at D i a g r a m 2a w i t h Black to move. White h a s in effect s u c c e e d e d in p a s s i n g the m o v e to Black b y t a k i n g a d e t o u r f r o m d2 to c2. N o w it is Black w h o c a n n o t pass, a n d a n y m o v e r e s t o r e s the White king's access to el. F o r instance, play m a y cont i n u e 2 . . . N b 4 + 3.Kcl, r e a c h i n g Diag r a m 2b. Black is still b o t t l e d up. If it

VOLUME 25, NUMBER 1, 2003

23

w e r e White to m o v e in D i a g r a m 2b, White w o u l d h a v e to r e l e a s e B l a c k w i t h K d l o r Kd2 a n d lose; b u t a g a i n B l a c k m u s t m o v e a n d a l l o w W h i t e b a c k to c2, f o r i n s t a n c e 3 . . . N d 3 + 4.Kc2 a n d w e a r e b a c k at D i a g r a m 2a. So w h i t e d o e s d r a w - - a t l e a s t if B l a c k obligingly s h u t t l e s t h e k n i g h t bet w e e n d3 a n d b4 to m a t c h t h e w h i t e king's o s c i l l a t i o n s b e t w e e n c l a n d c2. But w h a t if B l a c k t r i e s to i m p r o v e on this? While t h e king is l i m i t e d to t h o s e t w o squares, t h e k n i g h t c a n r o a m o v e r a l m o s t the e n t i r e b o a r d . F o r i n s t a n c e , f r o m D i a g r a m 2a B l a c k m i g h t b r i n g t h e k n i g h t to t h e far c o r n e r in m m o v e s , reaching a position such as Diagram 3a, a n d t h e n b a c k to d3 in n m o v e s . If m + n is odd, t h e n B l a c k will w i n s i n c e it will b e W h i t e ' s t u r n to m o v e . I n s t e a d o f d3, B l a c k c a n a i m for b3 o r e2, w h i c h a l s o c o n t r o l c l ; b u t e a c h o f t h e s e is t w o k n i g h t m o v e s a w a y f r o m d3, s o w e get a n equivalent p a r i t y c o n d i t i o n . Alternatively, B l a c k m i g h t t r y to r e a c h b4 f r o m d3 in a n even n u m b e r o f m o v e s , Diagram 3a

to r e a c h D i a g r a m 2b with White to move; a n d again Black c o u l d aim for a n o t h e r s q u a r e t h a t c o n t r o l s c2. But e a c h of t h e s e s q u a r e s is one o r t h r e e knight m o v e s a w a y from d3, so again w o u l d yield a c l o s e d p a t h of o d d length t h r o u g h d3. Can B l a c k thus p a s s the m o v e b a c k to White? F o r that matter, w h a t s h o u l d White do in Diagram 3b? D o e s either Kcl or K• draw, o r is White lost reg a r d l e s s o f this c h o i c e ? The o u t c o m e of D i a g r a m 2a thus h i n g e s on t h e a n s w e r to the following p r o b l e m in g r a p h theory: Let ~5 = ~s,s be the graph whose vertices are the 64 squares of the 8 • 8 chessboard and whose edges are the p a i r s of squares j o i n e d by a knight's move. Does ~ have a cycle of odd length through d3? L i k e w i s e W h i t e ' s initial m o v e in Diag r a m 3b a n d the o u t c o m e of this e n d g a m e c o m e s d o w n to the r e l a t e d q u e s t i o n c o n c e r n i n g the s a m e g r a p h ~5: What are the possible parities of lengths of paths on ~ f r o m h8 to c l or c2? The a n s w e r s result f r o m the following b a s i c p r o p e r t i e s o f ~5:

~///////z

t h e s a m e c o l o r a s the o n e o c c u p i e d b y t h e knight. REMARK. O u r a n a l y s i s w o u l d r e a c h t h e s a m e c o n c l u s i o n s if the B l a c k p a w n on c2 w e r e r e m o v e d f r o m D i a g r a m s 1 a n d 3b; w e i n c l u d e d this s u p e r f l u o u s p a w n o n l y a s b a i t to m a k e the w r o n g c h o i c e o f c2 m o r e t e m p t i n g . P u z z l e 1. F o r w h i c h rectangular b o a r d s (if a n y ) d o e s p a r t (i) o r (ii) of t h e L e m m a fail? T h a t is, w h i c h ~5~,,,~a r e n o t c o n n e c t e d , o r n o t b i p a r t i t e ? (All puzzles a n d all d i a g r a m s n o t e x p l i c a t e d in t h e t e x t h a v e s o l u t i o n s at the e n d o f this article.) Knight's Tours and the Thirty-Two Knights

The g r a p h ~5 a r i s e s often in p r o b l e m s a n d p u z z l e s involving knights. F o r ins t a n c e , t h e p e r e n n i a l knight's t o u r puzzle a s k s in effect for a H a m i l t o n i a n p a t h o n ~5; a "re-entrant" or "closed" k n i g h t ' s t o u r is j u s t a H a m i l t o n i a n circuit. T h e e x i s t e n c e of s u c h t o u r s is classical--even Euler spent some time c o n s t r u c t i n g t h e m , finding a m o n g others t h e e l e g a n t c e n t r a l l y s y m m e t r i c t o u r i l l u s t r a t e d in Diagram 4 ( f r o m [9, p. 191]):

LEMMA. (i) The graph ~ is connected. ( i i ) The graph is bipartite, the two parts c o m p r i s i n g the 32 light squares and 32 dark squares of the chessboard.

Diagram 3b

COROLLARIES. (1) There are no knight cycles o f odd length on the chessboard. (2) Two squares of the s a m e color are connected by knight-move paths oj even length but not of odd length; two squares o f opposite color are connected by knight-move paths of odd length but not by paths of even length.

% White to move

24.

Proof'. P a r t (i) is j u s t the familiar fact t h a t a k n i g h t can get f r o m a n y square on t h e c h e s s b o a r d to a n y o t h e r square. P a r t (ii) a m o u n t s to the o b s e r v a t i o n t h a t e v e r y k n i g h t m o v e c o n n e c t s a light a n d a d a r k square.

THE MATHEMATICALINTELLIGENCER

We t h u s a n s w e r o u r c h e s s questions: White d r a w s b o t h D i a g r a m 1 a n d D i a g r a m 3b b y starting with K c l . More generally, f o r any initial p o s i t i o n of t h e B l a c k knight, White c h o o s e s b e t w e e n c l a n d c2 b y m o v i n g to the square o f

Diagram 4

I

Y/

A closed knight's tour constructed by Euler

T h e e x t e n s i v e l i t e r a t u r e on knight's t o u r s i n c l u d e s m a n y e x a m p l e s , which, w h e n n u m b e r e d along the p a t h f r o m 1 to 64, y i e l d s e m i - m a g i c squares (all r o w a n d c o l u m n s u m s equal 260), s o m e t i m e s w i t h f u r t h e r "magic" p r o p e r t i e s , b u t it is n o t y e t k n o w n w h e t h e r a fully m a g i c k n i g h t ' s t o u r (one with m a j o r dia g o n a l s a s w e l l a s r o w s and c o l u m n s

s u m m i n g to 260), either o p e n or closed, c a n exist. More generally, we m a y ask for H a m i l t o n i a n circuits o n %~,,, for other m , n ; that is, for closed k n i g h t ' s t o u r s on other r e c t a n g u l a r c h e s s b o a r d s . A n e c e s s a r y c o n d i t i o n is that ~,,,,, be a c o n n e c t e d graph with a n e v e n n u m b e r of vertices. H e n c e we m u s t have 2Jmn a n d b o t h m , n at least 3 (cf. Puzzle 1). But n o t all %,,n satisfying this condition admit H a m i l t o n i a n circuits. F o r instance, one easily c h e c k s that ~J3,4 is n o t Hamiltonian. Nor are ~ , 6 a n d ~5~,s, b u t ~g~,J0 has a H a m i l t o n i a n circuit, as does G3,,~ for each e v e n n > 10. F o r instance, Diagram 5 s h o w s a closed knight's tour o n the 3 • 10 board:

set of more than at least three squares must include two of the san~e color. Cocliques are more interesting: how m a n y pairwise nonattacking knights c a n the chessboard a c c o m m o d a t e ? ~ We follow Golomb ([21], via M. G a r d n e r [9, p. 193]). Again the fact that c~ is bipartite suggests the a n s w e r (Diagram 6): Diagram 6

Diagram 5

32 mutually nonattacking knights A closed knight's tour on the 3 x 10 board

There are s i x t e e n s u c h t o u r s (ignoring the b o a r d s y m m e t r i e s ) . More generally, e n u m e r a t i n g the closed knight's t o u r s on a 3 X (8 + 2n) b o a r d yields a s e q u e n c e 16, 176, 1536, 15424, . . . satisfying a c o n s t a n t l i n e a r r e c u r s i o n of degree 21 that was o b t a i n e d i n d e p e n d e n t l y by Donald K n u t h a n d NDE in April 1994. See [23, S e q u e n c e A070030]. In 1997, B r e n d a n McKay first comp u t e d that there are 13267364410532 ( m o r e than 1.3 x 10 t3) closed knight's tours o n the 8 • 8 b o a r d ([19]; see also [23, Sequence A001230], [26]). We r e t u r n n o w f r o m e n u m e r a t i o n to existence. After c~,},,~ the n e x t case is ~54,,~. This is tricMer: the r e a d e r might try to c o n s t r u c t a closed k n i g h t ' s t o u r o n a 4 • 11 board, or to p r o v e that n o n e exists. We a n s w e r this q u e s t i o n later. What of maximal cliques a n d cocliques on q3? A clique is j u s t a collection of pairwise defending (or attacking) knights. Clearly there c a n be n o more than two knights, again b e c a u s e ~5 is bipartite: two squares of the same color c a n n o t be a knight's move apart, a n d any

Diagram 7

P u z z l e 2. What h a p p e n s if m , n are b o t h odd, or if m --< 2 or n --< 2? Are Diagram 6 a n d its c o m p l e m e n t the only m a x i m a l cocliques? Yes, b u t this is h a r d e r to show. One elegant proof, given by G r e e n b e r g in [21], i n v o k e s the e x i s t e n c e of a closed knight's tour, such as E u l e r ' s Diagram 4. In general, o n a circuit o f l e n g t h 2M the only sets of M p a i r w i s e n o n a d j a c e n t vertices are the set of e v e n - n u m b e r e d vertices a n d the set of o d d - n u m b e r e d ones o n the circuit. Here M = 32, a n d the knight's t o u r in effect e m b e d s that circuit into (6, so a f o r t i o r i t h e r e c a n be at m o s t two cocliques of size M o n ~5--and we have a l r e a d y f o u n d t h e m both! Of course this p r o o f applies equally to any b o a r d with a closed knight's tour: on any s u c h b o a r d the light- and darksquared s u b s e t s are the only maximal cocliques. Conversely, a b o a r d for which there are further m a x i m a l cocliques cannot s u p p o r t a closed knight's tour. For example, any 4 x n b o a r d has a nfixedcolor m a x n u a l coclique, as illustrated for n = 11 in Diagram 8. Diagram 8

N A third maximal knight coclique on the 4 x 11 board

A one-factor in

It is n o t hard to see that we c a n n o t do better: the 64 s q u a r e s m a y b e partitioned into 32 pairs, e a c h related b y a knight move, a n d t h e n at m o s t o n e square from each p a i r c a n be u s e d (Diagram 7). This is P a t e n a u d e ' s s o l u t i o n in [21]. Such a p a i r i n g of c9 is called a "one-factor" in g r a p h theory. Similar one-factors exist o n all ~3m,,~w h e n 21ran and m , n both e x c e e d 2; they c a n be used to show that in g e n e r a l a knight coclique o n an m • n b o a r d has size at most ran~2 for s u c h m , n .

This yields p o s s i b l y the c l e a n e s t p r o o f that there is no closed knight's tour on a 4 • n board f o r a n y n. (According to Jelliss [14], this fact was k n o w n to E u l e r a n d first p r o v e d by C. Flye Sainte-Marie in 1877; Jelliss attributes the a b o v e c l e a n p r o o f to Louis Posa.) WARNING: the e x i s t e n c e of a closed knight's t o u r is a sufficient b u t n o t necessary c o n d i t i o n for the existence of only t w o m a x i m a l knight cocliques. It is k n o w n that a n m x n b o a r d s u p p o r t s a closed t o u r if a n d only if its area i n n is a n e v e n i n t e g e r > 24 a n d n e i t h e r m n o r n is 1, 2, or 4. In particular, as n o t e d a b o v e t h e r e are n o closed knight's

~Burt Hochberg jokes (in [11, p. 5], concerning the analogous problem for queens) that the answer is 64, all White pieces or all Black: pieces of the same color cannot attack each other! Of course this joke, and similar jokes such as crowding several pieces on a single square, are extraneous to our analysis.

VOLUME 25, NUMBER 1 2003

25

tours on the 3 • 6 and 3 x 8 boards, t h o u g h a s it h a p p e n s o n e a c h o f t h e s e b o a r d s t h e o n l y m a x i m a l k n i g h t cocliques a r e t h e t w o o b v i o u s m o n o c h r o m a t i c ones.

More about ~: Domination Number, Girth, and the Knight Metric A n o t h e r c l a s s i c puzzle asks: H o w m a n y k n i g h t s d o e s it t a k e to e i t h e r o c c u p y o r d e f e n d e v e r y s q u a r e o n the b o a r d ? In g r a p h t h e o r y p a r l a n c e this a s k s for t h e " d o m i n a t i o n n u m b e r " o f <6.2 F o r t h e standard 8 • 8 board, the symmetrical s o l u t i o n w i t h 12 k n i g h t s ( D i a g r a m 9) h a s long b e e n k n o w n :

We a l r e a d y n o t e d that ~5, b e i n g bipartite, h a s no c y c l e s of o d d length. (We a l s o e n c o u n t e r e d the n o n e x i s t e n c e o f 3-cycles as "~5 has no cliques o f size 3".) Thus the girth (minimal cycle l e n g t h ) o f ~5 is at least 4. In fact t h e girth is e x a c t l y 4, as s h o w n for i n s t a n c e in D i a g r a m 10.

p a w n a n d giving White t i m e for 4.N x a2 a n d a draw. On o t h e r B l a c k m o v e s f r o m D i a g r a m 10a White r e s u m e s control o f a2 w i t h 3.Ncl o r 3.Nb4; for ins t a n c e 2 . . . Kc2 3.Nb4+ o r 2 . . . Kc3 3 . N c l Kb2 (else N a 2 + ) 4 . N d 3 + ! etc. N o t e t h a t the White king w a s n o t needed.

Diagram 10

NOTE TO ADVANCED CHESS PLAYERS: it might seem that the knight does need a bit o f h e l p after 1.Nb4 ICol!?, w h e n e i t h e r 2.Na2? o r 2.Nd3? l o s e s (in t h e l a t t e r c a s e to 2 . . . a2), b u t B l a c k h a s no t h r e a t so White can s i m p l y m a k e a r a n d o m ("waiting") king move. But this is n o t n e c e s s a r y , as W h i t e c o u l d also d r a w b y thinking (and p l a y i n g ) o u t o f t h e a2-b4-d3-cl-a2 box: 1.Nb4 K b l 2.Nd5! If n o w 2 . . . a2 t h e n 3 . N c 3 + is a n e w d r a w i n g fork, a n d o t h e r w i s e White p l a y s 3.Nb4 a n d r e s u m e s the s q u a r e dance.

White to move draws

P u z z l e 5. C o n s t r u c t a p o s i t i o n w h e r e this Nd5 r e s o u r c e is W h i t e ' s o n l y w a y to draw.

Diagram 9

Diagram 10a

All unoccupied squares controlled

P u z z l e 3. P r o v e t h a t this s o l u t i o n is unique u p to reflection. T h e k n i g h t d o m i n a t i o n n u m b e r for c h e s s b o a r d s o f a r b i t r a r y size is n o t k n o w n , n o t e v e n a s y m p t o t i c a l l y . See [9, Ch. 14] for r e s u l t s k n o w n at t h e t i m e for s q u a r e b o a r d s o f o r d e r up to 15, m o s t d a t i n g b a c k to 1918 [1, Vol. 2, p. 359]. If w e a s k i n s t e a d t h a t e v e r y square, o c c u p i e d o r not, be d e f e n d e d , t h e n t h e 8 • 8 c h e s s b o a r d r e q u i r e s 14 knights. On a n m • n b o a r d , at l e a s t mn/8 knights are needed, since a k n i g h t d e f e n d s at m o s t 8 squares. P u z z l e 4. P r o v e t h a t m n / 8 + O ( m + n ) k n i g h t s suffice. HINT: T r e a t t h e light and dark squares separately.

% After 2 Nd3!

This s q u a r e cycle is i m p o r t a n t to e n d g a m e theory: a White knight traveling o n t h e cycle c a n p r e v e n t the p r o m o t i o n o f t h e Black p a w n on a3 supp o r t e d b y its king. To d r a w this p o s i t i o n White m u s t either b l o c k t h e p a w n o r c a p t u r e it, even at the c o s t o f t h e knight. The p o i n t is s e e n a f t e r l . N b 4 Kb3 2.Nd3! (reaching D i a g r a m 10a) a2 3 . N c l + ! , "forking" king a n d

WARNING: This puzzle is h a r d a n d requires c o n s i d e r a b l y m o r e c h e s s b a c k g r o u n d t h a n anything else in this article. The c o n s t r u c t i o n r e q u i r e s s o m e delicacy: it is n o t e n o u g h to s i m p l y s t a l e m a t e t h e White king, b e c a u s e t h e n White c a n p l a y 2.Na2 w i t h impunity; o n t h e o t h e r h a n d if the White king is p u t in Z u g z w a n g (so that it h a s s o m e legal m o v e s , b u t all o f t h e m lose), t h e n t h e d i r e c t 1 . . . a2 2 . N x a 2 K x a 2 w i n s for Black. Even more important for the pract i c a l c h e s s p l a y e r is t h e d i s t a n c e funct i o n o n .~, w h i c h e n c o d e s t h e n u m b e r of moves a knight needs to get from a n y s q u a r e to a n y other. T h e d i a m e t e r ( m a x i m a l d i s t a n c e ) o n ~ is 6, w h i c h is a t t a i n e d o n l y b y d i a g o n a l l y o p p o s i t e c o r n e r s . This is to b e expected, but shorter distances bring s o m e s u r p r i s e s . The t a b l e a c c o m p a n y i n g D i a g r a m 11 s h o w s t h e d i s t a n c e f r o m e a c h v e r t e x o f ~5 to a c o r n e r square:

2This terminology is not entirely foreign to the chess literature: A piece is said to be "dominated" when it can move to many squares but will be lost on any of them. (The meaning of "many" in this definition is not precise because domination is an artistic concept, not a mathematical one.) The introduction of this term into the chess lexicon is attributed to Henri Rinck ([12, p. 93], [16, p. 151]). The task of constructing economical domination positions, where a few chessmen cover many squares, has a pronounced combinatorial flavor; the great composer of endgame studies G.M. Kasparyan devoted an entire book to the subject, Domination in 2545 Endgame Studies, Progress Publishers, Moscow, 1980.

26

THE MATHEMATICALINTELLIGENCER

5

4

5

4

5

4

5

6

4

3

4

3

4

5

4

5

3

4

3

4

3

4

5

4

2

3

2

3

4

3

4

5

3

2

3 2 3 4 3 4

2

1

4 3 2 3 4 5

3

4*

1

2 3 4 3 4

2

3

2

~

3

3

4

5

Diagram 11

% White loses

The starred entry is due to the board edges: a knight c a n travel from any square to any diagonally adjacent square in two moves except w h e n one of them is a c o m e r square. But the other irregularities of the table at short distances do not depend o n edge effects. Anywhere on the board, it takes the otherwise agile knight three m o v e s to reach an orthogonally a d j a c e n t square, and four moves to travel two squares diagonally. This peculiarity m u s t be a b s o r b e d by any chess player w h o would learn to play with or against knights. One consequence, k n o w n to e n d g a m e theory, is s h o w n in Diagram 11, which exploits both the generic irregularity a n d the special c o m e r case. Even with White to move, this position is a win for Black, who will p l a y . . , a2 a n d . . . alQ. One might expect that the knight is close enough to stop this, b u t in fact it would take it three m o v e s to reach a2 a n d four to reach al, in each case one too many. In fact this knight helps Black by blocking the White king's a p p r o a c h to al!

Diagram 13

P u z z l e 6. D e t e r m i n e the k n i g h t dist a n c e from (0,0) to (re,n) o n a n infinite b o a r d as a f u n c t i o n of the i n t e g e r s m , n . Further

Puzzles

We c o n t i n u e with several m o r e puzzles that exploit or e x t e n d the a b o v e discussion. P u z z l e 7. How does White play in Diagran~ 12 to force c h e c k m a t e as quickly as possible against a n y Black d e f e n s e ? Yes, it's White who wins, despite having only king and p a w n against 15 Black men. Black's m e n are almost paralyzed, with only the q u e e n able to m o v e in its c o m e r prison. White must keep it that way: if he ever m o v e s his king, Black will sacrifice his e2-pawn by p r o m o t i n g it, bring the Black army to life a n d s o o n o v e r w h e h n White. So White m u s t m o v e only the pawn, a n d the piece that it will p r o m o t e to. That's good e n o u g h for a draw, b u t how to actually win? P u z z l e 8. (See Diagram 13.) T h e r e are exactly 24 = 4! p a t h s that a knight o n d l c a n take to reach d7 in four moves; plotting these paths o n the c h e s s b o a r d yields a beautiful p r o j e c t i o n of (the 1s k e l e t o n of) the 4 - d i m e n s i o n a l hypercube! Explain. P u z z l e 9. We saw that there is a n essentially unique m a x i m a l c o n f i g u r a t i o n of 32 m u t u a l l y n o n - d e f e n d i n g k n i g h t s on the 8 x 8 board. i. S u p p o s e we allow each knight to be d e f e n d e d at m o s t once. H o w m a n y m o r e knights c a n the b o a r d t h e n accommodate?

Diagram 12

| White to play and mate as quickly as possible

/

N

The 4! shortest knight paths from dl to d7

ii. Now s u p p o s e we r e q m r e each knight to be d e f e n d e d exactly once. What is the largest n u m b e r of knights o n the 8 x 8 b o a r d satisfying this constraint, a n d w h a t are all the m a x i m a l c o n f i g u r a t i o n s ? P u z z l e 10. A "camel" is a (3,1) leaper, that is, a n u n o r t h o d o x chess p i e c e that m o v e s from (x,y) to one of the s q u a r e s ( x _ + 3 , y _ + l ) or ( x - + l , y + - 3 ) . (A knight is a (2,1) leaper.) B e c a u s e t h e r e are eight such squares, it t a k e s at least mn/8 camels to d e f e n d every square, o c c u p i e d or not, o n an m x n board. Are mn/8 + O(m + n) sufficient, as in Puzzle 4? Synthetic

Games

The r e m a i n d e r of this article is d e v o t e d to c o m p o s e d chess p r o b l e m s f e a t u r i n g knights. A synthetic g a m e [13] is a chess game c o m p o s e d ( r a t h e r t h a n played) to achieve s o m e objective, u s u a l l y in a m i n i m a l n u m b e r of moves. Ideally the s o l u t i o n should be unique, b u t this is very rare. Failing this, we c a n h o p e for a n "almost unique" solution, e.g., o n e w h e r e the final p o s i t i o n is unique, b u t n o t the move order. F o r i n s t a n c e , the s h o r t e s t game e n d i n g in c h e c k m a t e by a knight is 3.0 moves: 1.e3 Nc6 2.Ne2 Nd4 3.g3 Nf3 mate. White c a n vary the o r d e r of his m o v e s a n d c a n play e4 a n d / o r g4 i n s t e a d of e3 a n d g3. The Black knight has t w o p a t h s to f3. The biggest flaw, however, is that White c o u l d play c3/c4 i n s t e a d of g3/g4, a n d Black c o u l d m a t e at d3. At least all 72 s o l u t i o n s share the c e n t r a l f e a t u r e that White i n c a r c e r a t e s his king at its h o m e

VOLUME 25, NUMBER 1, 2003

27

Diagram 14

square. A b e t t e r s y n t h e t i c g a m e involving a k n i g h t is given in Puzzle 11. Puzzle ll. Construct a game of chess in w h i c h B l a c k c h e c k m a t e s White on B l a c k ' s fifth m o v e b y p r o m o t i n g a p a w n to a knight. Proof G a m e s A v e r y s u c c e s s f u l v a r i a t i o n o f synt h e t i c g a m e s t h a t a l l o w s u n i q u e solut i o n s a r e proof games, f o r w h i c h t h e l e n g t h n o f t h e g a m e a n d t h e final p o sition P are specified. For the condit i o n (P,n) to b e c o n s i d e r e d a s o u n d p r o b l e m , t h e r e s h o u l d b e a unique g a m e in n m o v e s e n d i n g in P. ( S o m e t i m e s t h e r e will be m o r e t h a n o n e solution, b u t s o l u t i o n s s h o u l d b e r e l a t e d in s o m e t h e m a t i c way. H e r e w e will o n l y c o n s i d e r c o n d i t i o n s (P,n) t h a t are uniquely realizable, with the exc e p t i o n o f D i a g r a m 17.) The e a r l i e s t p r o o f g a m e s w e r e c o m p o s e d b y t h e f a m o u s "Puzzle King" S a m L o y d in t h e 1890s b u t d i d n o t h a v e unique solutions; t h e e a r l i e s t p r o o f game meeting today's standards seems to have b e e n c o m p o s e d b y T. R. Daws o n in 1913. A l t h o u g h s o m e i n t e r e s t i n g p r o o f g a m e s w e r e c o m p o s e d in s u b s e q u e n t years, the v a s t p o t e n t i a l o f t h e s u b j e c t w a s n o t s u s p e c t e d until t h e fant a s t i c p i o n e e r i n g efforts o f Michel Caill a u d in t h e e a r l y 1980s. A c l o s e to c o m p l e t e c o l l e c t i o n o f all p r o o f g a m e s p u b l i s h e d up to 1991 ( a r o u n d 160 p r o b l e m s ) a p p e a r s in [28]. Let u s c o n s i d e r s o m e p r o o f g a m e s r e l a t e d to knights. We m e n t i o n e d earlier t h a t t h e s h o r t e s t g a m e e n d i n g in m a t e b y knight h a s length 3.0 m o v e s . N o n e o f t h e 72 s o l u t i o n s y i e l d p r o o f g a m e s w i t h unique solutions; i.e., e v e r y terminal position has more than one w a y o f r e a c h i n g it in 3.0 m o v e s . It is t h e r e f o r e n a t u r a l to a s k for t h e l e a s t n u m b e r n ( e i t h e r a n i n t e g e r o r halfi n t e g e r ) for w h i c h t h e r e e x i s t s a uniquely realizable g a m e o f c h e s s in n m o v e s ending w i t h c h e c k m a t e b y knight, i.e., given t h e final p o s i t i o n , t h e r e is a unique g a m e t h a t r e a c h e s it in n m o v e s . Such a g a m e w a s f o u n d ind e p e n d e n t l y b y the t w o a u t h o r s o f this a r t i c l e in 1996 for n = 4.0, w h i c h is s u r e l y t h e m i n i m u m . The final p o s i t i o n is s h o w n in D i a g r a m 14.

28

THE MATHEMATICALINTELLIGENCER

A

Position a f t e r Black's 4th m o v e . How did t h e g a m e go?

Five o t h e r p r o o f game p r o b l e m s involving knights are p r e s e n t e d in Puzzles 12 t h r o u g h 16. The m i n i m u m k n o w n n u m b e r of moves for achieving the game is given in parentheses. (We repeat, the g a m e m u s t b e uniquely realizable from the n u m b e r o f moves a n d final position.)

e a r l i e s t o f all p r o o f g a m e s , while Diag r a m 16 is c o n s i d e r a b l y m o r e challenging. D i a g r a m 17 f e a t u r e s a differe n t k i n d o f i m p o s t o r . N o t e t h a t it h a s t w o solutions; it is r e m a r k a b l e h o w e a c h s o l u t i o n h a s a different i m p o s t o r . The c o m p l e x a n d difficult D i a g r a m 18 i l l u s t r a t e s t h e Frolki~l theme: t h e multiple c a p t u r e o f p r o m o t e d p i e c e s . Diag r a m 19 s h o w s , in the w o r d s o f Wilts a n d F r o l k i n [28, p. 53], t h a t "the s e e m ingly i n d i s p u t a b l e fact t h a t a knight c a n n o t lose a t e m p o is n o t quite unambiguous." P u z z l e 15. C o n s t r u c t a p r o o f g a m e ending w i t h m a t e b y a p a w n p r o m o t i n g to a k n i g h t w i t h o u t a c a p t u r e on the m a t i n g m o v e (6.0). P u z z l e 16. C o n s t r u c t a p r o o f g a m e ending with mate by a pawn promoting to a knight w i t h n o c a p t u r e s b y the mating side t h r o u g h o u t the g a m e (7.0). Diagram 15

P u z z l e 12. C o n s t r u c t a p r o o f g a m e w i t h o u t a n y c a p t u r e s t h a t e n d s with m a t e b y a knight (4.5).

.

P u z z l e 13. Construct a p r o o f g a m e ending w i t h mate b y a knight malting a c a p t u r e (5.5). P u z z l e 14. C o n s t r u c t a p r o o f g a m e ending w i t h mate b y a p a w n p r o m o t i n g to a k n i g h t (5.5). T h e r e is a r e m a r k a b l e v a r i a n t o f Puzzle 14. R a t h e r than having t h e g a m e det e r m i n e d b y its final p o s i t i o n a n d numb e r o f m o v e s , it is i n s t e a d c o m p l e t e l y d e t e r m i n e d by its last m o v e (including the m o v e number)! This is t h e l o n g e s t k n o w n g a m e with this p r o p e r t y .

A f t e r B l a c k ' s 4th. How did t h e g a m e go?

Diagram 16

x

i

P u z z l e 1 4 ' . C o n s t r u c t a g a m e of c h e s s with last m o v e 6 . g x f 8 N mate. The a b o v e p r o o f g a m e s f o c u s on a c h i e v i n g s o m e o b j e c t i v e in the minim u m n u m b e r o f moves. Many o t h e r p r o o f g a m e s in w h i c h knights p l a y a k e y role h a v e b e e n c o m p o s e d , of w h i c h w e give a s a m p l e o f five p r o b l e m s . Dia g r a m s 15, 16, a n d 17 f e a t u r e "impostors"--some piece(s) are not what they seem. The first of t h e s e ( D i a g r a m 15) is a c l a s s i c p r o b l e m t h a t is o n e o f t h e

A f t e r B l a c k ' s 12th. How did t h e g a m e go?

Diagram 17

Diagram 20

! i

After White's 13th. How did the game go?

N

NAN

s h o u l d b e dual-free, w h i c h m e a n s t h a t B l a c k h a s at l e a s t one m e t h o d o f def e n d i n g w h i c h f o r c e s e a c h White m o v e u n i q u e l y if White is to a c h i e v e his objective. The o b j e c t i v e of c h e c k m a t e c a n b e c o m b i n e d with o t h e r conditions, s u c h a s White having o n l y o n e unit b e s i d e s his king. The i n g e n i o u s Dia g r a m 21 s h o w s t h e c u r r e n t r e c o r d for a "knight minimal," i.e., W h i t e ' s o n l y unit b e s i d e s his king is a knight. F o r o t h e r l e n g t h r e c o r d s , as well as m a n y o t h e r t a s k s a n d r e c o r d s , s e e [20]. Diagram 21

Mate in one

Two solutions! Diagram 18

~y///>.-

After White's 27th move. How did the game go?

h i s t o r y of the game. It is only a s s u m e d that the p r i o r p l a y is legal; n o a s s u m p tion is m a d e that t h e p l a y is "sensible." P r o o f g a m e s are a s p e c i a l class o f r e t r o p r o b l e m s . We will give only o n e illust r a t i o n h e r e of a r e t r o p r o b l e m t h a t is n o t a p r o o f game. It is b a s e d on cons i d e r a t i o n s of parity, a c o m m o n t h e m e w h e n e v e r knights a r e involved. Diag r a m 20 is a mate i n one. A c h e s s p r o b lem with this s t i p u l a t i o n a l m o s t invariably involves an e l e m e n t o f r e t r o g r a d e analysis, such as d e t e r m i n i n g w h o h a s the move. In a p r o b l e m w i t h t h e stipulation "Mate in n," it is a s s u m e d t h a t w h i t e m o v e s first u n l e s s it c a n b e p r o v e d that B l a c k h a s t h e m o v e in ord e r for the p o s i t i o n to b e legal.

Diagram 19 Length Records

XJ A

After Black's 10th move. How did the game go? Retrograde

Analysis

In r e t r o g r a d e a n a l y s i s p r o b l e m s (called retry problems for s h o r t ) , it is n e c e s s a r y to d e d u c e i n f o r m a t i o n f r o m the current position concerning the prior

In length r e c o r d s , o n e t r i e s to cons t r u c t a p o s i t i o n t h a t m a x i m i z e s the n u m b e r o f m o v e s t h a t m u s t e l a p s e before a c e r t a i n o b j e c t i v e is satisfied. The m o s t o b v i o u s a n d m o s t - s t u d i e d objective is c h e c k m a t e . In o t h e r w o r d s , h o w large c a n n be in a p r o b l e m w i t h the o b j e c t i v e "mate in n" (i.e., White to p l a y and c h e c k m a t e B l a c k in n m o v e s ) ? Chess p r o b l e m s t a n d a r d s d e m a n d t h a t the s o l u t i o n s h o u l d b e unique if at all possible. It is t o o m u c h to e x p e c t , esp e c i a l l y for long-range p r o b l e m s , t h a t White has a unique r e s p o n s e to every Black m o v e for W h i t e to a c h i e v e his objective. In o t h e r w o r d s , it is p o s s i b l e for Black to d e f e n d p o o r l y a n d a l l o w w h i t e to achieve his o b j e c t i v e in m o r e t h a n one way, o r e v e n to a c h i e v e it earlier t h a n specified. T h e c o r r e c t uniquen e s s c o n d i t i o n is t h a t t h e p r o b l e m

Mate in 48 Paradox

The term "paradox" has several meanings in b o t h m a t h e m a t i c s a n d o r d i n a r y d i s c o u r s e . We will r e g a r d a f e a t u r e o f a c h e s s p r o b l e m (or c h e s s g a m e ) as p a r a d o x i c a l if it is s e e m i n g l y o p p o s e d to c o m m o n sense. F o r instance, c o m m o n s e n s e tells us that a m a t e r i a l adv a n t a g e is b e n e f i c i a l in w i n n i n g a c h e s s g a m e o r m a t i n g quickly. Thus sacrifice in a n o r t h o d o x c h e s s p r o b l e m (i.e., a d i r e c t m a t e o r s t u d y ) is p a r a d o x i c a l . Of c o u r s e it is j u s t this p a r a d o x i c a l elem e n t t h a t e x p l a i n s t h e a p p e a l o f a sacrifice. A n o t h e r c o m m o n p a r a d o x i c a l t h e m e is u n d e r p r o m o t i o n . Why n o t promote to the strongest possible p i e c e , n a m e l y , t h e queen? This t h e m e is r e l a t e d t o t h a t o f sacrifice, b e c a u s e in e a c h c a s e t h e p l a y e r is forgoing material. To b e sure, u n d e r p r o m o t i o n to k n i g h t in o r d e r to win, draw, o r c h e c k m a t e q u i c k l y is n o t so s u r p r i s i n g ( a n d h a s e v e n o c c u r r e d a fair n u m b e r o f t i m e s in g a m e s ) , s i n c e a k n i g h t c a n m a k e m o v e s f o r b i d d e n to a queen. Tim K r a b b d t h u s r e m a r k s in [15] t h a t

VOLUME 25, NUMBER 1, 2003

29

knighting hardly counts as a true "underpromotion. "3 Nevertheless, knight promotions can be used for surprising purposes that heighten the paradoxical effect. Diagram 22 shows four knight sacririces, all promoted pawns, with a total of five promotions to knight. Diagram 23 shows a celebrated problem composed by Sam Loyd where a pawn promotes to a knight that threatens no pieces or checks and is hopelessly out of play. For some interesting comments by Loyd on this problem, see [27, p. 403]. Diagram 22

N

N|174

other knights. Similarly the time-wasting 5.hXg8N 6.Nh6 7.Nxf7 of Diagram 19 seems paradoxical--why not save a move by 5.hxgSB and 6.bxf7+? Helpmate

In a helpmate in n moves, Black moves first and cooperates with White so that White mates Black on White's nth move. If the number of solutions of a helpmate is not specified, then there should be a unique solution. For a long time it was thought impossible to construct a sound helpmate with the theme of Diagram 24, featuring knight promotions. Note that the first obstacle to overcome is the avoidance of checkmating White or stalemating Black. The composer of this brilliant problem, Gabor Cseh, was tragically killed in an accident in 2001 at the age of 26. Diagram 24

solution to #341] and called the method of "buttons and strings," is to form a graph whose vertices are the squares of the board, with an edge between two vertices if the problem piece (here a knight) can move from one vertex to the other. For Diagram 25, the graph is just an eight-cycle (with an irrelevant isolated vertex corresponding to the center square of the board). Diagranl 26 is a representation of the problem that makes it quite easy to see that the minimum number of moves is sixteen (eight by each color), achieved for instance by cyclically moving each knight four steps clockwise around the eight-cycle. If a White knight is added at b l and a Black knight at b3, then somewhat paradoxically the minimum number of moves is reduced to eight! A variation of the stipulation of Diagram 25 is the problem presented as Puzzle 17, whose solution is a bit tricky and essentially unique. Diagram 25

White to play and win Diagram 23

Exchange the knights in a minimum number

t

of moves Diagram 26

a2

:~

Helpmate in 10

Mate in 3

Note that the impostors of Diagrams 15-17 may also be regarded as paradoxical, because we're trying to reach the position as quickly as possible, and it seems a waste of time to move knights into the original square(s) of

Piece Shuffle In piece shuffles or permutation tasks, a rearrangement of pieces is to be achieved in a minimum number of moves, sometimes subject to special conditions. They may be regarded as special cases of "moving counter problems" such as given in [2, pp. 769-777] or [3, pp. 58-68]. A classic example involving knights, going back to Guarini in 1512, is shown in Diagram 25. The knights are to exchange places in the mininmm number of moves. (Each White knight ends up where a Black knight begins, and vice versa.) The systematic method for doing such problems, first enunciated by Dudeney [3,

3More paradoxical are underpromotions to rooks and bishops, but we will not be concerned with them here.

30

THE MATHEMATICAL INTELLIGENCER

b3 ~ L

~-~

'~2

a3

The graph corresponding to Diagram 25

P u z z l e 17. In Diagram 25 exchange the knights in a minimum number of move sequences, where a "move sequence" is an unlimited number of consecutive moves by the same knight. For some more sophisticated problems similar to Diagram 25, see [10, pp. 114-124]. The most interesting piece

shuffle p r o b l e m s c o n n e c t e d with the g a m e of chess (though n o t f o c u s i n g o n k n i g h t s ) are d u e to G. F o s t e r [5, 6, 7, 8], c r e a t e d with the help of his comp u t e r p r o g r a m WOMBAT (Work Out Matrix By Algorithmic Techniques). Puzzle Answers, and Solutions

Hints,

1. The graph ~m,~ is connected for m = n = 1 (only one v e r t e x ) a n d n o t c o n n e c t e d for m = n = 3 (the c e n t r a l square is an isolated vertex). With t h o s e two exceptions, ~m,n is c o n n e c t e d if a n d only if m > 2 a n d n > 2. Every ~Sm,, is bipartite, e x c e p t ~1,1 ( e m p t y parts n o t allowed); each n o n - c o n n e c t e d graph ~,,,,, is bipartite in several ways e x c e p t for q~l,2 = q~2,1. 2. If m = l o r n = l t h e n ~Jm,. is disc o n n e c t e d , so the m a x i m a l coclique is the set of all m n vertices. The graph ~J2,. (or ~J,~,2) decomp o s e s into two p a t h s of length Ln/2J a n d two of length F:n/2]. It thus has a one-factor if a n d only if 4in , a n d o t h e r w i s e has cocliques of size > n ; the m a x i m a l coclique size i s n + 6 w h e r e 6 E {0, 1, 2} a n d n --+ ~ rood 4. If m a n d n are odd integers g r e a t e r t h a n 1 t h e n the maximal coclique size of ~Sm,,, is (ran + 1)/2, a t t a i n e d by p l a c i n g a knight o n each square of the s a m e parity as a c o m e r square of a n m • n board. One c a n prove that this is m a x i m a l by deleting o n e of these squares a n d c o n s t r u c t i n g a onefactor o n the r e m a i n i n g m n - 1 vertices of ~.,,,,. 3. Each of the four 2 x 2 c o m e r subb o a r d s requires at least three knights, a n d n o single knight m a y o c c u p y or d e f e n d s q u a r e s in two different s u b b o a r d s . H e n c e at least 4 93 = 12 knights are n e e d e d . F o r three k n i g h t s to cover the {al, b l , a2, b2} s u b b o a r d , one of t h e m m u s t be on c3; likewise if3, f6, c6 m u s t be o c c u p i e d if 12 k n i g h t s are to suffice. It is n o w easy to verify that Diagram 9 a n d its r e f l e c t i o n are the only ways to place the r e m a i n i n g 8 knights so as to c o v e r the entire chessboard. 4. ([3, #319, p. 127]) On a n infinite c h e s s b o a r d , each square of odd

parity is a knight-move a w a y f r o m exactly one of the s q u a r e s w i t h coordinates (2x,2y) with x ~- y rood 4. Intersecting this lattice with a n m x n c h e s s b o a r d yields ran~16 + O(m + n) knights that c o v e r all odd squares at d i s t a n c e at least 3 from the n e a r e s t edge. T h u s a n extra O(m + n) knights d e f e n d all the odd squares o n the board. The same c o n s t r u c t i o n for the e v e n squares yields a total of mn/8 +

O(m + n). Diagram 27

@

White to move draws

5. One such p o s i t i o n is s h o w n i n Diagram 27. Once the a - p a w n is gone, the position is a t h e o r e t i c a l d r a w w h e t h e r Black plays f x g2 + (Black can do no b e t t e r t h a n s t a l e m a t e against Kxg2, Khl, Kg2 etc.) or f2 (ditto after Ke2, Kfl, etc.), or lets White play g x f 3 a n d Kg2 a n d t h e n j e t t i s o n the f-pawn to r e a c h the same draw that follows f x g 2 + . But as long as Black's a - p a w n is o n the board, White c a n m o v e only the knight s i n c e gxt'3 w o u l d liberate Black's b i s h o p w h i c h c o u l d t h e n force White's k n i g h t a w a y (for i n s t a n c e 1.Nb4 K b l 2 . g x f 3 ? g2+! 3.Kxg2 Bd6 4.Nd5 Kb2) a n d safely p r o m o t e the a-pawn. B l a c k ' s p a w n on f3 c o u l d also b e o n h3 with the s a m e effect. 6. The distance is a n integer, c o n g r u ent to m + n m o d 2, t h a t e q u a l s or exceeds each of !mi/2, !nl/2, and (jm~ + inl)/3. It is the s m a l l e s t s u c h integer except in the c a s e s a l r e a d y n o t e d of (m,n) = (0,-+1), (-+1,0), or (-2,_+2), w h e n the d i s t a n c e ex-

ceeds the a b o v e l o w e r b o u n d b y 2. 7. ( a d a p t e d f r o m Gorgiev) To win, White m u s t p r o m o t e the p a w n to a knight, c a p t u r e the p a w n s o n b5 a n d c4, a n d t h e n m a t e with N x b 3 w h e n the Black q u e e n is o n al. Thus N x b 3 m u s t be a n o d d - n u m b e r e d move. T h e r e f o r e 1.h4, 2.h5, 3.h6, 4.h7, 5.hSN d o e s n o t w o r k bec a u s e all k n i g h t p a t h s f r o m h8 to b3 have odd length. Since the knight c a n n o t "lose the move," the p a w n m u s t do so o n its initial move: 1.h3!, followed b y 6.hSN!, 7.Nf7, 8.Nd6, 9 . N x b 4 , 10.Nd6, l l . N X c 4 . 12.Na5. At this p o i n t the Black q u e e n is o n a2, h a v i n g m a d e 11 m o v e s from the initial position; w h e n c e the c o n c l u s i o n : 1 2 . . . Q a l 1 3 . N x b 3 mate. (We o m i t t e d from G o r g i e v ' s o r i g i n a l p r o b l e m the initial m o v e 1 . K i 2 X N e l Qa2-al, w h i c h only s e r v e d to give Black his entire a r m y in the initial p o s i t i o n a n d thus m a x i m i z e the material disparity; a n d w e m o v e d a Black p a w n from c5 to b5 to m a k e the sol u t i o n unique, at s o m e cost in strategic interest.) 8. Recall that a k n i g h t ' s m o v e j o i n s s q u a r e s differing b y o n e of the eight v e c t o r s (_+1, _+2) or (_+2, _+1), a n d c h e c k t h a t to get s o m e four of t h o s e to a d d to (0,6) we m u s t use the four v e c t o r s with a positive o r d i n a t e in s o m e order. Thus, to r e a c h d7 f r o m d l (or, m o r e generally, to travel six s q u a r e s n o r t h with n o o b s t r u c t i o n from the edges of the b o a r d ) in four moves, the k n i g h t m u s t m o v e o n c e in e a c h of its four north-going directions. T h e r e f o r e e a c h path c o r r e s p o n d s to a p e r m u t a t i o n of the four v e c t o r s (_+ 1,2) a n d (_+ 2,1). The n u m b e r of p a t h s is t h u s 4! = 24, a n d d r a w i n g t h e m all yields the image of the 4-cube u n d e r a proj e c t i o n t a k i n g the u n i t v e c t o r s to (-+1,2) a n d (-+2,1). I n s t e a d of d l a n d d7 w e c o u l d also d r a w the 24 p a t h s from a4 to g4 in f o u r m o v e s to get the s a m e picture. Not b2 a n d f6, though: b e s i d e s the 24 p a t h s of Diagram 13 t h e r e are o t h e r fourm o v e j o u r n e y s , for i n s t a n c e b2-d3f4-h5-f6. 9. (i) The m a x i m u m is still 32 (though

VOLUME25, NUMBER112003

31

there are many more configurat i o n s t h a t attain this m a x i m u m ) . To s h o w this, it is e n o u g h to p r o v e t h a t at m o s t 8 knights c a n fit o n a 4 • 4 b o a r d if e a c h is to b e def e n d e d at m o s t once. This in t u r n c a n b e s e e n b y d e c o m p o s i n g ~4.4 a s a u n i o n o f f o u r 4-cycles (Diag r a m 28), a n d n o t i n g t h a t o n l y t w o k n i g h t s c a n fit on e a c h 4-cycle. (ii) O n c e again, t h e m a x i m u m is 32, this t i m e w i t h a n e w configur a t i o n ( D i a g r a m 29) unique up to reflection! (But n o t e t h a t this c o n f i g u r a t i o n h a s a cyclic g r o u p o f 4 s y m m e t r i e s , unlike t h e e l e m e n t a r y a b e l i a n 2-group o f s y m m e t r i e s o f the maximal coclique (Diagram 6).) T h a t this is m a x i m a l f o l l o w s f r o m t h e first p a r t o f this puzzle. F o r u n i q u e n e s s , o u r p r o o f is t o o long to r e p r o d u c e h e r e in full; it p r o c e e d s a s follows. In a n y 32knight configuration, each of the four 4 x 4 corner subboards must c o n t a i n e i g h t knights, t w o on e a c h o f its f o u r 4-cycles. We a n a l y z e c a s e s to s h o w t h a t it is i m p o s s i b l e for t w o k n i g h t s in different s u b b o a r d s to d e f e n d e a c h other. We t h e n s h o w t h a t D i a g r a m 29 a n d its r e f l e c t i o n a r e t h e o n l y w a y s to fit f o u r eight-knight c o n f i g u r a t i o n s into a n 8 x 8 b o a r d u n d e r this constraint. 10. Yes, mn/8 + O(m + n)camels suffice. The c a m e l a l w a y s s t a y s o n s q u a r e s o f t h e s a m e color. T h e s q u a r e s o f o n e c o l o r m a y b e reg a r d e d o n a c h e s s b o a r d in its o w n right, t i l t e d 45 ~ a n d m a g n i f i e d b y a factor of ~/2--in other words, multiplied by the complex number 1 + i. On this b o a r d , t h e c a m e l ' s m o v e a m o u n t s to t h e o r d i n a r y k n i g h t ' s m o v e s i n c e 3 + i = (2 i)(1 + i). We c a n t h u s a d a p t o u r s o l u t i o n to Puzzle 4. Explicitly, o n a n infinite c h e s s b o a r d e a c h s q u a r e w i t h b o t h c o o r d i n a t e s o d d is a camel's move away from exactly o n e s q u a r e o f t h e f o r m (4x,8y). T h u s c a m e l s at (4x + a, 8x + b) (a,b E {0,1}) c o v e r the entire b o a r d w i t h o u t d u p l i c a t i o n , a n d t h e inters e c t i o n o f this c o n f i g u r a t i o n w i t h a n m • n b o a r d c o v e r s all b u t O(m + n) o f its squares.

3 ~'

THE MATHEMATICAL INTELLIGENCER

Diagram 28

Diagram

Solutions

D i a g r a m 14. (N. Elkies, R. Stanley, 1996) 1.c4 Na6 2.c5 N X c 5 3.e3 a6 4.Ne2 Nd3 mate. D i a g r a m 15. (G. Schweig, Tukon, 1938) 1.Nc3 d6 2.Nd5 Nd7 3 . N x e 7 Ndf6 4 . N x g 8 N x g 8 . The i m p o s t o r is the knight at g8, w h i c h a c t u a l l y s t a r t e d o u t at b8. Diagram 29

N

Solution of Puzzle 8(ii)

11. 1.d3 e5 2.Kd2 e4 3.Kc3 e X d 3 4.b3 d X e 2 5.Kb2 e X d l N mate. White c a n p l a y d4 i n s t e a d o f d3 (so B l a c k p l a y s e x d4) and can v a r y his m o v e order, b u t the final p o s i t i o n is bel i e v e d to be unique. This g a m e first a p p e a r e d in [17]. 12. (G. F o r s h i n d , R e t r o s Mailing List, J u n e 1996) l.e3 f5 2.Qf3 Kff 3 . B c 4 + Kf6 4 . Q c 6 + Ke5 5.Nf3 mate. 13. (G. Wicklund, Retros Mailing List. O c t o b e r 1996) 1.Nf3 e6 2.Ne5 Ne7 3 . N x d 7 e5 4 . N x f 8 Bd7 5.Ne6 Rf8 6 . N x g 7 mate. 14. (P. R6ssler, Problemkiste, A u g u s t 1994 (version)) 1.h4 d5 2.h5 Nd7 3.h6 Ndf6 4 . h x g 7 Kd7 5.Rh6 Ne8 6 . g x f 8 N mate. 1 4 ' . See s o l u t i o n to Puzzle 14. 15. (G. Donati, Retros Mailing List, J u n e 1996) 1.h4 g6 2.Rh3 g5 3.Re3 g• 4.1"3 h3 5.Kf2 h2 6 . Q e l h l N mate. 16. (O. Heimo, Retros Mailing List, J u n e 1996) 1.d4 e5 2 . d • d5 3.Qd4 Be6 4.Qb6 d4 5.Kd2 d3 6.Kc3 d2 7.a3 d l N mate. 17. a l - c 2 , c l - b 3 - a l , c3-a2-cl-b3, a 3 - b l c3-a2-cl, c2-a3-bl-c3, al-c2-a3, b3c l . S e v e n move sequences.

D i a g r a m 16. (U. H e i n o n e n , The Problemist 1991) 1.c4 Nf6 2.Qa4 Ne4 3.Qc6 N x d 2 4.e4 Nb3 5.Bh6 Na6! 6.Nd2 Nb4 7.Rcl Nd5 8.Rc3 Nf6 9.Rf3 Ng8 10.Rf6 Nc5 11.f4 Na6 12.Ngf3 NbS. H e r e b o t h B l a c k k n i g h t s a r e imp o s t o r s , as t h e y h a v e e x c h a n g e d places! F o r a d e t a i l e d a n a l y s i s o f this p r o b l e m , s e e [16, pp. 207-209]. D i a g r a m 17. (D. Pronkin, Die Schwalbe, 1985, 1st prize) 1.b4 Nf6 2.Bb2 Ne4 3.Bf6 e x f 6 4.b5 Qe7 5.b6 Qa3 6.bXa7 Bc5 7 . a x b 8 B Ra6 8.Ba7 Rd6 9.Bb6 Kd8 10.Ba5 b6 11.Bc3 Bb7 12.Bb2 Kc8 13.Bcl. 1.Nc3 Nf6 2.Nd5 Ne4 3.Nf6+ e x f 6 4.b4 Qe7 5.b5 Qa3 6.b6 Bc5 7 . b x a 7 b6 8 . a X b S N Bb7 9.Na6 0-0-0 1O.Nb4 Rde8 l l . N d 5 Re6 12.Nc3 Rd6 13.Nbl. This p r o b l e m i l l u s t r a t e s the Phoenix theme: a p i e c e l e a v e s its original s q u a r e to b e s a c r i f i c e d s o m e w h e r e else, t h e n a p a w n p r o m o t e s to exactly the s a m e p i e c e w h i c h r e t u r n s to t h e original s q u a r e to r e p l a c e the s a c r i f i c e d piece. In the first s o l u t i o n t h e b i s h o p at c l is p h o e n i x , while in t h e s e c o n d it is the k n i g h t at b l ! As if this w e r e n ' t s p e c t a c u l a r enough, B l a c k c a s t l e s in the s e c o n d s o l u t i o n b u t n o t t h e first. D i a g r a m 18. (M. Caillaud, Th~mes-64, 1982, 1st p r i z e ) 1.a4 c5 2.a5 c4 3.a6 c3 4 . a X b 7 a5 5.Ra4 Na6 6.Rc4 a4 7.b4 a3 8.Bb2 a2 9.Na3 a l N ! 10.Nb5 Nb3 11.cXb3 c2 12.Be5 c l N ! 13.Bb8 N d 3 + 14.eXd3 e5 15.Qg4 e4 16.Ke2 e3 17.Kt3 e2 18.Ke4 e X f l N ! 19.Nf3 N g 3 + 2 0 . h x g 3 h5 21.Rel h4 22.Re2 h3 2 3 . N e l h2 24.Qh3 h l N ! 25.g4 N g 3 + 2 6 . f x g 3 Ne7 27.Nd6 mate. An a m a z i n g f o u r p r o m o t i o n s b y B l a c k to knight, all c a p t u r e d ! D i a g r a m 19. (A. Frolkin, Shortest Proof Games, 1991) 1.g4 e5 2.g5 Be7 3.g6 Bg5 4 . g x h 7 Qf6 5.hxg8N! Rh4 6.Nh6

Re4 7.Nxf7 K x f 7 8.Nc3 Kg6 9.Na4 Kh5 1O.c3 g6. If 5.hXg8B? Rh4 6.BXf7+ K x f 7 7.Nc3 Re4 8.Na4 Kg6 9.c3 Kh5, then White m u s t disturb his position b e f o r e 1 0 . . . g6. A knight is able to "lose a tempo" by taking two moves to get from g8 to fT, while a bishop must take one or at least three moves.

15.aSN and wins, as White can play 19 N x f 3 mate j u s t after 1 8 . . . blQ. F o r the history of this problem, see [25, pp. xxi-xxii]. Diagram 23. (S. Loyd, Holyoke Transcript, 1876) 1.bXa8N! K x g 2 2.Nb6, followed by 3.a8Q (or B) mate. Note that a knight is n e e d e d to p r e v e n t 2 B• A queen or b i s h o p promotion at move one would be stalemate, and a r o o k p r o m o t i o n leads nowhere. Normally a key move of capturing a piece is c o n s i d e r e d a serious flaw b e c a u s e it r e d u c e s Black's strength. Here, however, the capture seems to accomplish nothing so it is acceptable. Loyd himself says "[ill the capture s e e m s a h o p e l e s s move 9 . . then it is obviously well con9

Diagram 20. (V. A. Korolikov, Sehach, 1957) White's knights are on squares of the same color and hence have made an odd n u m b e r of moves in all. The White rooks and the White king have made an even n u m b e r of moves, and White has m a d e one p a w n move. No other White units (i.e., the queen and bishops) have moved. Hence White has made an even number of moves in all. Similarly, Black has made an odd n u m b e r of moves. Since White m o v e d first, it is currently Black's move, so Black mates in one with 1 . . . N Xc2 mate.

.

.

cealed, and the m o s t difficult keymove that could be selected" [18, p. 156]. F o r further p r o b l e m s by Loyd featuring distant knight p r o m o t i o n , see [27, pp. 402-403]. Diagram 24. (G. Cseh, StrateGems, 2000, 1st prize) 1.hlN! Nd6 2.h2 Nf5 3.Ng3+ NXg3 4.hlN! Ne2 5 . f x e 2 + Kg2! (not 5 . . . Kxe2?, since Black's tenth move would then c h e c k White) 6.flN! Rc7 7.Bg3 R x c 3 8 . B x e 5 RXc2 9.Bg7 R x c l 1 0 . b x c l N ! BXg7 mate. F o u r p r o m o t i o n s to knight by Black. REFERENCES

[1] W. Ahrens, Mathematische Unterhaltungen und Spiele, Teubner, Leipzig, 1910 (Vol. 1) and 1918 (Vol. 2). [2] E. R. Berlekamp, J. H. Conway, and R. K.

Diagram 21. (P. O'Shea, The Prom lemist, 1989, 1st prize) 1.Ne5 b l N + (the only defense to 2.Nf3 mate) 2.Ka2 Nd2 3.Kal Nb3+ 4.Kbl Nd2§ 5.Ka2. If Black moves either knight then c h e c k m a t e is immediate, so 5 . . . a3 is forced. Now White and Black r e p e a t the m a n e u v e r Kal, Nb3+, Kbl, Nd2+, Ka2 (any pawn moves by Black would j u s t hasten the end): 8.Ka2 a4 l l . K a 2 a5 14.Ka2 a6. Then 15.Kal N b 3 § 16.Kbl a2+ 17.K• Nd2. This m a n e u v e r gets rep e a t e d until all of Black's a-pawns are captured: 44.Kxa2 Nd2 45.Kal Nb3§ 46.Kbl Nd2+ 47.Ka2. Finally Black m u s t allow 48.Nf3 mate or 48.Ng4 mate! Diagram 22. (H. M. Lommer, Szachy, 1965) White c a n n o t allow Black's rook at e8 to stay on the board, but how does White p r e v e n t Black from being s t a l e m a t e d without releasing the sleeping units in the h l c o m e r ? 1.fxe8N d3 2.Nf6 (not 2.Nd6? eXd6, and s t a l e m a t e c a n n o t be prevented without releasing the h l corner) g• f6 (capturing with the other pawn merely h a s t e n s the end) 3.g5 f xg5 4.g7 g4 5.g8N g3 6.Nf6 e x f 6 7.Kg6 f5 8.e7 f4 9.e8N f3 10.Nd6 c • 11.c7 d5 12.c8N d4 13.Nb6 a f b 6 14.a7 b5

VOLUME 25, NUMBER 1, 2003

33

[3]

[4]

[5]

[6]

[7]

[8]

[9] [10]

[11]

Guy, Winning Ways, vol. 2, Academic Press, London/New York, 1982. H. E. Dudeney, Amusements in Mathematics, Dover, New York, 1958, 1970 (reprint of Nelson, 1917). N. D. Elkies, On numbers and endgames: Combinatorial game theory in chess endgames, in [22], pp. 135-150. G. Foster, Sliding-block problems, Part 1, The Problemist Supplement 49 (November, 2000), 405-407. G. Foster, Sliding-block problems, Part 2, The Problemist Supplement 51 (March, 2001 ), 430-432. G. Foster, Sliding-block problems, Part 3, The Problemist Supplement 54 (September, 2001), 454. G. Foster. Sliding-block problems, Part 4, The Problemist Supplement 55 (November, 2001), 463-464. M. Gardner. Mathematical Magic Show, Vintage Books, New York, 1978. J. Gik, Schach und Mathematik, MIR, Moscow, and Urania-Verlag, Leipzig/Jena/ Berlin, 1986; translated from the Russian original published in 1983. B. Hochberg, Chess Braintwisters, Sterling, New York, 1999.

[12] D. Hooper and K. Whyld, The Oxford Companion to Chess, Oxford, Oxford University Press, 1984. [13] G. P. Jelliss, Synthetic Games, September 1998, 22 pp. [14] G. P. Jelliss, Knight's TourNotes: Knight's Tours of Four-Rank Boards (Note 4a, 30 November 2001), http://home.freeuk.net/ ktn/4a.htm [15] T. Krabb& Chess Curiosities, George Allen & Unwin Ltd., London, 1985. [16] J. Levitt and D. Friedgood, Secrets of Spectacular Chess, Batsford, London, 1995. [17] C. D. Locock, Manchester Weekly Times, December 28, 1912. [18] S. Loyd, Strategy, 1881. [19] B. McKay, Comments on: Martin Loebbing and Ingo Wegener, The Number of Knight's Tours Equals 33,439,123,484, 294--Counting with Binary Decision Diagrams, Electronic J. Combinatorics, http:// www.combinatorics.org/Volume 3/Comments/v3ilr5.html. [20] J. Morse, Chess Problems: Tasks and Records, London, Faber and Faber, 1995; second ed., 2001. [21] I. Newman, problem E 1585 ("What is the maximum number of knights which can be

[22]

[23]

[24] [25]

[26]

[27]

[28]

placed on a chessboard in such a way that no knight attacks any other?"), with solutions by R. Patenaude and R. Greenberg, Amer. Math. Monthly 71 no. 2 (Feb. 1964), 210-211. R. J. Nowakowski, ed., Games of No Chance, MSRI Publ. #29 (proceedings of the 7/94 MSRI conference on combinatorial games), Cambridge, Cambridge University Press, 1996. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, on the Web at http://www.research.att.com/-njas/sequences. L. Stiller, Multilinear Algebra and Chess Endgames, in [22], pp. 151-192. M.A. Sutherland and H. M. Lommer, 1234 Modem End-Game Studies. Dover, New York, 1968. G. T6rnberg, "Knight's Tour", http://wl. 859.telia.com/- u85905224/knight/eknig ht.htm. A. C. White, Sam Loyd and His Chess Problems, Whitehead and Miller, 1913; reprinted (with corrections) by Dover, New York, 1962. G. Wilts and A. Frolkin, Shortest Proof Games, Gerd Wilts, Karlsruhe, 1991.

MOVING? W e n e e d y o u r n e w a d d r e s s so that y o u d o n o t m i s s a n y issues of

THE M A T H E M A T I C A L INTELLIGENCER. P l e a s e s e n d y o u r o l d a d d r e s s (or label) a n d n e w a d d r e s s to:

Springer-Verlag N e w York, Inc., Journal Fulfillment Services P.O. Box 2485, Secaucus, NJ 07096-2485 U.S.A. Please give us six weeks notice.

34

THE MATHEMATICALINTELLIGENCER