## A A 1 fiSAA

5. 412 moves

6. Two moves that only one man (the white queen) can move [see Figure 116, No. 7]. No one has yet found a way to place legally all 32 men so that no move is possible.

There are many legal ways to place the 16 nonpawns to achieve a maximum of 46 captures, and all 32 men can be legally placed to allow 88 captures. How about illegal positions? If 32 black knights go on black cells and 32 white knights on white cells, 336 captures are possible. This was considered the

Figure 116, No. 7

Figure 116, No. 7

7. Only white queen can move

maximum for many decades until 1967, when T. Marlow ingeniously substituted two queens and two pawns for four knights to raise the record to 338 [see Figure 116, No. 8], It is assumed that each capture by a pawn counts as four moves because it can become any of four pieces.

I have touched on only a small fraction of tasks concerning moves and captures. Space does not allow discussing the hundreds of tasks involving checks, discovered checks, mates, selfmates, stalemates, forced captures (every move a capture), forced checks, forced mates and so on. Of special interest to combinatorial mathematicians are one-move construction tasks involving the placing of a specified set of men so that a maximum or a minimum number of cells are attacked or unat-tacked, or to achieve some other goal that does not involve moves or captures. A classic problem of this type (see Chapter 16 of The Unexpected Hanging) is to place eight queens (the maximum) so that no queen attacks another. The similar tasks of maximizing the number of nonattacking rooks (8), bishops (14), knights (32) and kings (16) are considered in the same chapter. A more difficult problem is to place 16 pawns (the maximum) so that no three are in a straight line. Lines are not restricted to rows, columns or diagonals but may have any orientation. Think of each pawn as a point in the center of the cell it occupies. No three such points may be colinear. One of many solutions is shown in Figure 116, No. 9. It is the only one in which two pawns occupy central cells.

Figure 116, No. 8 & 9

i i

k&k&k&Kd

1 A

(kk&t&kiik

I i

1 1

& kCAk a k

i l

i

Ali

i i

9. No three pawns in a line

8. 338 captures

### 9. No three pawns in a line

Another difficult task of the same general category is to place eight queens so that 11 vacant squares are not attacked. There are at least six basic ways to do it (the exact number is not known), one of which will be given in the Answer Section. Eleven unchecked cells is undoubtedly maximum, although no proof is known to me.

A generalization of this problem—placing n queens on an order-w square to leave a maximum number of unattacked vacant cells—has not, to my knowledge, been fully analyzed. When n equals 1, 2 or 3, it is easy to see that no cell may be unchecked. When n equals 4, only one cell may be unchecked. For n equals 5 the problem is suddenly nontrivial. Three cells may be unattacked, but the pattern is difficult to find and also unique, except for rotations and reflections. Can the reader find it before checking the answer? The maximum number of unattacked cells when n equals 6, 7, 8, 9, 10, 11, 12 is believed to be 5, 7, 11, 16, 22, 27 and 36 respectively.

The minimum number of queens needed to attack all vacant cells of square boards is a general problem that has been thoroughly explored for boards of order 2 through 13. Since no piece attacks the cell it is on, the problem falls into three main groups: solutions in which no queen attacks another, or all queens are attacked, or some, but not all, are attacked. On the standard chessboard five queens are required in all three cases, and there are hundreds of solutions. Two tasks of this type on smaller boards are particularly pretty because each has only one basic solution. Can the reader put three queens on an or-der-6 board so that all vacant cells are attacked? Can he put four queens on an order-7 board so that all vacant cells are attacked and no queen attacks another?

Four queens can be placed on the order-8 board so that a maximum of 58 vacant cells are checked, leaving only two unchecked empty cells. There are many ways to eliminate those two squares by adding a single rook, bishop or king, but to check all vacant cells with four queens and a knight seems to have only one basic solution, which was first published by J. Wallis in 1908. Can the reader discover it? (Hint: The four queens must leave three of the vacant cells unchecked.)

It is easy to prove that nine kings, eight bishops or eight rooks are needed to attack all vacant cells on a standard chessboard. Much harder to find is the unique pattern by which 12 knights (the minimum) check all vacant cells. (See my Mathematical Magic Show, Chapter 14.) To attack all 64 squares requires 14 knights, or eight rooks, or 10 bishops, or 12 kings.

The eight pieces of one color can attack all 64 squares only if the bishops are on the same color. With bishops on opposite colors 63 squares is maximum. Douglas G. Smith, of Fresno, CA., recently sent me the result of his long search for a way to eliminate one of these eight pieces and still attack all vacant cells. He found how to do it by dropping a bishop. I do not know if his beautiful solution is unique (aside from rotations, reflections and trivial rearrangements of the rooks and queen) or if the task can be solved by dropping a knight or the king instead of a bishop. To make the task completely clear: Place a queen, king, two rooks, two knights and a bishop on a chessboard so that all vacant cells are in check.

For readers who may want to go more deeply into this obscure corner of chess recreations, I have listed basic references in the Bibliography for this chapter.

1. Sam Loyd's three-move mate, all white men in starting position and a lone black king on Black's KR5:

 1. P-Q4 1. K-R4 2. Q-Q3 2. K moves 3. Q-KR3 (mate) or 1. P-Q4 1. K-N5 2. P-K4 (ch) 2. K moves 3. P-KN3 (mate)

2. One of six known ways to place eight queens so that 11 vacant cells are unattacked is shown in Figure 117 a. The unchecked squares are indicated by dots.

3. There is only one basic way to place five queens on an or-der-5 board so that three vacant cells are unattacked [see Figure 117 b], Mannis Charosh has suggested that the best systematic search procedure for proving uniqueness is to explore the equivalent problem of placing three queens so that five cells are unchecked, taking advantage of the board's symmetries to shorten the search.

4. The only basic way to place three queens on an order-6 board so that all vacant cells are checked is shown in Figure 117 c.

5. The only basic way to put four queens on an order-7 board so that all vacant cells are checked and no queen attacks another queen is shown in Figure 117 d.

Unit

Chapter 17

6. The only known basic way to place four queens and one knight so that all vacant cells are attacked is shown in Figure 117 e.

7. Figure 117 / shows one way to place seven of the eight pieces of one color so that all vacant cells are in check. The positions of the rooks and queen can be given trivial variations.

The problem of placing five queens on a 5 x 5 board so that three cells are not attacked has appeared in many places since I introduced it in my 1972 column. It is usually given in the following form: Place five queens of one color and three of another color on an order-5 board so that no queen attacks a queen of a different color. I myself gave it in this form in a later (February 1978) column.

I had in 1972 confined the task to n queens on a board also of order n. When I gave it again in 1978 for the order-5 board, a number of readers generalized it to k queens on an order-w board. The best results came from Hiroshi Okuno, of Tokyo, whose computer search provided valuable data for low values of n and k. In 1983, Ronald L. Graham and Fan K. Chung, both of Bell Laboratories, turned their attention to Okuno's data and made some truly remarkable discoveries about the general problem. They will be reported in a paper that may appear before this book is off the press.

### BIBLIOGRAPHY

"Chessboard Recreations." W. W. Rouse Ball in Mathematical Recreations and Essays. Macmillan, 1892, twelfth edition, 1972. Les tours de force dur I'echiquier. Alain White. Paris: 1906. "Chessboard Problems." Henry E. Dudeney in Amusements in Mathematics. London: Thomas Nelson, 1917, Dover reprint, 1958. Ultimate Themes. Thomas Rayner Dawson, privately published by C. M. Fox, Surrey, England, 1937; included in Five Classics of Fairy Chess, by Dawson, Dover, 1973. Rund um das Schachbrett. Karl Fabel. Berlin: Walter De Gruyter, 1955. "Combinatorial Problems on the Chessboard." A. M. Yaglom and I.

M. Yaglom, in Challenging Mathematical Problems. Holden-Day, 1964. "Chessboard Placement Problems." Joseph Madachy in Mathematics on

Vacation. Scribner's, 1966. Schach und Zahl. Eero Bonsdorff, Karl Fabel, and Olavi Riihimaa. Düsseldorf: Walter Rau Verlag, 1966.

A Guide to Fairy Chess. Anthony S. M. Dickins. Privately printed by the author, Surrey, England, 1967. Revised edition, Dover, 1971. Records in One-Mover Chess Construction Tasks. W. Cross and A. S. M.

Dickins. Privately printed, Surrey, England, 1970. "Chess Pieces." Stephen Ainley in Mathematical Puzzles. London: G. Bell, 1977.

Chess Ultimates. An irregularly published periodical on chess tasks, edited by Thur Row (Morton W. Luebbert, Jr.), 12039 Gardengate Drive, St. Louis, Mo. 63141. The cost is 50? per copy in the United States and Canada, 65? elsewhere. A Chess Ultimates Handbook with more than 1,000 record positions is in preparation.

0 0