

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


"""
# EightQueensPuzzle
 
Ported to **Julia** from examples in several languages from
here: https://hbfs.wordpress.com/2009/11/10/is-python-slow
"""
module EightQueensPuzzle
 
export Board, solve!
 
mutable struct Board
    cols::Int
    nodes::Int
    diag45::Int
    diag135::Int
    solutions::Int
 
    Board() = new(0, 0, 0, 0, 0)
end
 
"Marks occupancy."
function mark!(b::Board, k::Int, j::Int)
    b.cols    ⊻= (1 << j)
    b.diag135 ⊻= (1 << (j+k))
    b.diag45  ⊻= (1 << (32+j-k))
end
 
"Tests if a square is menaced."
function test(b::Board, k::Int, j::Int)
    b.cols    & (1 << j)        +
    b.diag135 & (1 << (j+k))    +
    b.diag45  & (1 << (32+j-k)) == 0
end
 
"Backtracking solver."
function solve!(b::Board, niv::Int, dx::Int)
    if niv > 0
        for i in 0:dx-1
            if test(b, niv, i) == true
                mark!(b, niv, i)
                solve!(b, niv-1, dx)
                mark!(b, niv, i)
            end
        end
    else
        for i in 0:dx-1
            if test(b, 0, i) == true
                b.solutions += 1
            end
        end
    end
    b.nodes += 1
    b.solutions
end
 
end # module
 
using  .EightQueensPuzzle
 
for n = 1:17
    b = Board()
    @show n
    print("elapsed:")
    solutions = @time solve!(b, n-1, n)
    @show solutions
    println()
end
 