Go言語と Ruby で 8 queens 問題

Go で「8 queens 問題」を解いてみました。実際は n queens が解けます。

すべての解を出力します。num = 8 の場合、解は 92通りあります。こんな感じ。

------------------
n = 1
@.......
....@...
.......@
.....@..
..@.....
......@.
.@......
...@....
------------------
n = 2
@.......
.....@..
.......@
..@.....
......@.
...@....
.@......
....@...
------------------
（以下略）

　
コードはこんな感じです。
eight_queen.go

package main
import "fmt"
import "strings"

const num = 8
var count = 0

//出力
func putout(field []int) {
    count++
    fmt.Println("------------------")
    fmt.Printf("n = %d\n", count)
    st := strings.Repeat(".", num - 1)
    for _, queen := range field {
        fmt.Println(st[0: queen] + "@" + st[0: num - queen - 1])
    }
}

//ここまでの field で女王の置けるマス（空白）を探す（1なら置けない）
func get_space(field []int) [num]int {
    result := [num]int{}
    l := len(field)
    for i, queen := range field {
        result[queen] = 1
        dst := l - i
        if a := queen - dst; a >= 0  {result[a] = 1}
        if a := queen + dst; a < num {result[a] = 1}
    }
    return result
}

//メインの深さ優先探索
func solve(field []int) {
    if len(field) == num {
        putout(field)
    } else {
        for i, space := range get_space(field) {
            if space == 0 { solve(append(field, i)) }
        }
    }
}

func main () {
    solve([]int{})
}

実質的に solve() と get_space() の 2つのメソッドだけでシンプルに書けました。putout() は出力用です。たぶん、これはたいていの言語にそのまま移植できると思います。
　
結構うまく書けたのではないでしょうか。再帰的に深さ優先探索で解いています。

実行時間は num = 8 の場合ほぼ一瞬（0.01秒くらい）です。num = 15 の場合、最終的な解の個数だけ出力するように改変して（コード）実行すると

$ time ./eight_queen
2279184

real	0m17.135s
user	0m17.332s
sys	0m0.040s

となります。num = 17 で

$ time ./eight_queen
95815104

real	13m38.920s
user	13m42.884s
sys	0m1.228s

くらいが限界でしょうか。

Go で書くのは好きですね。コードの見た目がいいです。

※参考
これまでの試み。今回は以前とはだいぶちがったロジックで求めています。
エイト・クイーン（8 queen）問題を Ruby で解いてみる - Camera Obscura
ふたたび Ruby で 8 queen（関数型プログラミングっぽく） - Camera Obscura
Swift で 8queen 問題を解く - Camera Obscura
　

ちなみに Ruby だとこんな風に移植できますか。
eight_queen_another.rb

#ここまでの field で女王の置けるマス（空白）を探す（falseなら置けない）
def get_space(field)
  result = Array.new(N, true)
  l = field.size
  field.each_with_index do |queen, i|
    result[queen] = false
    dst = l - i
    result[queen - dst] = false if queen - dst >= 0
    result[queen + dst] = false if queen + dst <  N
  end
  result
end

#メインの深さ優先探索および出力
def solve(field)
  if field.size == N
    @count += 1
    puts "------------------"
    puts "n = #{@count}"
    field.each {|queen| puts ("." * (N - 1)).insert(queen, "@")}
  else
    get_space(field).each_with_index {|space, i| solve(field + [i]) if space}
  end
end

N = 8
@count = 0
solve([])