Table of Contents for

Algorithmic Problem Solving

Figure 11.1: Knight’s moves.

11.1 STRAIGHT-MOVE CIRCUITS

Finding a Knight’s circuit is too difficult to tackle head on. Some experience of tackling simpler circuit problems is demanded.

Let’s turn the problem on its head. Suppose you want to make a circuit of a chessboard and you are allowed to choose a set of moves that you are allowed to make. What sort of moves would you choose?

The obvious first answer is to allow moves from any square to any other square. In that case, it’s always possible to construct a circuit of any board, whatever its size – starting from any square, choose a move to a square that has not yet been visited until all the squares are exhausted; then return to the starting square. But that is just too easy. Let’s consider choosing from a restricted set of moves.

The simplest move is one square horizontally or vertically. (These are the moves that a King can make, but excluding diagonal moves.) We call these moves straight moves. Is it possible to make a circuit of a chessboard just with straight moves?

The answer is yes, although it isn’t immediately obvious. You may be able to find a straight-move circuit by trial and error, but let us try to find one more systematically. As is often the case, it is easier to solve a more general problem; rather than restrict the problem to an 8×8 board, let us consider an arbitrary rectangular board. Assuming each move is by one square only, to the left or right, or up or down, is it possible to complete a straight-move circuit of the entire board? That is, is it possible to visit every square exactly once, beginning and ending at the same square, making “straight” moves at each step?

In order to gain some familiarity with the problem, please tackle the following exercise. Its solution is relatively straightforward.

The conclusion of exercise 11.1 is that a straight-move circuit is only possible if the board has size 2m×n, for positive numbers m and n. That is, one side has length 2m and the other has length n. (Both m and n must be non-zero because the problem assumes the existence of at least one starting square.) Also, a straight-move circuit can always be completed when the board has size 2×n, for positive n. This suggests that we now try to construct a straight-move circuit of a 2m×n board, for m at least one and n greater than one, by induction on m, the 2×n case providing the basis for the inductive construction.

To complete the inductive construction, we need to consider a board of size 2m × n, where m is greater than 1. Such a construction is hopeful because, when m is greater than 1, a 2m × n board can be split into two boards of sizes 2p × n and 2q × n, say, where both p and q are smaller than m and p+q equals m. We may take as the inductive hypothesis that a straight-move circuit of both boards can be constructed. We just need to combine the two constructions.

In our description of the solution below, we use the convention that the first component of the size of a board gives the number of rows and the second the number of columns.

The key to the combination is the corner squares. There are two straight moves from each of the corner squares, and any straight-move circuit must use both. In particular, it must use the horizontal moves. Now, imagine that a 2m × n board is divided into a 2p × n board and a 2q × n board, with the former above the latter. The bottom-left corner of the 2p × n board is immediately above the top-left corner of the 2q × n board. Construct straight-move circuits of these two boards. Figure 11.2 shows the result diagrammatically. The two solid horizontal lines at the middle-left of the diagram depict moves that we know must form part of the two circuits. The dashed lines depict the rest of the circuits. (Of course, the shape of the dashed lines gives no indication of the shape of the circuit that is constructed.)

Figure 11.2: Combining straight-move circuits. First, split the board into two smaller boards and construct straight-move circuits of each.

Now, to combine the circuits to form one circuit of the entire board, replace the horizontal moves from the bottom-left and top-left corners by vertical moves, as shown by the vertical solid lines in Figure 11.3. This completes the construction.

Figure 11.3: Second, combine the two circuits as shown.

Figure 11.4 shows the circuit that is constructed in this way for a 6 × 8 board. Effectively, the basis of the inductive algorithm constructs straight-move circuits of three 2 × 8 boards. The induction step then combines them by replacing horizontal moves by the vertical moves shown in Figure 11.4.

Figure 11.4: A straight-move circuit for a 6 × 8 board.

11.2 SUPERSQUARES

Let us now return to the Knight’s-circuit problem. The key to a solution is to exploit what we know about straight moves. The way this is done is to imagine that the 8 × 8 chessboard is divided into a 4 × 4 board by grouping together 2 × 2 squares into “supersquares”, as shown in Figure 11.6.

Figure 11.6: Chessboard divided into a 4 × 4 board of supersquares.

If this is done, the Knight’s moves can be classified into two types: Straight moves are moves that are “straight” with respect to the supersquares; that is, a Knight’s move is straight if it takes it from one supersquare to another supersquare either vertically above or below, or horizontally to the left or to the right. Diagonal moves are moves that are not straight with respect to the supersquares; a move is diagonal if it takes the Knight from one supersquare to another along one of the diagonals through the starting supersquare. In Figure 11.7, the boundaries of the supersquares are indicated by thickened lines; the starting position of the Knight is shown in black, the straight moves are to the white positions, and the diagonal moves are to the grey positions.

Focusing on the straight moves, we now make a crucial observation. Figure 11.8 shows the straight moves from one supersquare – the bottom-left supersquare – vertically upwards and horizontally rightwards. The “colours” (the combination of stripes and shading) indicate the moves that can be made. For example, from the bottom-left white square a straight move can be made to the top-left white square or to the bottom-right white square. However, it is not possible to move from a square to another square of a different “colour”.

Figure 11.7: Straight (white) and diagonal (grey) knight’s moves from some starting position (black). Boundaries of the supersquares are indicated by thickened lines.

Figure 11.8: Straight moves from the bottom-left supersquare.

Observe the pattern. Vertical moves flip the “colours” around a vertical axis, whilst horizontal moves flip them around a horizontal axis. (The vertical moves interchange striped and not-striped squares; the horizontal moves interchange shaded and not-shaded squares.)

Let us denote by v the operation of flipping the columns of a 2 × 2 square (v is short for “vertical”). Similarly, let us denote by h (short for “horizontal”) the operation of flipping the rows of the square. Now, let an infix semicolon denote doing one operation after another. So, for example, v ; h denotes the operation of first flipping the columns and then flipping the rows of the square. Flipping the columns and then flipping the rows is the same as flipping the rows and then the columns. That is,

v ; h = h ; v.

Both are equivalent to rotating the 2 × 2 square through 180° about its centre. So, let us use c (short for “centre”) as its name. That is, by definition of c,

We have now identified three operations on a 2 × 2 square. There is a fourth operation, which is the do-nothing operation. Elsewhere, we have used skip to name such an operation. Here, for greater brevity we use n (short for “no change”). Flipping twice vertically, or twice horizontally, or rotating twice through 180° about the centre, all amount to doing nothing. That is;

Also, doing nothing before or after any operation is the same as doing the operation.

The three equations (11.3), (11.4) and (11.5), together with the fact that doing one operation after another is associative (that is, doing one operation x followed by two operations y and z in turn is the same as doing first x followed by y and then concluding with z – in symbols, x ; (y ; z) = (x ; y) ; z) allow the simplification of any sequence of the operations to one operation. For example,

        v; c; h
=               {          v; h = c  }
        v; v; h; h
=               {          v; v = h; h = n  }
        n; n
=               {          n; x = x, with x:= n  }
        n.

In words, flipping vertically, then rotating through 180° about the centre, and then flipping horizontally is the same as doing nothing. (Note how associativity is used implicitly between the first and second steps. The use of an infix operator for “followed by” facilitates this all-important calculational technique.)

11.3 PARTITIONING THE BOARD

The identification of the four operations on supersquares is a significant step towards solving the Knight’s-circuit problem. Suppose one of the supersquares is labelled “n”. Then the remaining fifteen supersquares can be uniquely labelled as n, v, h or c squares, depending on their position relative to the starting square. Figure 11.9 shows how this is done. Suppose we agree that the bottom-left square is an “n” square. Then immediately above it is a “v” square, to the right of it is an “h” square, and diagonally adjacent to it is a “c” square. Supersquares further away are labelled using the rules for composing the operations.

As a consequence, all 64 squares of the chessboard are split into four disjoint sets. In Figure 11.9, the different sets are easily identified by the colour of the square¹. Two squares have the same colour equivales they can be reached from each other by straight Knight’s moves. (That is, two squares of the same colour can be reached from each other by straight Knight’s moves, and two squares of different colour cannot be reached from each other by straight Knight’s moves.)

Figure 11.9: Labelling supersquares.

Recall the discussion of straight-move circuits in section 11.1. There we established the simple fact that it is possible to construct a straight-move circuit of a board of which one side has even length and the other side has length at least two. In particular, we can construct a straight-move circuit of a 4 × 4 board.

Now, a “straight” Knight’s move is “straight” with respect to the supersquares of a chessboard. That means we can construct straight-move circuits of each of the four sets of squares on the chessboard. In Figure 11.9, this means constructing a circuit of all the white squares, a circuit of all the striped squares, a circuit of all the shaded squares, and a circuit of all the shaded-and-striped squares. Figure 11.10 shows how we distinguish the four different circuits. Specifically, moves connecting white squares are shown as 0-dot, dashed lines, moves connecting striped squares are shown as 1-dot, dashed lines, moves connecting shaded squares are shown as 2-dot, dashed lines, and moves connecting shaded-and-striped squares are shown as 3-dot, dashed lines.

Figure 11.10: Moves from the bottom-left supersquare. The number of dots (0, 1, 2 or 3) corresponds to the “colour” of connected squares (white, striped, shaded and striped-and-shaded).

We now have four disjoint circuits that together visit all the squares of the chessboard. The final step is to combine the circuits into one. The way to do this is to exploit the “diagonal” Knight’s moves. (Refer back to Figure 11.7 for the meaning of “diagonal” in this context.)

A simple way of combining the four circuits is to combine them in pairs, and then combine the two pairs. For example, we can combine the circuits of the white and striped squares into a “non-shaded” circuit of half the board; similarly, we can combine the circuits of the shaded and shaded-and-striped squares into a “non-white” circuit. Finally, by combining the non-shaded and non-white circuits, a complete circuit of the board is obtained.

Figure 11.11 shows schematically how non-shaded and non-white circuits are formed; in each case, two straight moves (depicted by dotted lines) in the respective circuits are replaced by diagonal moves (depicted by solid lines). Figure 11.12 shows one way of choosing the straight and diagonal moves in order to combine striped and white circuits, and shaded and shaded-and-striped circuits – in each case, two “parallel” straight moves are replaced by two “parallel” diagonal moves. Exploiting symmetry, it is easy to find similar “parallel moves” with which to combine striped and shaded-and-striped circuits, or shaded and white circuits. On the other hand, there are no diagonal moves from striped to shaded, or from shaded-and-striped to white squares; consequently, it is impossible to construct a “non-striped” or a “non-plain” circuit.

Figure 11.11: Schema for forming “non-shaded” and “non-white” circuits. The straight-move circuits are depicted as circles, a single move in each being depicted by a dotted line. These straight moves are replaced by the diagonal moves, shown as solid lines.

Striped and white straight-move circuits have been combined in Figure 11.13 to form a “non-shaded” circuit. The method of combination is indicated by the dotted and solid lines: the straight moves (dotted lines) are replaced by diagonal moves (solid lines). To complete a circuit of the whole board, with this “non-shaded” circuit as basis, a “non-white” circuit has to be constructed, and this circuit combined with the “non-shaded” circuit. This is left as an exercise.

A slight difficulty of this method is that it constrains the straight-move circuits that can be made. For example, considering the suggested method for combining striped and white circuits in Figure 11.12, no constraint is placed on the white circuit (because there is only one way a straight-move circuit of the white squares can enter and leave the bottom-left corner of the board). However, the straight-move circuit of the striped squares is constrained by the requirement that it make use of the move shown as a dotted line. The difficulty is resolved by first choosing the combining moves and then constructing the straight-move circuits appropriately.

Figure 11.12: Forming circuits of the “non-shaded” and “non-white” squares. The straight moves shown as dotted lines are replaced by the diagonal moves shown as solid lines.

In order to construct a Knight”s circuit of smaller size boards, the different pairs of combining moves need to be positioned as close as possible together. This is possible in the case of an 8 × 6 board, but not for smaller boards.

Figure 11.13: A circuit of the “non-shaded” squares. Parallel straight moves, shown as thicker dotted lines, are replaced by parallel diagonal moves, shown as thicker solid lines, thus combining the two circuits.

11.5 BIBLIOGRAPHIC REMARKS

Solutions and historical information on the Knight”s circuit problem can easily be found on the internet. According to one of these [MacQuarrie, St. Andrews Univ.] the first Knight’s tour is believed to have been found by al-Adli ar-Rumni in the ninth century, long before chess was invented.

I learnt about the use of supersquares in solving the Knight’s circuit problem from Edsger W. Dijkstra [Dij92]. Dijkstra’s solution is for a standard-sized chessboard and uses the method of combining straight-move circuits described in exercise 11.11. The pairwise combination of straight-move circuits was suggested by Diethard Michaelis. Both solutions involve searching for “parallel moves”. Michaelis’s solution is slightly preferable because just two pairs of “parallel moves” have to be found at each stage. Dijkstra’s solution involves searching for four pairs (twice as many) at the same time, making it a little bit harder to do. The solution to exercise 11.12 was constructed by the author, with useful feedback from Michaelis.

Since first writing this chapter (in 2003), I have learnt that the use of supersquares was devised by Peter Mark Roget (better known for his Thesaurus) in 1840. According to George Jelliss [google “Knight’s Tours”], H.J.R.Murray introduced the terminology “straights” and “slants” for the two types of move in a book entitled History of Chess and published in 1913. Jellis’s website gives an encyclopaedic account of Knight’s tours and Knight’s circuits.

¹Because we are unable to use true colours, like red and blue, we use “colour” to refer to the different combinations of shaded/not-shaded and striped/not-striped.