Sometimes you feel like doing math; sometimes you feel like writing software. I'm sure you can relate.
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 seconds. 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
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 works, I'll leave that one to you. The tour runs from lower left to upper right, so chain these boards together and a 4n by 3 board works.
A 7 by 3 board has this tour: a1 c2 a3 b1 c3 a2 c1 b3 d2 f3 g1 e2 g3 f1 e3 g2 e1 d3 b2 d1 f2. Put this together with the previous result and a 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, and only those 4 squares are in the circuit. So d4 starts or ends the tour. We can 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. 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. [Pause … spoiler alert.} 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 extends to 4n+9 by 3. 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
How about a 6 by 3 board? This one is a little trickier. 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. 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 It 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? I tweaked my program just a bit, taking arguments 8 8 - -, and the answer is yes. Here is the circuit. It starts and ends at the lower left.
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. This never changes, 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 of the sequence. 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 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 v to z for example. Thus there is a solution to the board of width 26, or 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. 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. a1 c2 d4 b5 a3 b1 d2 c4 a5 b3 c5 a4 b2 d1 c3 d5 b4 a2 c1 d3 You need to solve boards of width 5 6 and 7; I'll leave the details to you.
Chaining works on other heights as well, 4 is the only trouble maker.
A C program to find the knight's circuit on the chess board.