

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


n_queens = cluster is solve
    rep = null
    own hist: array[int] := array[int]$[]
    own solutions: array[string] := array[string]$[]
 
    attack = proc (i,j,col: int) returns (bool)
        return(hist[j]=i | int$abs(hist[j]-i)=col-j)
    end attack
 
    cur_solution = proc ()
        n: int := array[int]$size(hist)
        ss: stream := stream$create_output()
 
        for i: int in int$from_to(0,n-1) do
            for j: int in int$from_to(0,n-1) do
                if j=hist[i] then stream$putc(ss, 'Q')
                elseif (i+j)//2 = 1 then stream$putc(ss, ' ')
                else stream$putc(ss, '.')
                end
            end
            stream$putc(ss, '\n')
        end
 
        array[string]$addh(solutions, stream$get_contents(ss))
    end cur_solution
 
    solve_rec = proc (col: int)
        n: int := array[int]$size(hist)
        if col=n then cur_solution() return end
 
        for i: int in int$from_to(0,n-1) do
            j: int := 0
            while j<col cand ~attack(i,j,col) do j := j+1 end
            if j<col then continue end
            hist[col] := i
            solve_rec(col+1)
        end
    end solve_rec
 
    solve = proc (n: int) returns (sequence[string])
        hist := array[int]$fill(0,n,0)
        solutions := array[string]$[]
        solve_rec(0)
        return(sequence[string]$a2s(solutions))
    end solve
end n_queens
 
start_up = proc()
    N = 8
 
    po: stream := stream$primary_output()
    solutions: sequence[string] := n_queens$solve(N)
 
    count: int := 0
    for s: string in sequence[string]$elements(solutions) do  
        count := count + 1
        stream$putl(po, "No. " || int$unparse(count) || "\n-------\n" || s)
    end
end start_up