Algorithmic Problem Solving

The problem tackled in this chapter is a particularly hard one. Yet, by suitably decomposing the problem combined with effective reasoning skills, the problem becomes solvable.

The problem is to find a Knight’s circuit of a chessboard. That is, find a sequence of moves that will take a Knight in a circuit around all the squares of a chessboard, visiting each square exactly once, and ending at the square at which the circuit began.

The problem is an instance of a search problem; in principle, it can be solved by a systematic, exhaustive examination of all the paths a Knight can follow around a chessboard – a brute-force search. However, there are 64 squares on a chessboard; that means 64 moves have to be chosen, one for each square. From each of the corner squares, there is a choice of just 2 moves, but from each of the 16 central squares, there is a choice of 8 moves (see Figure 11.1); from the remaining squares either 4 or 6 moves are possible. This gives a massive amount of choice in the paths that can be followed. Lots of choice is usually not a problem but, when combined with the very restrictive requirement that the path forms a circuit that visits every square exactly once, it does become a problem. The Knight’s circuit problem is hard because of this critical combination of an explosion with an implosion of choice.

But, all is not lost. The squares on a chessboard are arranged ...