Across the Board: The Mathematics of Chessboard Problems (Princeton Puzzlers)
John J. Watkins
Format: PDF / Kindle (mobi) / ePub
Across the Board is the definitive work on chessboard problems. It is not simply about chess but the chessboard itself--that simple grid of squares so common to games around the world. And, more importantly, the fascinating mathematics behind it. From the Knight's Tour Problem and Queens Domination to their many variations, John Watkins surveys all the well-known problems in this surprisingly fertile area of recreational mathematics. Can a knight follow a path that covers every square once, ending on the starting square? How many queens are needed so that every square is targeted or occupied by one of the queens?
Each main topic is treated in depth from its historical conception through to its status today. Many beautiful solutions have emerged for basic chessboard problems since mathematicians first began working on them in earnest over three centuries ago, but such problems, including those involving polyominoes, have now been extended to three-dimensional chessboards and even chessboards on unusual surfaces such as toruses (the equivalent of playing chess on a doughnut) and cylinders. Using the highly visual language of graph theory, Watkins gently guides the reader to the forefront of current research in mathematics. By solving some of the many exercises sprinkled throughout, the reader can share fully in the excitement of discovery.
Showing that chess puzzles are the starting point for important mathematical ideas that have resonated for centuries, Across the Board will captivate students and instructors, mathematicians, chess enthusiasts, and puzzle devotees.
order, and ﬁnally shifting back to the front in order to close the tour. Problem 5.4 First, ﬁnd a Gray code for the sixteen binary strings of length 4. Then, by labeling the squares of a 4 × 4 69 CHAPTER 5 Figure 5.4 White to mate in four moves on a torus. chessboard so that the knights graph for the 4 × 4 chessboard on a torus becomes the 4-cube, show that your Gray code also provides a knight’s tour on a torus for the 4 × 4 chessboard. A Chess Problem I promised in the very ﬁrst chapter
then the Euler characteristic is given by Euler’s formula: the Euler characteristic of the surface = v − e + r . So, what can this formula tell us about chessboards? When I decide to put a chessboard on one of these surfaces—and remember, these surfaces don’t have boundaries—I want the following thing to happen: I want every square on the board to ‘feel’ like a square in the middle of a standard chessboard. In other words, chess pieces should be able to move in any one of the four
bottle with 4 bishops. Since a bishop does cover twice as many squares on a Klein bottle as it covers on a torus, it is not at all surprising that we can prove the following result. Theorem 9.3 (Johnson) The bishops domination number for an n × n chessboard on a Klein bottle is given by klein γ(Bn×n )= 1 2n . In order to understand how this works in general it is useful to look carefully at the 8 × 8 chessboard. In Figure 9.7, we see in separate diagrams the squares that are covered by four
immediately. As for the claim, whether a corner square in the top row is occupied determines whether or not the opposite corner square in the bottom row is occupied or not; similarly, for a non-corner square in 184 INDEPENDENCE Figure 10.14 The top row determines the arrangement of independent bishops. the top row, whether it is occupied determines what happens at the two corresponding squares in the side columns and also at the corresponding square in the bottom row, as shown on the left in
need to cover a chessboard? How many knights? These are examples of a large and important category of problems called domination problems in graph theory. Domination problems are being energetically investigated by mathematicians all over the world these days, in large part because they arise so naturally in a large number of real-world applications. However, it is worth remembering that domination problems ﬁrst originated when people began asking ‘covering’ questions about chess pieces. Even the