Go
golang

Go言語で 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

という感じです。

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

なお、以上はブログ記事が元になっています。