

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


with javascript_semantics
--
-- demo\rosetta\n_queens.exw
-- =========================
--
sequence co,    -- columns occupied
                -- (ro is implicit)
         fd,    -- forward diagonals
         bd,    -- backward diagonals
         board
 
atom count
 
procedure solve(integer row, integer N, integer show)
    for col=1 to N do
        if not co[col] then
            integer fdi = col+row-1,
                    bdi = row-col+N
            if not fd[fdi]
            and not bd[bdi] then
                board[row][col] = 'Q'
                co[col] = 1
                fd[fdi] = 1
                bd[bdi] = 1
                if row=N then
                    if show then
                        puts(1,join(board,"\n")&"\n")
                        puts(1,repeat('=',N)&"\n")
                    end if
                    count += 1
                else
                    solve(row+1,N,show)
                end if
                board[row][col] = '.'
                co[col] = 0
                fd[fdi] = 0
                bd[bdi] = 0
            end if
        end if
    end for
end procedure
 
procedure n_queens(integer N=8, integer show=1)
    co = repeat(0,N)
    fd = repeat(0,N*2-1)
    bd = repeat(0,N*2-1)
    board  = repeat(repeat('.',N),N)
    count = 0
    solve(1,N,show)
    printf(1,"%d queens: %d solutions\n",{N,count})
end procedure
 
for N=1 to iff(platform()=JS?12:14) do
    n_queens(N,N<5)
end for
