# ACROSS THE BOARD: THE MATHEMATICS OF CHESSBOARD PROBLEMS

This remarkable book is the first systematic work on chessboard problems and full-length book on the chessboard itself, devoted to an intriguing and comprehensive study from the knight´s tour problem and Queens Domination problems, in their many variations. Such earlier problems, including those involving other particular considerations, have now extended to three-dimensional chessboards, torus-shaped boards, a shape called Klein bottle, cylinders, etc.

The book is a stimulating and very well written. It is admirably clear. It explains not only methods and results but the motives for choosing, in each moment, various procedures. The material used in the book, is supplemented by excellently chosen exercises, questions or problems, some of which give an insight into other aspects of the proposed chapters. There is a good collection of problems and worked examples, with variations extending to boards of different sizes and shapes.

Across the board, is a concise, good, cleared, and indeed, definitive book on chessboard questions and problems. It is not simply about chess but the chessboard itself, in particular, the intriguing and challenging mathematics behind it. John Watkins, a well-known mathematician, surveys all the problems of interest in this promising area of recreational mathematics. Each main topic is treated in depth from its historical creation through to its status today.

The book is self-contained. The mathematical material is sufficiently closed, and contains up-to-date exposition of the key aspect of recreational mathematics. The book is quite accessible for undergraduate students of low courses, thus it can be used as a basic course book on recreational mathematics. This book can also be useful for professional and amateur mathematicians, because it contains the newest and the most significant scientific developments in this area.

The aim of the present book is to describe the main concepts of modern recreational mathematics together with full proofs that would be both accessible to beginners and useful for amateur and professional in chess problems. A large part of the present title is devoted to rapidly developing areas of recreational mathematics, such that, toruses, cylinders, others three-dimensional chessboards, etc.

The book contains thirteen chapters, references and an index, in 257 pp. It goes from the basics, classical and variants of the knight´s tour problems, domination in the queens problems, magic squares, etc., to the frontiers of research, because Watkins uses the visual language of graph theory, and guides perfectly the reader to the frontiers of current research, in news ideas emergent in mathematics. For the reader is suitable solving some of the many exercises. ¡Good experience for share seriously the problems! In short, the great resource to Professor Watkins´s proper tone ensures total attention from the audience to recreational mathematics.

The first chapter, untitled Introduction, (pp. 1-24), introduces the basic, definitions and notions, devoted to present the main topics in the subject. The chessboard provides the field of play for any number of games. Beginning with the Guarini´s problem, the earliest puzzle dated from 1512, in graph theory, and, then, one extension of Guarini´s problem to six knights, three white and three black, appeared in Scientific American in the December 1979 issue. We have just studied the famous problem of Knight´s Tour Problem, dates in the sixth century in India, with a long and rich history, from the beginnings to the frontiers of research. It is one of the main topics considered in this book.

This chapter is a compendium, remarkable and fascinating encyclopedic treatment of basics, and the main topics in the area of recreational mathematics. The main topics considered and studied in the following chapters are: Knights Tour, it follows the Euler´s work in 1759, the impossibility of an knight´s tour on 4x4 board; Domination problems, first originated when the people began asking covering questions about chess pieces, i.e., the minimum number of pieces of a given type needed to cover or control the entire board; Independence problems, what is the maximum number of pieces that you can place on chessboard, so that no two pieces attack one another?; Coloring, this is a theme of high recurrence, because using coloring to see how find infinitely many chessboards that can´t possibly have knight´s tours!; Geometric Problems, covering problems in the board; Chessboards on other surfaces, and even covering chessboards with ominoes in all manner of sizes: polyominoes, i.e., monominoes, dominoes, trominoes, tetraminoes, pentominoes, and so on, for example, the domino puzzle (Gomory´s theorem) for covering the chessboard.

Moreover, another interesting topic inside in a large number and not particularly easy to categorize is a puzzle that was popular in the eighteenth century, called Ozanam´s Problem, the study of the creation a Graeco-Latin square.

This chapter contains, moreover, six interesting problems, stated and solved, that cover the different relevant questions.

Chapter 2, (pp. 25-38) is full dedicated to Knight´s Tours, from the early work to actually: de Moivre, Legendre, Euler that provide a powerful and flexible technique, known Euler strategy, similar to actual backtracking algorithm, Hamilton, and other outstanding mathematicians. In other words, when we are looking for a knight´s tour we are actually trying to find a Hamiltonian cycle in the associated graph. It is possible consider also another tours, for example the rook´s tour for proved the Gomory´s theorem; the queen tour, in particular Dudeney´s puzzle, bishop´s tour problem, and the king´s tour.

This chapter contains, moreover, six interesting problems, stated and solved, that cover the different relevant questions.

In chapter 3 (pp.39-52) on consider the Knight´s Tour Problem. On prove the impossibility of such tour for a number of other chessboards. It mentioned that a 3x10 board was the smallest such board for which a knight´s tour is possible. A knight´s tour is impossible on the 4x4 chessboard, and also on any board both of whose dimensions are odd. There are no tours for the 3x4, 3x6 or 3x8 boards.

In this chapter on present two proofs of the impossibility of knight´s tours for 4xn boards, one due to Pósa and another one to Golomb, the inventor of polyominoes and then the Schwenk´s theorem, that reads: “An m x n chessboard with m ≤ n has a knight´s tour unless one or more of the following three conditions hold: a) m and n are both odd; b)m = 1,2, or 4, or c) m= 3 and n= 4, 6, or 8”.

To end the chapter, the case 3 x n, with an approach that works, as an inductive one, start with a tour of a small board and slowly but steadily build larger and larger tours from small tours. Any 3xn board has a knight´s tour for n≥10 and n even, that is, all the boards 3x10, 3x12, 3x14, 3x16, 3x18, etc., have tours.

The chapter contains, moreover, five interesting problems, stated and solved, that cover the different relevant questions.

Chapter 4 does magic squares (pp. 53-63). Claudia Zaslavsky described Muhammad ibn Muhammad´s work on magic squares, dated in 1732, in her book on African mathematics, Africa Counts. He made use of the knight´s move in order to construct magic squares of odd order, squares of size 3x3, 5x5, 7x7, etc. In magic squares, the sum of the numbers in each row, each column, and each of the main diagonals, for 3x3 will be 15; for 5x5 will be 65; and, for 7x7 the sum will be 175. This very same construction was discovered by Bachet en the early 1600s and a nearly identical construction was brought, by de la Loubère. In this chapter, on considered also, semi-magic squares, studied by Euler, Jaenisch, Wenzelides, Mrignac, and others famous mathematicians; and is possible using kings (Ghersi. 1921), and rooks (Rabinoff, 1925) tours, to construct magic squares.

The chapter contains, four interesting problems, stated and solved, that cover the different relevant questions.

In Chapter 5 (pp. 65-77), in the present book, will look many variations on the consideration of chessboards on two surfaces: the torus and the cylinder. On proves that on a torus: “Every rectangular chessboard has a knight´s tour”. As earlier, a knight has significantly more mobility on a torus, and so the knight´s graph for the 4x4 chessboard on a torus is highly richer that on 4x4 chessboard. On a torus each square is now completely equivalent, and so the degree of each vertex will be 4.Moreover, it turns out that the 4x4 toroidal knight´s graph is identical to an extremely famous graph called the 4-cube, or hypercube.

Then we explored the relation between the 4-cube and the Gray codes, invented by Frank Gray in the 1940s, as a way to transmit strings of data so that a small error occurring during transmission will result in only a small error in the received message. Gray listed all the strings in a sequence so that adjacent strings differ in only one position. This Gray code, in fact, corresponds to a Hamiltonian cycle in the hypercube.

To end the chapter, the following theorem (Watkins) solved an exact description of which rectangular chessboards have knight´s tour on cylinders: “An mxn cylindrical chessboard with m rows and n columns, the rows wrapped around the cylinder, has a knight´s tour unless one of the following two conditions hold: a) m= 1 and n>1; or b) m =2 or 4 and n is even”.

This chapter considered six problems and their respective solutions.

Chapter 6, (pp.79-94), deals with the Klein bottle and other variations. The different interesting ways to identify edges, that is, to look at a rectangular chessboard, produced a new surface, called Klein bottle, for example identify the top and bottom edges of the rectangle just as we did for the torus; and also identify the left and the right edges, but in reverse order. The following theorem due to Watkins solved completely the question: “On a Klein bottle, every rectangular chessboard has a knight´s tour”.

The Möbius strip is the most famous example of a one-sided surface. It is also, another way to identify edges in a rectangular chessboard, just one pair of opposite edges as we did for the cylindrical board, but this time to add a half twist just we did for the Klein bottle. Similarly, the following theorem (Watkins) solved the question: “An m x n chessboard on a Möbius strip, with m rows and n columns, the rows wrapped around the Möbius strip, has a knight´s tour unless one or more of the following three conditions hold: a) m= 1 and n>1; or n=1 and m=3, 4, or 5; b) m =2 and n is even, or m=4 and n is odd; c) n=4 and m =3”.

Since about the middle of the nineteenth century mathematician have had a complete list of all possible surfaces. This list is fully described as the Classification Theorem. Surfaces such as the sphere, the torus and the Klein bottle are called closed, that they are finite, also called two-manifolds, and each of these surfaces has a number assigned to it, the Euler characteristic of the surface. Surface such as the plane is infinite or open.

Other variations, such as, the Euler characteristic of the surface, Klein bottle, torus, etc.; the third dimension; boxes; camel piece, a chess piece used in Persian chess (fourteenth century); triangular honeycombs (1997); three dimensional torus, and so on, are also discussed.

Moreover, this chapter considered four problems and their respective solutions.

Chapter 7, (pp.95-111), is related with the classical and interesting, well-known domination problem. The concept of domination is one of the central ideas in graph theory, and is especially important in the applications of the theory to the real world. A set S of vertices in a graph G is called a dominating set if every vertex in the graph is either in the set S or is adjacent to a vertex in the set S. The domination number if a graph is, then, the minimum size of a dominating set in the graph.

In this chapter on analyzed the covering problem. This problem is defined as follows: for each chess piece: how many chess pieces of an individual type are required to cover an nxn chessboard? It is among the oldest and most studied problems related to the chessboard, and it and its many variations, for example: knights, rooks, bishops, and kings.

The chapter contains, moreover, five interesting problems, stated and solved, that cover the different relevant questions.

The chapter 8, (pp.113-137), is devoted to the intriguing and challenging queens domination problem and other variants. The chapter presents the Spencer-Cockatyne construction, upper and lower bound for the number of queens needed to cover an nxn board, Spencer´s remarkable lower bound, Weakley´s new improved lower bound, etc.

The chapter contains, moreover, three interesting problems, stated and solved, that cover the different relevant questions.

The Chapter 9, (pp. 139-162), is related with domination on other surfaces. In this chapter on take another look at the domination problem for each of the chess pieces and consider what happens on the torus and the Klein bottle for the queen, the knight, the rook, the bishop, and the king. More general result about pieces dominating rectangular toroidal chessboards and on a Klein bottle on presented.

The chapter contains, moreover, seven interesting problems, stated and solved.

In the chapter 10, (pp. 163-189), devoted to the independence problem, on analyzed the concept of independence, closely related to that of domination. The concept of independence is also one of the central ideas in graph theory, and is especially important in the applications of the theory to the real world. Two vertices in a graph are independent if there is no edge joining them. A set of vertices in a graph G is said to be an independent set if no two vertices in S are adjacent. The independence number of a graph G is the cardinal of the maximum independence set. An independent set with this maximum size is called a maximum independent set. The 8-queens problem with all solutions; the n-queens problem, and the Ahrens theorem with the proof given by Yaglom and Yaglom, and Pólya´s doubly periodic solutions; independent rooks; independent knights; independent bishops, and independent kings, on presented.

The chapter contains, moreover, seven interesting problems, stated and solved.

The chapter 11, (pp. 191-212), is related to other surfaces and other variations. In this chapter on treated the independence number for each of the chess pieces on a variety of other surfaces, such as the torus and the Klein bottle. It is interesting the following statements: the 8-queens problem on a cylinder; independent kings on a torus; independent kings on a Klein bottle; combinations of two notions of domination and independence: the covering problem; the upper domination number; the irredundance numbers, and the total domination number.

The chapter is illustrated with five problems, stated and solved.

In the chapter 12, (pp. 211-222), is devoted to the study of Latin squares, a classical problem. A Latin square is an nxn array of the integers 0, 1, 2, ... , n-1, or equivalently, a labeling of the squares of an nxn chessboard with these integers, such that each integer appears once and only once in each row, and once and only once in each column. The constructing Latin squares using the Ball´s method; Eulerian squares, that is, two Latin squares of the same size such that the resulting combination by combining their entries and forming ordered pairs, is such that each the possible n2 ordered pairs occurs exactly once, then the two Latin squares are said to be orthogonal, and the new combined square is called an Eulerian square, or sometimes Graeco-Latin square, because Latin letters might be used for one square and Greek letters for the other; Euler´s conjecture impossibility to construct a pair of orthogonal Latin squares, accordingly with the dimensions of boards, in particular 6x6, is wrong. Beyond n=6, that is, n= 10,14,18,22, and so on, there always exists a pair of orthogonal nxn Latin squares for any n.

The chapter is illustrated with three problems, stated and solved.

Finally, chapter 13, (pp. 223-246) is related with two problems concerning geometric dissection problems in recreational mathematics. The first problem is referred to divide the land into four identical pieces with restrictions, and the second problem is to reconstruct the entire chessboard, breaking into eight pieces.

Then analyzed dominoes; dissecting rectangles into dominoes (the bricklayer´s problem); the De Bruijn´s theorem; trominoes; polyominoes; pentominoes; the remarkable three scaling problems involving pentominoes; hexominoes and beyond; the amazing figure of the final chessboard 51x58, that was covered with the 369 octominoes, that 6 of those have holes in the middle.

The chapter is illustrated with seven problems, stated and solved.

References, (pp. 247-249). They are 41 references.

Index (pp. 251-257)

Definitely the book is high recommended and is of much interest. This book is, no doubt, the newly best exposition of the interconnection between amusing recreational mathematics and the interesting chessboard problems.

I feel sure that it will be of great use both to students of graph theory, geometry, topology and mathematics, in general, and captivate to scholars, instructors, chess enthusiasts, puzzle devotees, and to those intervening in amusing and recreational mathematics.

Finally, in short, the great resource to Professor Watkins´s proper tone ensures total attention from the audience to amusing and recreational mathematics, into the adventure proposed, by this challenging and remarkable book.

Reviewer:
Francisco José Cano Sevilla
Affiliation:
Book details

This book is a stimulating and very well written. It is admirably clear. It explains not only methods and results but the motives for choosing, in each moment, various procedures. The material used in the book, is supplemented by excellently chosen exercises, questions or problems, some of which give an insight into other aspects of the proposed chapters. There is a good collection of problems and worked examples, with variations extending to boards of different sizes and shapes.

Across the board is a concise, good, cleared, and indeed, definitive book about questions and problems on chessboard. It is not simply about chess but the chessboard itself, in particular, the intriguing and challenging mathematics behind it. John Watkins, a well-known mathematician, surveys all the problems of interest in this promising area of recreational mathematics. Each main topic is treated in depth from its historical creation through to its status today.

The book contains thirteen chapters, references and an index, in 257 pp. It goes from the basics, classical and variants of the knight´s tour problem, queens domination, magic squares, etc., to the frontiers of research in recreational mathematics, because Watkins uses the visual language of graph theory, and guides perfectly the reader to the frontiers of current research, in news ideas emergent in mathematics, such that, the shape Klein bottle, three-dimensional chessboards and even chessboards on unusual surfaces, toruses and cylinders.
Definitely the book is high recommended and is of much interest. This book is, no doubt, the newly best exposition of the interconnection between recreational mathematics and the interesting chessboard problems. I feel sure that it will be of great use both to students of graph theory, geometry, topology and mathematics, in general, and captivate to scholars, instructors, chess enthusiasts, puzzle devotees, and to those intervening in recreational mathematics.

Author:
Published:
2012
ISBN:
978-0-691-15498-5
Price:
From 14.78$to 18.95$.
Categorisation