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([])
