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 から始まるのには戸惑いました。あと、Ruby の each_with_index
に相当する文法がないのかな? それ以外はかなり書きやすいですね。型の記述はしませんでした。このあたり、柔軟である。
N = 13 にしてかつ最終的な解の個数だけ出力するようにしてみると、
$ time julia eight_queens.jl 73712 real 0m12.339s user 0m12.401s sys 0m0.276s
という感じ。