Julia で 8 queens 問題

obelisk.hatenablog.com
ここで Go と Ruby でやっていることを、Julia でやってみました。

結果はこんな感じ。

$ time julia eight_queens.jl
--------------
n = 1
@.......
....@...
.......@
.....@..
..@.....
......@.
.@......
...@....
--------------
n = 2
@.......
.....@..
.......@
..@.....
......@.
...@....
.@......
....@...
--------------

....

--------------
n = 92
.......@
...@....
@.......
..@.....
.....@..
.@......
......@.
....@...

real	0m0.367s
user	0m0.474s
sys	0m0.211s

 
コード。
eight_queens.jl

N = 8
count = 0

function get_space(field, n)
    result = fill(true, N)
    for i in 1:n
        queen = field[i]
        result[queen] = false
        dst = n - i + 1
        if queen - dst >= 1 ; result[queen - dst] = false end
        if queen + dst <= N ; result[queen + dst] = false end
    end
    result
end

function solve(field, n)
    if n == N
        global count += 1
        println("--------------")
        println("n = $count")
        for queen in field
            println(repeat(".", queen - 1) * "@" * repeat(".", N - queen))
        end
    else
        tmp = get_space(field, n)
        for i in 1:N
            if tmp[i]
                field[n + 1] = i
                solve(field, n + 1)
            end
        end
    end
end

solve(repeat([0], N), 0)

配列のインデックスが 1 から始まるのには戸惑いました。あと、Rubyeach_with_index に相当する文法がないのかな? それ以外はかなり書きやすいですね。型の記述はしませんでした。このあたり、柔軟である。
 
N = 13 にしてかつ最終的な解の個数だけ出力するようにしてみると、

$ time julia eight_queens.jl
73712

real	0m12.339s
user	0m12.401s
sys	0m0.276s

という感じ。