The 4 Queens problem - place 4 Queens on a 4 x 4 chessboard so that none of them is threatened by any other.
No problem in Cannot place 2nd Cannot place 2nd Can place 2nd
placing 1st Queen Queen in top row Queen in 2nd row Queen in 3rd row
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗
1 ║ Q │ │ │ ║ ║ Q │ X │ │ ║ ║ Q │ │ │ ║ ║ Q │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
2 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ X │ │ ║ ║ │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
3 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ Q │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
4 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║
╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝
So now we can try to place the third Queen in the third column:
Cannot place 3rd Cannot place 3rd Cannot place 3rd Cannot place 3rd
Queen in top row Queen in 2nd row Queen in 3rd row Queen in 4th row
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗
1 ║ Q │ │ X │ ║ ║ Q │ │ │ ║ ║ Q │ │ │ ║ ║ Q │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
2 ║ │ │ │ ║ ║ │ │ X │ ║ ║ │ │ │ ║ ║ │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
3 ║ │ Q │ │ ║ ║ │ Q │ │ ║ ║ │ Q │ X │ ║ ║ │ Q │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
4 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ X │ ║
╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝
Oh dear! Are we stuck completely? No, we can still back track and try to find another position for the 2nd Queen. We have already looked at rows 1 and 2 (no use) and row 3 (was okay until now!). That leaves row 4.
The 2nd Queen can Cannot place 3rd Can place 3rd Cannot place 4th
also fit in row 4. Queen in 1st row Queen in 2nd row Queen in any row
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗
1 ║ Q │ │ │ ║ ║ Q │ │ X │ ║ ║ Q │ │ │ ║ ║ Q │ │ │ - ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
2 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ Q │ ║ ║ │ │ Q │ - ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
3 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ - ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
4 ║ │ Q │ │ ║ ║ │ Q │ │ ║ ║ │ Q │ │ ║ ║ │ Q │ │ - ║
╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝
Oh dear! The 4th Queen cannot fit on any row in the 4th column. Are we at last stuck completely? Can we still back track and try to find another position for the 2nd Queen. No, there are no more. We shall have to backtrack still further and take the 2nd Queen right off, and also move the first Queen.
The first Queen Cannot place 2nd Cannot place 2nd Cannot place 2nd
can go in row 2 Queen in row 1 Queen in row 2 Queen in row 3
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗
1 ║ │ │ │ ║ ║ │ X │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
2 ║ Q │ │ │ ║ ║ Q │ │ │ ║ ║ Q │ X │ │ ║ ║ Q │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
3 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ X │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
4 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║
╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝
This is getting frustrating. But if at first you don't succeed:
Can place 2nd Can place 3rd Cannot place 4th Cannot place 4th
Queen in row 4 Queen in row 1 Queen in 1 or 2 Queen in row 3
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗
1 ║ │ │ │ ║ ║ │ │ Q │ ║ ║ │ │ Q │ X ║ ║ │ │ Q │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
2 ║ Q │ │ │ ║ ║ Q │ │ │ ║ ║ Q │ │ │ X ║ ║ Q │ │ │ ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
3 ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ ║ ║ │ │ │ Q ║
╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢ ╟───┼───┼───┼───╢
4 ║ │ Q │ │ ║ ║ │ Q │ │ ║ ║ │ Q │ │ ║ ║ │ Q │ │ ║
╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝ ╚═══╧═══╧═══╧═══╝
All things come to those who wait. Are there any other solutions do you suppose? How do you find them if there are? Could we do the same sort of thing for any number of Queens?
A good discussion of back-tracking algorithms is to be found in a classic text by Niklaus Wirth (inventor of Pascal, Modula, Modula-2 and Oberon, and one of the greatest computer scientist of our age). The book has the unusual name Algorithms + Data Structures = Programs, and is well worth consulting. It was published by Prentice Hall in 1976 in a Pascal edition, and again in 1985 in a Modula-2 edition.
Wirth gives a general pattern for finding solutions to these sorts of problems as follows (I have translated his notation slightly).
PROCEDURE TryNextStep (VAR Successful : BOOLEAN);
BEGIN
InitializeDataStructures;
REPEAT
SelectPossibility;
IF Acceptable THEN
RecordPossibility;
IF SolutionIncomplete THEN
TryNextStep(Successful)
IF NOT Successful THEN
CancelPossibility
END
END
END
UNTIL Successful OR NoMorePossibilities
END TryNextStep;
Sometimes - as in the case of the Queens problem - one can parameterize this routine further, to include a counter I among the N items to be selected, and sometimes the NoMorePossibilities failure is easily determined in terms of a counter J that reaches a limit. Hence we get variations on this theme like:
PROCEDURE TryNextStep (I, N : INTEGER; VAR Successful : BOOLEAN);
VAR
J : INTEGER;
BEGIN
InitializeDataStructures; J := 0;
REPEAT
INC(J); SelectPossibility(J);
IF Acceptable THEN
RecordPossibility;
IF I < N THEN
TryNextStep(I + 1, N, Successful)
IF NOT Successful THEN
CancelPossibility(J)
END
END
END
UNTIL Successful OR (J = N) (* NoMorePossibilities for J *)
END TryNextStep;
And here, finally, is essentially how Wirth develops this system for the specific case of finding a solution to the 8 Queens problem. This solution is given in Pascal (you should all be exposed to Pascal at some stage, even if the world shouts Java and C++ all day). Wirth is a fascinating programmer. He write very tight code - but is it always easy to follow? If not, why not?
PROGRAM Queens;
(* Find a solution to the 8 Queens problem - how do we place 8 Queens on
a chessboard so that none of them is threatened by any other one.
Code closely based on that by Niklaus Wirth in "Algorithms + Data
Structures = Programs" (Prentice-Hall, 1976; page 145)
Modifications by Pat Terry, Rhodes University, 2000 *)
CONST
Size = 8;
VAR
A : ARRAY [1 .. Size] OF BOOLEAN;
B : ARRAY [2 .. 2*Size] OF BOOLEAN;
C : ARRAY [-Size+1 .. Size-1] OF BOOLEAN;
X : ARRAY [1 .. Size] OF INTEGER;
I : INTEGER;
Success : BOOLEAN;
PROCEDURE Try (I : INTEGER; VAR Success : BOOLEAN);
VAR
J : INTEGER;
BEGIN
J := 1; Success := FALSE;
WHILE NOT SUCCESS AND (J <= Size) DO BEGIN
IF A[J] AND B[I+J] AND C[I-J] THEN BEGIN
X[I] := J;
A[J] := FALSE; B[I+J] := FALSE; C[I-J] := FALSE;
IF I < Size
THEN BEGIN
Try(I+1, Success);
IF NOT Success THEN BEGIN
A[J] := TRUE; B[I+J] := TRUE; C[I-J] := TRUE
END;
END
ELSE Success := TRUE;
END;
J := J + 1;
END
END;
BEGIN
FOR I := 1 TO 8 DO A[I] := TRUE;
FOR I := 2 TO 16 DO B[I] := TRUE;
FOR I := -7 TO 7 DO C[I] := TRUE;
Try(1, Success);
IF Success
THEN FOR I := 1 TO Size DO Write(X[I]:4)
ELSE Write('No solution');
WriteLn;
END.