Solution of the four queens problem
Many combinatorial puzzles are easily formulated as non-deterministic computations. Consider, for example, the classical eight queens problem. The start state is an empty board. The possible actions at any point are placing a queen in any of the squares not accessible in a single move from those already on the board. If there are none then the computation terminates, successfully, if we’ve placed eight queens, and unsuccessfully, if we haven’t.
The problem can be made more tractable if we realise that any successful solution must have exactly one queen in each row and the order in which we place the queens has no bearing on whether the configuration is permitted or not, so we can reformulate the problem slightly, with the permitted actions at the \({ i }\)’s step being placing a queen somewhere in the \({ i }\)’th row which is not accessible in a single move from those already on the board. This change, for example, reduces the number of possible actions for the first step from 64 to 8 and the number for the second step from somewhere between 36 and 42 to either 5 or 6. The number of possibilities for the full problem is still too many for diagrams which fit on a single page though so we’ll consider a chessboard with four rows and columns rather than eight.
A good way to illustrate the possible computational paths is with a tree, as in the diagram.
The lowermost two leaves of the tree, the ones with four queens placed, represent successful computational paths. The other four leaves, with either two or three queens placed, represent unsuccessful computational paths.
We can, of course, do the same thing in the original eight queens problem or, more generally, in a wide variety of similar puzzles.