Ed Pegg Jr., April 11, 2005
I recently picked up Across the Board by John Watkins, a book on a variety of mathematical chess problems. Here are a few of the problems you might expect to see:
Some of the things I hoped to see were missing, so I'll list some of them here.
Problem 5 is the non-dominating queens problem, and a favorite puzzle of both Martin Gardner and me. (Solve it!) It's a favorite problem of Mario Velucchi. Here are six of the 7 solutions for the 8×8 board. For placing n queens on an n×n board, the maximal number of non-dominated squares is still unsolved for n>17.
Figure 1. Six solutions for the non-dominating queens problem. Find the seventh.
Erich Friedman recently explored the non-dominating problem for bishops and knights. Another interesting question is to place equal armies of queens on a board peacefully. I believe two armies of 9 queens can be placed on a chessboard, but I cannot pin down the source. On the 12×12 board, three armies of 10 queens can be placed peacefully in a variety of ways.
Figure 2. Three armies of 10 in peaceful queens problem.
There is also the dominating queens problem. Watkins covers this problem very well. A classic problem is to attack or cover every square of a chessboard with 5 queens. That's easy -- so try it with 3 queens and 2 rooks (the solution is unique). Solutions for the 11×11 board and 21 knights, or the 18×18 board and 9 queens show how tricky the problem can be. The definitive paper on dominating queens is "Values of Domination Numbers of the Queen's Graph."
Figure 3. 21 dominating knights, and 9 dominating queens.
No-three-in-line is one of the great unsolved questions. Can 2n lattice points (x, y) (1≤ x, y ≤ n) be selected with no three in a straight line? At first, lots of solutions can be found, but the problem gets increasingly difficult. Below is the single known solution for n=52, found by Achim Flammenkamp. Almost nothing is known for n>52.
Figure 4. The current record holder for the No-three-in-line problem.
Richard Guy (pers comm, Oct 2004): "I got the no-three-in-line problem from Heilbronn over 50 years ago. See F4 in UPINT. In Canad. Math. Bull. 11 (1968) 527--531; MR 39 #129 Guy & Kelly conjecture that, for large n, at most (c + ε)n points can be selected. Curiously, as recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives c = π/sqrt(3), or c ~ 1.813799. I should send a correction to Canad Math Bull! For those with a lot of computer time to spare, there's a lot to be discovered. Apart from a limping odd-even phenomenon, the number of solutions with 2n points appears to grow exponentially at first. Who will be the first to show that this begins to tail off? A000769 in OEIS has 3 more terms than I give in UPINT (perhaps due to Flammenkamp?)."
Here are more solutions by Flammenkamp, counting down from n=50 to 36. Thousands more are available at Flammenkamp's No-three-in-line site. It is strongly believed that the number of solutions is finite. The last computer to tackle this problem was a 1995-era system.
Figure 5. More solutions for the No-three-in-line problem.
Arrange 5 sets of 5 queens on a 5×5 board so that the board is completely covered, and so that each set of queens is non-attacking. This is a fairly easy problem. For 8 sets of 8 queens on an 8×8 board , the problem has no solution. How about 12 sets of 12? Well, George Pólya showed that a doubly periodic solution for the n-queens problem exists if and only if n = 1 or 5 (mod 6). For years, due to Pólya, it has been assumed that n=12 is unsolvable. Patrick Hamlyn and Guenter Stertenbrink tackled it anyway, using a clique-search program in the graph of all 14200 12-queen solutions. Turns out there are 454 solutions. None of the solutions is doubly periodic, of course. They also solved n=14, but suspect that n=16 is unsolvable.
Figure 6. What Pólya missed -- 12 sets of 12 queens on a 12×12 board. By Guenter Stertenbrink and Patrick Hamlyn.
The first half of Across the Board covers knight tours of various sorts. I was shocked (shocked!) that Watkins did not reference Leaper Graphs by Don Knuth. More amazingly, on the knight tour material, he didn't reference the G. P. Jelliss study Introducing Knight's Tours. There is no mention of variant pieces. For example, the knight is considered a (1,2) leaper. There are other leapers.
One variant piece, the fiveleaper, is a generalized knight that makes moves of length 5. In coordinates, it moves as either (0,5) or (3,4). G.P. Jelliss made the following observation: “Since the fiveleaper has four moves at every square of the 8×8 board, it follows that in every closed tour the unused moves are also two at every square, and therefore form either a tour (is this possible?) or a pseudotour (i.e. a set of closed circuits). The question of whether such a double tour is possible was in fact answered in the affirmative by Tom Marlow.”
20 47 62 55 06 21 46 63 . 46 37 60 11 56 49 04 63
31 42 57 50 11 34 29 44 . 39 24 31 52 27 40 23 32
02 59 16 09 52 03 36 17 . 54 15 06 21 34 29 16 13
13 22 39 26 19 14 23 38 . 57 08 03 64 19 36 59 10
54 05 28 45 64 61 56 07 . 26 41 50 45 38 25 42 51
51 48 35 30 43 58 49 10 . 47 28 61 12 55 48 05 62
32 41 24 37 12 33 40 25 . 20 35 30 53 14 07 22 33
01 60 15 08 53 04 27 18 . 01 18 43 58 09 02 17 44
Figure 7. A fiveleaper double tour by Tom Marlow.
As it happens, I intended for my first serious mathematical paper to involve leaper tours. A few weeks after I started my research, Don Knuth's Leaper Graphs was published, which completely trumped everything I'd been planning. I was advised to pick another topic. I remember being upset about Knuth being so thorough. Since then, I have learned a truism for mathematics -- "Someone else thought of it first." Still, here is a portion of of my own leaper study.
1. There is no closed tour for the (1,2) leaper [knight] on a 4×n board.
Proof by contradiction: Suppose such a tour existed. As can be seen in diagram 1, every is adjacent to two 's. A is never adjacent to a . Since half the tour consists of , the tour must look something like ... , where the first and last gray cells are the same cell. Thus, every other move is a .
As can be seen in diagram 2, are adjacent only to . Every other move must be a . By combining these two results, we get a contradiction; namely, that one fourth of the points support one half of the total moves.
2. There is no open tour for a (1,2) leaper on a 4×4 board.
Proof A: Examine the and points of diagram 3. The corner are adjacent only to the interior . The same applies to the corners. A closed tour is thus impossible, since these two colors are closed to the rest of the board. However, we have the leeway of a spare move at the beginning and end of an open tour. We can start with a corner, eventually make a move from a interior point to a and , move to a interior point, and finish the tour. Unfortunately, it is impossible to move directly from a dot point to a clear point. So an open tour is impossible.
Proof B: This proof exploits the idea of Proof 1. Color the outer columns as shown in diagram 4. A closed tour is impossible, as described in Proof 1. However, an open tour is possible on a 4×n board, provided the move sequence looks something like the following: ... , If we color the top and bottom rows, we reach the same conclusion. Combining these, a tour is possible as long as we move from a in diagram 5 to another . This is impossible.
3. There is no open tour for a (1,4) leaper on an 8×8 board.
Proof A: Examine diagram 6. Borrowing a term from Cartesian coordinates, examine the eight in the first and third quadrants. They are adjacent only to in the second and fourth quadrants. Similarly, the in the second and fourth quadrants are adjacently only to in the first and third quadrants. From here on, the proof is identical to the proof in 2A.
Proof B: Color the board as shown in diagram 7. The are adjacent only to and . The closed tour is impossible, see proof 1. An open tour might be possible if we move from a non- to a non- midway through the tour. Rotate the diagram 90 degrees, and make the same observations. A tour is possible if two are tour-adjacent. But they aren’t, so there isn’t an open tour.
4. There is no open tour for a (2,3) leaper on an 8×8 board.
Proof: In diagram 8, each has degree 2, unless it marks the beginning or end of a tour, in which case it can have degree 1. The are adjacent only to . The require at least (14×2 + 2×1 = 30) lines, but the can only accept (12×2 = 24) of these lines. An open tour is thus impossible.
5. There is no open tour for a (2,3) leaper on a 9×9 board.
Proof: In diagram 9, each is adjacent to two . Each is adjacent to at least one . The and points require at least ( (16×2 + 16×1)/2 = 24) points, but there are only 21 , so the open tour is impossible.
A similar coloring scheme is useful for showing the impossibility of (a,b) leapers on small boards.
6. There is no open tour for a (2,3) leaper on an 11×11 board.
Proof: First, note that this is an odd board. Due to parity, and can neither begin nor end the open tour. Next, note that are adjacent only to and . During the course of the tour, we must have the sequence four times. Now look at the . As far as the tour is concerned, the cannot be adjacent to , so they must be adjacent to the . Since each has degree two, we have a closed loop: . The tour is impossible. This problem was first solved by Dan Cass.
7. There is no open tour for a (2,3) leaper on a 12×12 board.
Proof: First, note that a closed tour is impossible. Each has degree 2 and is only adjacent to . There are 36 and 36 , and thus we have a closed system.
Now then, using the methodology in Proof 1, note that and are adjacent only to and . Turn the diagram 90 degrees and note the same thing. Combining, an open tour is possible only if we can move from a to a midway through the tour. We can! But this use of the only free move leads to the same closed system described above. Thus the open tour is impossible.
I like Knuth's approach more, but I still think my proofs are kinda cute. In his book, Watkins uses some nice proofs for tours as well, along with a gentle introduction to graph theory. While I'm on proofs, let me mention that the rook-domino problem (9) also requires a cute proof.
I've been somewhat harsh about Across the Board, mainly because of the book description: "Across the Board is the definitive work on chessboard problems." Too much famous material is missing for me to agree with the middle word. To be fair, I did enjoy the book. It's well-written, entertaining, friendly, educational, and does contain more on mathematical chess than any other book I know of. I do hope a second edition will truly earn the word definitive.
Hans Bodlaender, "The Chess Variant Pages," http://www.chessvariants.com/Gindex.html.
Doug Chatham, "The N+1 Queens Problem," http://people.moreheadstate.edu/fs/d.chatham/N+1QP.pdf.
Douglas Chatham, Gerd Fricke, and Duane Skaggs, "The Queens Separation Problem," http://people.moreheadstate.edu/fs/d.chatham/queenssep.pdf.
Martin Chlond and Cath Toase, "IP Modeling of Chessboard Placements and Related Puzzles," http://ite.pubs.informs.org/Vol2No2/ChlondToase/.
Achim Flammenkamp, "The No-Three-in-Line Problem," http://wwwhomes.uni-bielefeld.de/achim/cgi/no3in/readme.html.
Erich Friedman, "Non-Attacking Bishop," http://www.stetson.edu/~efriedma/mathmagic/0305.html.
Richard Guy, "F4 The no-three-in-a-line problem" in Unsolved Problems in Number Theory, Springer, 2004.
G. P. Jelliss, "Introducing Knight's Tours," http://homepages.stayfree.co.uk/gpj/ktn.htm.
G. P. Jelliss, "The Games and Puzzles Journal," http://gpj.connectfree.co.uk/index.htm.
Donald Knuth, "Dancing Links," Millennial Perspectives in Computer Science, http://www-cs-staff.stanford.edu/~knuth/papers/dancing-color.ps.gz.
Donald Knuth, "Leaper Graphs," Math. Gazette 78 (1994), 274--297, http://arxiv.org/abs/math/9411240.
T. W. Marlow and G. P. Jelliss, "Fiveleaper Tours," http://www.ktn.freeuk.com/9f.htm.
Patric Östergård and William Weakley, "Values of Domination Numbers of the Queen's Graph," E-Jour of Comb 29:8, 2001. http://www.combinatorics.org/Volume_8/Abstracts/v8i1r29.html.
Neil Sloane, "No-3-in-line problem: number of ways of placing 2n points on n×n grid so no 3 are in a line." A000769 in the On-Line Encyclopedia of Integer Sequences.
Mario Velucchi, "For Me, this is the Best Chess-Puzzle!" http://anduin.eldar.org/%7Eproblemi/papers.html.
John Watkins, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2004.
Eric W. Weisstein. "Queens Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/QueensProblem.html.
Comments are welcome. Please send comments to Ed Pegg Jr. at firstname.lastname@example.org.
Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld, and as administrator of the Mathematica Information Center.