

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


def     N=8;    \board size (NxN)
int     R, C;   \row and column of board
char    B(N,N); \board
include c:\cxpl\codes;
 
proc Try;       \Try adding a queen to the board
int  R;         \row, for each level of recursion
 
    func Okay;
    \Returns 'true' if no row, column, or diagonal from square R,C has a queen
    int I;
    [for I:= 0 to N-1 do
        [if B(I,C) then return false;                   \row is occupied
        if B(R,I) then return false;                    \column is occupied
        if R+I<N & C+I<N then
                if B(R+I, C+I) then return false;       \diagonal down right
        if R-I>=0 & C-I>=0 then
                if B(R-I, C-I) then return false;       \diagonal up left
        if R-I>=0 & C+I<N then
                if B(R-I, C+I) then return false;       \diagonal up right
        if R+I<N & C-I>=0 then
                if B(R+I, C-I) then return false;       \diagonal down left
        ];
    return true;
    ]; \Okay
 
[ \Try
if C>=N then
        [for R:= 0 to N-1 do                            \display solution
            [ChOut(0, ^ ); \(avoids scrolling up a color)
            for C:= 0 to N-1 do
                [Attrib(if (R|C)&1 then $0F else $4F);  \checkerboard pattern
                ChOut(6, if B(R,C) then $F2 else ^ );   \cute queen symbol
                ChOut(6, if B(R,C) then $F3 else ^ );
                ];
            CrLf(0);
            ];
        exit;                                           \one solution is enough
        ];
for R:= 0 to N-1 do
    [if Okay(R,C) then          \a queen can be placed here
        [B(R,C):= true;         \ so do it
        C:= C+1;                \move to next column
        Try;                    \ and try from there
        C:= C-1;                \didn't work: backup
        B(R,C):= false;         \undo queen placement
        ];
    ];
]; \Try
 
 
[for R:= 0 to N-1 do            \clear the board
    for C:= 0 to N-1 do
        B(R,C):= false;
C:= 0;                          \start at left column
Try;
]