__precompile__(true)

"""
# EightQueensPuzzle

Ported to Julia from examples in several languages from
https://hbfs.wordpress.com/2009/11/10/is-python-slow
https://gist.github.com/SalchiPapa/f5107608f9780e30132f
(c) 2015 Ismael Venegas Castelló
(c) 2018 Peter Luschny (modified, profile added)
Placed in public domain.
"""

module EightQueensPuzzle

mutable struct Board
    size::Int
    cols::Int
    diag4::Int
    diag1::Int
    Board(n) = new(n - 1, 0, 0, 0)
end

"Marks occupancy."
@inline function mark!(b::Board, k::Int, j::Int)
    b.cols  = xor(b.cols,  1 << j)
    b.diag1 = xor(b.diag1, 1 << (j + k))
    b.diag4 = xor(b.diag4, 1 << (32 + j - k))
end

"Tests if a square is menaced."
@inline function test(b::Board, k::Int, j::Int)
    b.cols  & (1 << j)            +
    b.diag1 & (1 << (j + k))      +
    b.diag4 & (1 << (32 + j - k)) == 0
end

"Backtracking solver."
function solve!(b::Board, profile, level::Int)
    level -= 1
    if level > 0
        for i in 0:b.size
            if test(b, level, i)
                mark!(b, level, i)
                solve!(b, profile, level)
                profile[level + 1] += 1
                mark!(b, level, i)
            end
        end
    else
        for i in 0:b.size
            if test(b, 0, i)
                profile[1] += 1
            end
        end
    end
end

function ProblemOfQueens(n::Int)
    profile = zeros(Int, n + 1)
    profile[end] = 1 # start with root
    b = Board(n)
    print("elapsed: ")
    @time solve!(b, profile, n)
    println("size:      ", n)
    println("profile:   ", [profile[n-i+1] for i = 0:n])
    println("nodes:     ", sum(profile))
    println("solutions: ", profile[1])
end

for n in 1:12
    gc()
    ProblemOfQueens(n)
    println()
end

end

#=

elapsed:   0.000001 seconds
size:      1
profile:   [1, 1]
nodes:     2
solutions: 1

elapsed:   0.000002 seconds
size:      2
profile:   [1, 2, 0]
nodes:     3
solutions: 0

elapsed:   0.000004 seconds
size:      3
profile:   [1, 3, 2, 0]
nodes:     6
solutions: 0

elapsed:   0.000002 seconds
size:      4
profile:   [1, 4, 6, 4, 2]
nodes:     17
solutions: 2

elapsed:   0.000004 seconds
size:      5
profile:   [1, 5, 12, 14, 12, 10]
nodes:     54
solutions: 10

elapsed:   0.000011 seconds
size:      6
profile:   [1, 6, 20, 36, 46, 40, 4]
nodes:     153
solutions: 4

elapsed:   0.000037 seconds
size:      7
profile:   [1, 7, 30, 76, 140, 164, 94, 40]
nodes:     552
solutions: 40

elapsed:   0.000145 seconds
size:      8
profile:   [1, 8, 42, 140, 344, 568, 550, 312, 92]
nodes:     2057
solutions: 92

elapsed:   0.000639 seconds
size:      9
profile:   [1, 9, 56, 234, 732, 1614, 2292, 2038, 1066, 352]
nodes:     8394
solutions: 352

elapsed:   0.002993 seconds
size:      10
profile:   [1, 10, 72, 364, 1400, 3916, 7552, 9632, 7828, 4040, 724]
nodes:     35539
solutions: 724

elapsed:   0.015253 seconds
size:      11
profile:   [1, 11, 90, 536, 2468, 8492, 21362, 37248, 44148, 34774, 15116, 2680]
nodes:     166926
solutions: 2680

elapsed:   0.094858 seconds
size:      12
profile:   [1, 12, 110, 756, 4080, 16852, 52856, 120104, 195270, 222720, 160964, 68264, 14200]
nodes:     856189
solutions: 14200

=#