

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


MODULE NQueens;
FROM InOut IMPORT Write, WriteCard, WriteString, WriteLn;
 
CONST N = 8;
VAR hist: ARRAY [0..N-1] OF CARDINAL;
    count: CARDINAL;
 
PROCEDURE Solve(n, col: CARDINAL);
    VAR i, j: CARDINAL;
 
    PROCEDURE Attack(i, j: CARDINAL): BOOLEAN;
        VAR diff: CARDINAL;
    BEGIN
        IF hist[j] = i THEN RETURN TRUE;
        ELSE
            IF hist[j] < i THEN diff := i - hist[j];
            ELSE diff := hist[j] - i;
            END;
            RETURN diff = col-j;
        END;
    END Attack;
BEGIN
    IF col = n THEN
        INC(count);
        WriteLn;
        WriteString("No. ");
        WriteCard(count, 0);
        WriteLn;
        WriteString("---------------");
        WriteLn;
 
        FOR i := 0 TO n-1 DO
            FOR j := 0 TO n-1 DO
                IF j = hist[i] THEN Write('Q');
                ELSIF (i + j) MOD 2 = 1 THEN Write(' ');
                ELSE Write('.');
                END;
            END;
            WriteLn;
        END;
    ELSE
        FOR i := 0 TO n-1 DO
            j := 0;
            WHILE (j < col) AND (NOT Attack(i,j)) DO INC(j); END;
            IF j >= col THEN
                hist[col] := i;
                Solve(n, col+1);
            END;
        END;
    END;
END Solve;
 
BEGIN
    count := 0;
    Solve(N, 0);
END NQueens.