Copyright © Karl Dahlke, 2022
Consider the knight's tour problem. Can a knight travel around the chess board, landing on each square exactly once? ♞ This would be incredibly tedious to work out by hand, but a simple computer program finds a solution in a few minutes. I'll print the solution here, in algebraic notation, so you can verify it. If you started playing chess in the 60's or earlier, you might remember the old clunky notation: rook to queen's bishop 5, or rqb5, but even that wasn't sufficient if there were two rooks that could land on the same square. So they switched to algebraic in the 70's, which is basically battleship, a through h (rook to rook), and 1 through 8 up the board. Here is the knight's tour, starting at the lower left and ending at the upper left. Grab a chess board and a knight and give it a whirl.
a1 c2 e3 g4 h6 g8 e7 c8 a7 b5 d6 f7 h8 g6 f8 d7 b8 a6 c7 e8 f6 h7 g5 e6 g7 f5 d4 c6 d8 b7 a5 b3 c5 a4 b2 d1 c3 b1 a3 c4 e5 d3 e1 g2 h4 f3 h2 f1 d2 e4 f2 h1 g3 h5 f4 h3 g1 e2 c1 a2 b4 d5 b6 a8
Here is the program that finds the above solution. Pass it the arguments 8 8 0 0 for an 8 by 8 board starting at the lower left.
Ok, all programming and no math is pretty dull, so let's explore some smaller boards from first principles. Can a knight travel around a 3 by 3 grid? No, because if it starts in the center it has no place to go, and if it starts on the edge it can never get to the center. A 4 by 3 board, 4 across and 3 high, works, I'll leave that one to you. Hint: start at the lower left and end at the upper right.
Place two such boards together, end to end, giving an 8 by 3 field. Cover the first board as above, then jump to the lower left of the second board, and cover it as above. You can chain n such boards together, hence a 4n by 3 board works.
A 7 by 3 board has this tour, from lower left to an interior square at the right: a1 c2 a3 b1 c3 a2 c1 b3 d2 f3 g1 e2 g3 f1 e3 g2 e1 d3 b2 d1 f2. Put additional 4 by 3 boards on the left, and chain them together, and every 4n+3 by 3 board works (n positive).
An n by 2 board never works, because if the knight starts at the lower left, it keeps moving to the right forever.
How about a 4 by 4 board? One corner might start, and one corner might end, but at least 2 corners are in the middle of the tour. Assume one of these is the lower left, thus the knight jumps from c2 to a1 to b3. d4 cannot be in the middle of the tour, for that would also consume c2 and b3, whence only those 4 squares are in the circuit. Thus d4 starts or ends the tour. We can safely say the tour starts: d4 c2 a1 b3. In the same way, the tour ends with b2 d1 c3 a4, or these four possibly in a different order. The 8 moves in the middle of the tour consume the 8 side squares. If you jump from b3 to c1, you are forced to run a circuit of four, clockwise or counterclockwise, e.g. c1 d3 b4 a2 c1. The same thing happens if you jump from b3 to d2. Thus we cannot tour the 4 by 4 board.
A 5 by 5 board works: a1 c2 e3 d5 b4 a2 c3 d1 b2 a4 c5 e4 d2 b1 a3 b5 d4 e2 c1 b3 a5 c4 e5 d3 e1. If there are 13 black squares and 12 white, the tour has to start and end on black. Thus the knight cannot jump from the last square to the first, completing a circuit. We can run a tour, but not a circuit. An odd number of squares never allows for a circuit.
With the tricks at hand, you should be able to prove the 5 by 3 board is impossible.
By the black and white argument, you can't start or end on a2. The tour runs … c1 a2 c3 … Similarly, e2 is in the middle of the tour. That builds the 4 cycle c1 a2 c3 e2 c1.
Here is 9 by 3, which is, happily, from lower left to upper right.
a1 c2 a3 b1 d2 b3 c1 a2 c3 e2 g3 i2 g1 h3 i1 g2 e3 f1 h2 f3 e1 d3 b2 d1 f2 h1 i3
Chain additional 4 by 3 boards on the end, and 4n + 9 by 3 works.
How about a 6 by 3 board? This one is tricky. If a2 and e2 are both in the middle of the tour, then we have the 4 cycle: a2 c1 e2 c3 a2. Thus either a2 or e2 starts or ends the tour. In the same way, either b2 or f2 starts or ends the tour. Each of the 4 corners is in the middle of the tour. The tour includes b1 a3 c2 a1 b3 (or its reverse), and e1 f3 d2 f1 e3 (or its reverse). We can't start or end at b1, so connect it to c3. Then connect b3 to c1. c1 and c3 cannot start or end the tour, so one connects to a2 and the other to e2. We have a subtour of length 9, and it cannot connect to the other subtour of length 9.
Here is the 10 by 3 board, again, from lower left to upper right.
a1 c2 a3 b1 d2 b3 c1 a2 c3 e2 g3 i2 g1 f3 e1 g2 i3 j1 h2 f1 e3 d1 b2 d3 f2 h1 j2 h3 i1 j3
This extends to 4n+10 by 3, and that completes all boards of height 3. A board works if its length is 4, or ≥ 7.
Return to the 8 by 8 chess board. A rook can start at a1 and tour the entire board, and even return to a1. (I'll leave that one to you.) A queen or king could do the same thing, and even a pawn if you let the pawn turn into a queen when it reaches the eighth row. A bishop can't tour since she always has to stay on her own color. A bishop can't tour all the black squares. It's a relatively easy proof; I'll leave it to you. Hint: it would have to start at one corner and end at the other.
Can a knight tour the chess board and then return to start, a circuit if you will? Run the program with arguments 8 8 - -, the dashes indicating a circuit, and the answer is yes.
a1 c2 e3 g4 h6 g8 e7 c8 a7 b5 d6 f7 h8 g6 f8 d7 b8 a6 c7 a8 b6 a4 c5 e6 g7 e8 f6 h7 g5 e4 c3 d5 b4 a2 c1 e2 d4 f5 h4 g2 e1 d3 b2 d1 f2 h1 g3 h5 f4 h3 g1 f3 h2 f1 d2 b1 a3 c4 e5 c6 d8 b7 a5 b3
We analyzed all boards of height 3; how about boards of height 4? Boards of width 1 and 2 fail trivially, 3 works, and 4 fails, as shown earlier. 5 works: a1 c2 e1 d3 b4 a2 c1 e2 d4 b3 d2 e4 c3 b1 a3 c4 e3 d1 b2 a4.
Recall the strategy we used for boards of height 3. We chained boards of width 4 together to analyze boards of widths 4n, 4n+1, 4n+2, and 4n+3. You might want to do the same thing here, perhaps using blocks of width 5, but you can't. In fact there is no way to chain blocks together, of any width. Color arguments will force us down a different path.
Color the top and bottom stripes red, and the middle two stripes green. The knight always has to move from red to green. Write the tour as a sequence of colors rgrggrgggrgr… At the end, there are equal numbers of greens and reds. If, at any point in the sequence, green exceeds red by 2, then there will always be more green than red, all the way to the end. This is a contradiction. If you start with g then the next color is r, then grgrgrgrgr all the way to the end. We never jump from green to green. If you start with red, then you can have one gg jump. After that, red and green alternate, ending in red. Those are the only possibilities. The 5 by 4 solution shown above looks like this. rgrgrgrgrggrgrgrgrgr
Next, overlay a white and black checkerboard on the green stripes. The red stripes do not participate. Look at an alternating sequence like grgrgrg… If the first square is white then all the g squares are white. If your tour starts with g, then all the g squares are white, and that is impossible. Therefore the tour starts with r.
For a while, all the g squares are white, until you run into the one and only gg jump. After that all the g squares are black. At the end of the sequence, black equals white. Therefore there is one gg jump, and it occurs exactly in the middle. The tour can be summarized: rgrgr…gg…rgrgr.
We start on red, and end on red. A circuit is not possible, since you cannot jump back from r to r. Also, a chain of two blocks is not possible. The first block ends on r, and the second block starts on r, and we cannot jump from r to r. Thus chaining does not work. Each x by 4 board is one big tour.
Start the tour in the lower left, with a component like this. a1 c2 b4 a2 c1 b3. From here we can jump to d4, and start the next component upside down. d4 f3 e1 d3 f4 e2. From here we can jump to g1 and start the next component right side up. This continues for multiples of 3. Notice there are no gg jumps.
Let the tour end at the upper left, designated a4. Walk backwards from the end of the tour, building the upside down component a4 c3 b1 a3 c4 b2. This leads to the next component, and the next, and so on. After some multiple of 3, we have the start of the tour ending at, say, t3, and the end of the tour starting at t2. In fact, t3 must jump to v4, and v1 jumps to t2. Thus we need a tour from v1 to v4, and that completes the board. We saw this earlier with a block of width 5, from columns v to z for example. Thus there is a solution to the board of width 26, or more generally, 3n+5.
If we can find tours for the boards of width 6 and 7, starting at a1 and ending at a4, then we are done with height 4. Once again the computer helps us out here.
a1 c2 b4 a2 c1 e2 f4 d3 e1 f3 d4 b3 d2 f1 e3 c4 a3 b1 c3 e4 f2 d1 b2 a4
a1 c2 d4 b3 c1 e2 g1 f3 e1 g2 f4 d3 b4 a2 c3 e4 g3 f1 d2 b1 a3 c4 e3 g4 f2 d1 b2 a4
For boards of height 5, chaining works again. Use this block of width 4. Then chain blocks together for boards of width 4n.
a1 c2 d4 b5 a3 b1 d2 c4 a5 b3 c5 a4 b2 d1 c3 d5 b4 a2 c1 d3
Next, we need to solve boards of width 5 6 and 7. Once again the computer provides solutions. The 5 by 5 solution starts at the lower left and ends at the lower right. Reflect the 4 by 5 board above, and put it next to this board, and chain, giving a solution to the 9 by 5 board. Keep chaining, thus covering 4n+5 by 5.
The solutions for 6 by 5 and 7 by 5 also support chaining to the right.
Sometimes we can chain blocks together to create a row, then stack rows on top of each other to make a larger board. Recall the tour of the 7 by 3 board. It starts at a1 and ends at f2. Chain additional boards on the left, to tour a 4n+7 by 3 board. Reflect this pattern, and place it on top of the first, and the knight can tour the 4n+7 by 6 board. In general we have a solution to every board that is 4n+3 by 3m, n and m positive.
Here is a tour of 8 by 3 that goes from an interior square to lower right. Use this to chain, and stack, and tour any board that is 4n+4 by 3m, n and m positive.
b2 d3 c1 a2 c3 b1 a3 c2 a1 b3 d2 f1 h2 f3 e1 g2 e3 d1 f2 h3 g1 e2 g3 h1
There is a 9 by 3 tour, from one corner to an interior piece at the other end, and that is enough to chain and stack. Boards that are 4n+5 by 3m, n and m positive, are covered.
a3 b1 d2 f3 e1 d3 b2 d1 f2 h3 i1 g2 i3 h1 g3 i2 g1 e2 c3 a2 c1 b3 a1 c2 e3 f1 h2
With a little more work, you might be able to write a program that, given the dimensions of a rectangular board, cranks out a knights tour on that board in polynomial time, or declares the tour impossible, as on a 3 by 3 board. That would be a fun project.
There is more to explore here, but I'll stop for now. None of this helps feed the hungry, but it is good training in logic and formal proofs. If you're a high school teacher, and you are able to take a break from algebra or trigonometry, your students might enjoy this recreational diversion.