


Across the Board: 
This file is also available in Adobe Acrobat PDF format Chapter 1 INTRODUCTION We are no other than a moving row This book is about the chessboard. No, not about chess, but about the board itself. The chessboard provides the field of play for any number of games, both ancient and modern: chess and its many variants around the world, checkers or draughts, Go, Snakes and Ladders, and even the word game Scrabble. Boards for these games come in many sizes: 8 × 8 boards for chess; 8 × 8 and 10 × 10 boards for checkers, depending on what part of the world you are in; 10 ×10 boards for Snakes and Ladders; 15 × 15 boards for Scrabble; 18 × 18 boards for Go; and even nonsquare sizes such as 4 × 8 and 2 × 6 boards for Bau and Owari, two games that are widely played in various forms and under several different names in Africa. In some board games there are no special colors given to individual squares of the board, all squares are the same, but in other games the color of individual squares can be very important. The familiar checkered black and white or black and red alternating coloring of the squares in chess or checkers are the best examples of this. Alfred Butts spent years during the 1930s and 1940s tinkering with the coloring of the board for the game that eventually became Scrabble, deliberating on exactly where the double and triple valued squares should go, what their colors should be, and how many of each type he wanted. We, too, will discover that ingenious colorings of the squares on an otherwise ordinary chessboard can pay surprising dividends. Board games, like other of our games, are usually in some form a metaphor for life itself. Chess, of course, is about war, conquering your enemy and protecting your king; Go is about the territorial imperative; Snakes and Ladders a morality play for children about how to achieve Nirvana. Omar Khayyám, in the two quatrains I quoted for you from The Rubáiyát, saw in such games a reflection of our lives as mere 'pawns' in a game run by the 'Master of the Show', a theme picked up by Shakespeare 300 years later in As You Like It, the play with which he possibly opened the Globe Theatre in 1599: All the world's a stage, Even now, in an age, and especially in a society, such as ours, in which the problematic notion of free will is simply taken for granted, this is still an idea that carries a chilling weight. However, this is not a book about such games, and still less is this book concerned with the cultural significance of the games we humans play. Instead, this book is about the game board itself, the simple grid of squares that forms such a common feature of games played around the world, and, more importantly, about the mathematics that arises from such an apparently simple structure. Let us begin with a puzzle. Guarini's Problem The earliest chessboard puzzle that I know of dates from 1512, almost 500 years ago. This puzzle is known as Guarini's Problem and involves four knights, two white and two black, at the four corners of a small 3 × 3 chessboard. The white knights and the black knights wish to exchange places. Their situation is shown in Figure 1.1. A knight can move on a chessboard by going two squares in any horizontal or vertical direction, and then turning either left or right one more square. Since, in this problem, each knight will have only two moves available from any position, this is a very simple puzzle to solve, even by trial and error. Still, it is somewhat harder than it might look at first glance, so I urge you to try to do it for yourself before reading on. If you solved this problem you undoubtedly observed its underlying basic structure. Note that this rather simple structure comes from two things: the geometry of the board itself along with the particular way in which knights are allowed to move. In Figure 1.2, the structure of the possible knight moves is first exhibited explicitly, on the left, by lines that are drawn to connect any two squares of the board between which a knight can move. This diagram, or graph, can then be 'unfolded', as shown on the right in Figure 1.2, and the underlying structure of the graph immediately emerges. The graph, which looked somewhat complicated to us on the left, turns out to consist of only a single cycle, and so the solution to our puzzle is now completely clear. In order to exchange places, the knights have no choice at all. They must march around this cycle, all in the same direction, either clockwise or counterclockwise, until their positions are exactly reversed. This graphical solution, of course, still has to be translated back to the original 3 × 3 chessboard, but this final step is quite straightforward. I like Guarini's Problem in part because it is so very old, but also because it is such a nice illustration of the way in which mathematical abstraction can clear away the messy details of a problem and lead us gently toward a solution. In the case of Guarini's Problem, the first level of abstraction avoids for us the need to keep worrying about the awkward business of how a knight moves on a chessboard by the simple device of drawing lines on the board to represent these moves. This allowed us to forget about chess completely. The next level of abstraction is to forget also about the actual board and focus instead entirely on the diagram. Then, the final level of abstraction is to eliminate the clutter inherent in the diagram simply by unfolding it. This general process of turning a problem into a diagram is so useful and so natural that an entire area of mathematics, now called graph theory, has evolved that is dedicated to studying the properties and uses of such diagrams, called graphs. This book, then, is really a book about graphs in disguise. Usually, explicit graphs such as the one drawn in Figure 1.2 will be kept offstage during our drama, but rest assured, they are always there and ready to appear at a moment's notice should we ever have need of them. Problem 1.1 In Figure 1.3 we now have six knights, three white and three black, on opposite sides of a 4 × 3 chessboard. Find the minimum number of moves required for these knights to exchange places. This variation of Guarini's Problem appeared in Scientific American in the December 1979 issue. A solution was given the following month. Remember though that you can, if you like, find solutions to these problems at the end of each chapter. The Knight's Tour Problem Since we have just studied a problem involving knights, and we now know how they move, let's continue with them for the moment. Note that in Guarini's Problem the center square of the 3 × 3 chessboard is inaccessible to any of the four knights, but that otherwise a single knight could visit each square of the board exactly once and return to its original position merely by making a complete circuit of the cycle graph in Figure 1.2. What about on a larger board, such as a 4 ×4 board or an 8 ×8 board, might a knight be able to do a tour of the entire board, that is, visit every square exactly once and return to the start? The answer is: well, sometimes yes, and sometimes no. The general question of which chessboards have a knight's tour is known as the Knight's Tour Problem. This famous problem has a long and rich history. The Knight's Tour Problem dates back almost to the very beginnings of chess in the sixth century in India and will in fact be one of the main topics considered in this book. You might wish to try the following problem before continuing further. The key feature of a knight's tour is that a knight visits each square of the board exactly once. A tour can be closed, meaning the knight returns to its original position, or it can be open, meaning it finishes on a different square than it started. Unless otherwise indicated, the word 'tour' in this book will always mean a closed tour. Problem 1.2 The smallest chessboards for which knight's tours are possible are the 5 × 6 board and the 3 × 10 board. Find a tour for each of these boards. The smallest board for which an open tour is possible is the 3 × 4 board. Find an open tour for this board. Leonhard Euler, perhaps the most prolific mathematician of all time, did extensive work on the Knight's Tour Problem. One particularly attractive knight's tour for the 8 × 8 chessboard, done by Euler in 1759, is shown in Figure 1.5. What is especially interesting about this particular tour is that Euler first does an open tour of the lower half of the board, starting at square 1 and ending at square 32. He then repeats exactly this same tour, in a symmetric fashion, for the upper half of the board, starting at square 33 and ending at square 64. Note that Euler has also very carefully positioned both the beginning and the end of these two open halftours so that they can be joined together into a tour of the entire chessboard. This tour of Euler's tells us something very useful about the Knight's Tour Problem, at least we now know for sure that the 8 × 8 chessboard has a knight's tour. On the other hand, we already know that not all chessboards have knight's tours. For example, as we have seen, the 3 × 3 board can't have a tour for the simple reason that the center square is inaccessible. A more interesting, and much more surprising, example is the 4 × 4 board. A quick glance at the graph in Figure 1.6 shows why a knight's tour is impossible for this chessboard. The two bold lines, or edges as they are usually called in graph theory, coming from the upper lefthand corner represent the only possible way for a knight to get into or away from that particular corner square. Thus, both of these bold edges must be a part of any knight's tour of the entire board. For exactly the same reason, the two bold edges coming from the lower righthand corner must also be part of any tour of the entire board. But, as we can easily see, these four bold edges form a small closed cycle visiting just four squares, which means that they cannot simultaneously also be part of a larger tour of the entire board. So, because of this unavoidable conflict, a tour of the entire 4 × 4 board is impossible. Are there any other chessboards on which a knight's tour is impossible? In order to answer this question, it is going to turn out to be useful for us to color the squares of our chessboards, as we shall see. Coloring Chessboards Omar Khayyám used the black and white 'chequer'board pattern of the chessboard to represent nights and days in the passage I quoted earlier from The Rubáiyát, thereby invoking a disturbing sense of the endless cyclic repetitiveness of life. These days, we see the checkerboard pattern used so often for decorative purposeson taxicabs, on table cloths in Italian restaurants, for tiling floors, for the checkered flags at auto racesthat it will seem quite amazing to us how wonderfully useful this pattern also turns out to be for purely mathematical purposes. This is a theme to which we will return again and again. But, for now, let's use coloring to see how to find infinitely many chessboards that can't possibly have knight's tours! Up to this point, of course, we have not bothered to color the squares on any of our chessboards. But now, look at the 5 × 5 chessboard in Figure 1.7, where we have colored the squares in the usual way. The main thing to note is that a knight on this board always moves from a square of one color to a square of the other color. You should verify this for yourself. Therefore, a knight's tour necessarily alternates between black squares and white squares; and so, a knight's tour must consist of an equal number of black squares and white squares. But, the 5 × 5 chessboard doesn't have an equal number of black squares and white squares! In fact, our 5 × 5 chessboard has 12 white squares and 13 black squares. And so a tour of the 5 × 5 chessboard is impossible. The same argument, of course, works for any 'odd' chessboard, such as a 13 × 17 board, where both of the dimensions are odd, simply because in that case the total number of squares would also be odd, and so the number of black squares could not be equal to the number of white squares. Thus, there are infinitely many chessboards for which a knight's tour is impossible. Playing on Other Surfaces It may have occurred to you, however, that just because there isn't a closed knight's tour for a 5 × 5 chessboard doesn't mean that there can't be an open knight's tour. After all, couldn't an open tour begin on a black square and then also end on a black square and in that way successfully alternate 13 black squares with 12 white squares? This is indeed possible! One such tour is shown in Figure 1.7. This particular open tour suggests a natural extension of the Knight's Tour Problem, or at least it suggests something that might seem natural to anyone who has spent a significant amount of time playing video games. What if we change the rules for the knight and now allow the knight to move o3 the bottom of the board and then reappear at the top, exactly as happens in some video games? Or if we allow the knight to go o3 of one side of the board and instantly reappear at the other side? This is not an idea that would have seemed particularly natural to Euler in the middle of the eighteenth century when he was playing with knight's tours, but it certainly seems natural to us now. With this newfound, computeraided freedom, the poor knight who was previously stuck at square 25 in Figure 1.7 can now happily return to square 1 in a single move, thus closing the tour. In this particular situation, a mathematician might say we were playing chess on a flat torus. As we shall see later, this is actually the same as playing chess on the surface of a doughnut! Since I intend for us to be investigating knight's tours on a wide variety of strange surfaces like the torus, you should perhaps warm up a bit first on the following problem. Problem 1.3 Find a knight's tour on the surface of a 2 × 2 × 2 cube. This needs some explaining. First of all, this cube has only four squares on each face and so if a knight is to move at all it must be able to pass over an edge of the cube onto another face. So, we will agree ahead of time that a knight moves over an edge of the cube without even noticing it. The various possible knight moves will be far easier to visualize with an actual cube in your hand, such as a Rubik's Mini Cube, and using a waterbased pen to record the moves. A reasonably good alternative is to use the unfolded diagram of the cube shown in Figure 1.8 as a visual aid. For clarity, we should also agree on exactly what constitutes a knight's move. I earlier described this move as being 'two squares in one direction followed by one more square either left or right'. On a flat board this happens to be the same as saying 'one square in one direction followed by two more squares either left or right'. But on a 2 × 2 × 2 cube these two 'moves' don't always turn out to be the same. Since it is pretty hard to argue that either one or the other of these two 'moves' is the real knight's move, I will arbitrarily decree that you can use both. You might want to check that a knight at any position, therefore, has a total of ten possible moves. With that much mobility, this shouldn't be a hard problem! The Domino Puzzle We have just seen how the standard checkerboard pattern of alternating black and white squares can be used to show that chessboards having odd dimensions cannot possibly have knight's tours. Here, now, is a clever, and quite well known, puzzle that also illustrates the usefulness of coloring. This puzzle involves dominoes. You may well have seen this puzzle before, but it still provides us with a good introduction to a large class of interesting geometric problems. A domino, for us, is just a 1 × 2 rectangle. We are not interested in any spots it may have, just its onebytwo rectangular shape. If the size of our dominoes exactly matches the size of two adjacent squares on our chessboard, then we can easily see that an 8 × 8 chessboard can be 'covered' with 32 dominoes. No problem! Here is the wellknown Domino Puzzle : remove two diametrically opposite corner squares from an 8 × 8 chessboard; can you cover the 62 remaining squares of the chessboard with 31 dominoes? It seems as if you should be able to do this, after all, 2 · 31 = 62, but I do not recommend spending very much time trying to do itwell, maybe a littlebecause you are doomed to failure. Instead, try to visualize the checkerboard pattern of the 8 × 8 chessboard, or, better yet, look at an actual chessboard. All you have to do is note that the two diametrically opposite corner squares that have been removed from the original chessboard have the same color! So, we now have 32 squares of one color, but only 30 squares of the other color. Clearly, then, since a domino covers one white square and one black square, it is impossible to cover the remaining 62 squares with 31 dominoes. I have always observed that what makes the Domino Puzzle so successful as a puzzle is that people tend to concentrate mostly on the rather bizarre geometric shape of the board once the two opposing corners have been removed, so they approach the problem geometrically. Moreover, the checkerboard pattern is such a familiar design in our daily lives, one which is so frequently encountered that we hardly notice it, and so the color of the squares in this puzzle seems irrelevant. On the other hand, what if we start over with this same puzzle and remove, say, the upper lefthand corner square and the upper righthand corner square? Then, as we expected all along, it is a piece of cake to cover the remaining board with 31 dominoes. What if we make things a little harder and instead remove a single black square and a single white square from random positions on the board? Can we still always manage to cover the remaining board with 31 dominoes? Happily, the answer is: yes. In other words, the following remarkable theorem is true. Theorem 1.1 (Gomory's Theorem) If you remove one black square and one white square from anywhere on the 8 × 8 chessboard, then you can cover the remaining board with 31 dominoes. It is surprisingly easy to give a proof of this theorem. In order to do so, I first need to return to the idea of a tour of a chessboard. This time, however, I want to be thinking of a rook's tour rather than a knight's tour. A rook can move in either a horizontal or a vertical direction and it can also go as many squares as it wants. For our purpose, which, after all, is touring chessboards and visiting squares, it is best to think of the rook as moving just one square at a time. In other words, when a rook moves along a row or column it 'visits' every square along the way. Armed with this knowledge of how a rook moves, I am sure you will have no trouble finding a rook's tour of the 8 × 8 chessboard. Spend a moment and do this. You probably came up with something like the rook's tour illustrated in Figure 1.9. Now, using the rook's tour in Figure 1.9, we can give the easy proof of Gomory's Theorem I promised you. First, I suggest you try to ignore completely the fact that this is happening on a chessboard at all and instead just think about the tour itself, which, after all, is just one very long, very big cycle with the rook marching merrily along from square to square: black square, white square, black square, white square, black square, white square, until finally the rook gets back to the original starting square. Now, if a black square is removed from anywhere along this cycle, then the cycle stays connected in one piece, but is now open with a white square at each end. If a white square is now removed from somewhere along this piece, then we will be left with two pieces (unless, of course, we remove one of the two white ends, but then the argument becomes even easier). We can see that each of these two pieces is now white at one end and black at the other end. So, each individual piece can be covered with a string of dominoes, each domino covering one white square and one black square, and we are done with the proof. If this argument wasn't clear to you, try thinking of a necklace with 32 black beads alternating with 32 white beads. Cut one black bead out of the necklace and visualize what you are left with, and then also cut one white bead out and visualize the two remaining pieces. That's all there is to it. There were two keys to the unlocking of Gomory's Theorem: first, our very good friend the standard checkerboard coloring of the chessboard; and, second, the extremely convenient fact that the 8 × 8 chessboard has a rook's tour. Figure 1.10 presents several attractive rook's tours of the 8 × 8 board in a slightly different form, including the original tour from Figure 1.9 on the left in this new form. You may want to look for a few more tours. There are lots of them. We will return later in the book to the topic of covering chessboards with 'ominoes' in all manner of sizes: monominoes, dominoes, trominoes, tetrominoes, pentominoes, and so on. In the meantime, here is another problem involving 'ominoes' for you to work on. Problem 1.4 Figure 1.11 shows the five tetrominoes, that is, the five connected figures that cover four squares of a chessboard. Note that two of these tetrominoes look different if you turn them over, but they are still considered to be the same tetromino. If you take sixteen of the straight 1 × 4 tetrominoes, you can easily cover the 8 × 8 chessboard with them. Similarly, for the square 2 × 2 tetromino, with sixteen of them you can also easily cover the 8 × 8 board. Which of the other three tetrominoes can be used to cover the 8 × 8 board in this way, that is, using sixteen copies of the same tetromino? Here is a slightly different covering problem: can you cover the 4 × 5 board using each of the five tetrominoes? What about a 2 × 10 board? Don't forget that you can place a tetromino with either side facing up. Domination In the previous section, we talked about a certain kind of 'covering' for chessboards in which a chessboard was literally covered by various geometric shapes such as dominoes or tetrominoes. I'd like to turn now to a consideration of a very different kind of 'covering' for a chessboard. We begin our discussion with queens. The queen is by far the most powerful piece in chess, combining as it does the strength of the rook, which moves any distance it likes horizontally or vertically, with that of the bishop, which moves any distance it likes diagonally. Depending upon which square it is placed on, a single queen can cover or control anywhere from 22 to 28 squares of the chessboard. Now that is power. In fact, the four queens in Figure 1.12 together control almost the entire board, only the two shaded squares escape their control. (I can't resist interrupting myself to point out that if the board in Figure 1.12 were on a flat toruswhere, remember, queens could go o3 the board on one side and reappear at the opposite sidethen the two shaded squares would already be covered! Do you see how? In other words, the entire board would be covered by just these four queens. End of interruption, we now return to regular chessboards.) Since only two squares are uncovered in Figure 1.12, it is easy to place a fifth queen on the board so that the entire board is covered or controlled by these five queens. Unfortunately, it is not at all easy to prove that you actually need five queens in order to cover the 8 × 8 chessboard. This is the case, however. We will come back to this and other questions about queens later in the book. In the meantime, because it will prove to be a far easier question to answer, let us ask the same question about kings: how many kings do you need to cover an 8 × 8 chessboard? The king, like the queen, can move in any direction, but is far more limited than the queen, being able to move only one square, that is, to an immediately adjacent square. Thus, a king can cover at most nine squares, namely, the 3 × 3 portion of the board in which it is centered. It is easy to see, then, that nine kings can be placed so as to cover an 8 × 8 chessboard, for example, as arranged in the diagram on the left in Figure 1.13. But, do you need nine kings in order to cover the board? The answer is: yes, you do. This turns out to be easy to show. Consider the nine shaded squares in the diagram on the right in Figure 1.13. No matter where you might decide to place a king on this board, a single king would cover at most one of these shaded squares. In other words, a king could never cover two of the shaded squares at the same time. Therefore, you need at least nine kings merely to get the shaded squares covered, and hence, you need at least nine kings to cover the entire board. Note that in addressing the question: 'how many kings do you need to cover an 8 × 8 chessboard?', we had to do two different things in order to conclude that 'nine' is the correct answer. We had to demonstrate that the answer was 'nine or less' by actually covering the board with nine kings. We also had to demonstrate that the answer was 'nine or more' by some other kind of ad hoc argument; in this case, a rather clever argument involving shaded squares did the trick. Since we could do both of these things, the answer ended up being 'nine'. In the kind of covering problems we have just been looking at we are seeking the minimum number of pieces of a given type needed to cover or control the entire board. How many bishops do you 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 realworld applications. However, it is worth remembering that domination problems first originated when people began asking 'covering' questions about chess pieces. Even the aggressive sound of the term 'domination' should serve to remind us that domination in graph theory is a topic that had its origins in chess, which, after all, began so many centuries ago as a game of war. Independence We now turn to another large and important category of problems. In these problems we will ask questions that are similar to those that we have just met in domination theory, but that have a kind of reverse spin. For example, what is the maximum number of knights that you can place on an 8 × 8 chessboard so that no two knights attack one another? You might want to think about that for a moment before continuing. We will call a group of knights independent if none of them attacks any other. So, questions like the one we have just posed are referred to as independence problems. In order to answer this particular question about placing independent knights on a chessboard, we have to do two different things, just as was required of us in answering domination problems. First, we have already noted that a knight on, say, a black square, can only move to a white square, so if we place 32 knights on the 32 black squares, then no two knights can attack one another. So, these 32 knights are independent. It would seem pretty obvious that surely this must be the best that we can do, but how do we go about proving it? That is the second thing we have to do. Here is one way to do that. Thanks to the work of Euler, we have already seen that the 8 × 8 chessboard has a knight's tour and we have also observed that this tour alternates between black and white squares. Since we can't place two independent knights on 'adjacent' squares anywhere along this tour, we can place at most 32 independent knights along the tour. So, 32 is the best that we can hope to do. This argument gives us a bonus that we weren't even looking for: because the tour alternates between black and white, the 32 knights must either all go on the black squares or they must all go on the white squares. In other words, the easy placement we first thought ofthat is, putting all the knights on one colorwas, in fact, the only solution. Here is an alternative argument that 32 is the best that we can do. First, divide the board into eight 2 × 4 rectangles. Since a knight placed anywhere within one of these 2 × 4 rectangles covers exactly two squares in the 2 × 4 rectangle, at most four independent knights can be placed in each rectangle. But there are eight such rectangles, and so we can't possibly fit more than 32 independent knights on the chessboard. We will return to both domination problems and independence problems in considerable detail later, but for now, here is a problem for you to do. Problem 1.5 Place eight bishops on the 8 × 8 chessboard so that they dominate the entire board. Place fourteen bishops on the 8 × 8 chessboard so that they are independent. In each case, this is the best that can be done. A reminder: a bishop moves as many squares as it likes along a diagonal path. Note that a bishop always remains on squares of the same color. GraecoLatin Squares We have at this point introduced the main topics with which we will be concerned in this book: knight's tours, domination, independence, coloring, geometric problems, chessboards on other surfaces, and even polyominoes. But a subject as broadand as vaguely definedas 'chessboards' also contains within its scope plenty of room for a large number of miscellaneous topics and problems that, while not particularly easy to categorize, are nonetheless worthy of our attention. I'd like to conclude this introduction by turning briefly to such a topic now. The very first time I saw one of Martin Gardner's Mathematical Games columns was in the November 1959 issue of Scientific American. The topic of this column was GraecoLatin squares. They even had a painting on the cover of that issue that had been inspired by his column, a large 10 × 10 grid that looked like something that might have been painted by Piet Mondrian. That's about all I'm going to tell you about GraecoLatin squares for now. It turns out that the painting on the cover of the magazine, and Gardner's column on the inside, were nothing less than a stunning announcement that a very famous conjecture that had originally been made by Leonhard Euler and that had survived unscathed for nearly 200 years had finally just crashed spectacularly to defeat. As to what a GraecoLatin square actually is, I'll let you discover that for yourself by doing a puzzle that was popular in the eighteenth century, called Ozanam's Problem. Problem 1.6 Take all four aces, all four kings, all four queens, and all four jacks from a single deck of playing cards. Arrange these sixteen cards in four rows and four columns so that each row and each column contains all four card values as well as all four suits. If you succeed in doing this, you will have created a GraecoLatin square of order 4. Martin Gardner even tossed in an extra challenge: arrange the cards so that the two diagonals of the square also satisfy this same condition. Solutions to Problems Solution 1.1 In Figure 1.14 we first draw the knights graph in its natural position on the chessboard and also at the same time number the squares of the board in a convenient fashion. We then, of course, unfold the graph. We can immediately see that it takes seven moves just to move the three black knights into the correct position; and, by symmetry, there is really only one way to do this: bring the knight at 5 straight down to 8 and move the other two knights two squares each, that is from 3 to 1 and from 12 to 10. And so, we might hope to do the complete switch of all the knights in just fourteen moves, seven for each color, but unfortunately we can't move both the black and the white knights in these seven moves without the knights getting in each other's way. What we can do however is have one knight take a single step backwards at an appropriate time to clear the way for an opposing knight. The result will be a loss of only two moves, which is the best we can hope for. Here, then, is a sixteenmove solution: the black knight at 5 moves down to 7; this allows the white knight at 1 to move into place at 5, which allows the black knight at 3 to move into place at 1, which then allows the white knight at 10 to move straight into place at 3, and in turn the black knight at 12 to move into place at 10. So far, this has been perfectly efficient, but now the black knight at 7the polite knight, if you willsteps back to 6, allowing the white knight at 8 to move into place at 12, before continuing his otherwise straight path down to 8. Solution 1.2 The solutions for this problem are given in Figure 1.15. Solution 1.3 The strategy here is to do an open tour of the front three faces (squares 112 in Figure 1.16). Then repeat this exact same open tour on the back three hidden faces (squares 1324). Finally, these two open tours can be linked with knight's moves at squares 1213 and at squares 241 to complete the tour of the entire 2 × 2 × 2 cube. This particular solution of course imitates Euler's tour of the 8 × 8 board given in Figure 1.5. Another solution uses an idea given by Ian Stewart in Another Fine Math You've Got Me Into [28]. At the heart of this solution is the following very beautiful idea from geometry: if you hold a 2 × 2 × 2 cube so that one of its main diagonals is vertical and then cut the cube exactly in half with a horizontal slice, the crosssection you get will be a hexagon. In fact, the sides of this hexagon are nothing but the diagonals of the six 1 × 1 squares bisected by the horizontal slice, as shown in Figure 1.17. Now, here is the nice surprise. This hexagon just happens to form a small knight's minitour, which has been labeled A_{1},A_{2},...,A_{6 } in Figure 1.17. Furthermore, since a cube has four main diagonals, we can in this way construct four distinct hexagons and, hence, four distinct knight's minitours. The remaining three minitours have been labeled B_{1},B_{2},...,B_{6};C_{1},C_{2},...,C_{6}; and D_{1},D_{2},...,D_{6 } in Figure 1.17. These minitours are, of course, closed 6cycles which must be joined together in some way. But, note that >A_{6}B_{1}, B_{6}C_{1}, C_{6}D_{1}, and D_{6}A_{1 }are all legal knight's moves on the 2 × 2 × 2 cube. Thus, we can form the following knight's tour of the entire 2 × 2 × 2 cube: A_{1},A_{2},...,A_{6},B_{1},B_{2},...,B_{6},C_{1},C_{2},...,C_{6},D_{1},D_{2},...,D_{6},A_{1}. Solution 1.4 The 8 × 8 board can easily be covered by either sixteen L tetrominoes or by sixteen T tetrominoes; the simplest ways to do this are shown in Figure 1.18. On the other hand, it is impossible to cover the entire 8 × 8 board using only Z tetrominoes. Suppose you were to start by covering the upper lefthand corner square with a Z tetromino placed horizontally. This would then force you to place another one right next to it, also along the top row, and then a third one is forced as well. But then you are really completely stuck, since there is no way to cover the remaining two squares at the end of the top row. Of course, it makes no difference if you begin in the upper lefthand corner by orienting the first tetromino vertically. The same difficulty arises along the left edge. It is also impossible to cover either a 4 × 5 or a 2 × 10 board with the five distinct polyominoes. A checkerboard coloring of either of these boards has ten white squares and ten black squares. Now, it is easy to see that no matter how you place them on the board, the square tetromino, the straight tetromino, the L tetromino, and the Z tetromino each cover exactly two white squares and two black squares. However, the T tetromino always covers three squares of one color and one square of the other color. So, it is impossible for all five tetrominoes to cover an equal number of white squares and black squares. Solution 1.5 The solutions for this problem are given in Figure 1.19. Solution 1.6 The solution for this problem is given in Figure 1.20.
File created: 8/7/2007 Questions and comments to: webmaster@pupress.princeton.edu 