Swift で 8queen 問題を解く

以前 Ruby で「エイト・クイーン」問題を解きましたが、それを Swift に移植してみました。「エイト・クイーン」というのは

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3

というものです。すべての解（92個）を求めています。Linux Mint 18.2, Swift 3.1-dev。

実行するとこんな感じ。

$ time ./eight_queen
@.......
......@.
....@...
.......@
.@......
...@....
.....@..
..@.....
------------
@.......
......@.
...@....
.....@..
.......@
.@......
....@...
..@.....
------------

（省略）

------------
.......@
.@......
...@....
@.......
......@.
....@...
..@.....
.....@..
------------

92 answers.

real	0m0.056s
user	0m0.052s
sys	0m0.000s

　
コード。

import Glibc

let N = 8

class Step {
    var x: Int, y: Int
    var parent: Step?
    var depth: Int
    
    init(_ x1: Int, _ y1: Int) {
        (x, y) = (x1, y1)
        parent = nil
        depth = 0
    }
}

func solve(x: Int, y: Int) {
    var stack = Array(arrayLiteral: Step(x, y))
    while !stack.isEmpty {
        let a = stack.removeLast()
        let y = a.y + 1
        let board = get_board(a)
        for x in 0..<N {
            if board[y][x] == 1 {continue}
            let next = Step(x, y)
            next.parent = a
            next.depth  = a.depth + 1
            if next.depth == N - 1 {
                answer(next)
            } else {
                stack.append(next)
            }
        }
    }
}

func get_board(_ a1: Step) -> [[Int]] {
    var board = [[Int]](repeating: [Int](repeating: 0, count: N), count: N)
    var a: Optional = a1
    while a != nil {
        for i in 0..<N {
            board[i][a!.x] = 1
            if i == a!.y {board[i] = [Int](repeating: N, count: N)}
            let d = abs(i - a!.y)
            let x1 = a!.x - d
            let x2 = a!.x + d
            if x1 >= 0 {board[i][x1] = 1}
            if x2 <  N {board[i][x2] = 1}
        }
        a = a!.parent
    }
    return board
}

func answer(_ a1: Step) {
    var bd = [String](repeating: "........", count: N)
    var a: Optional = a1
    while a != nil {
        var st = "......."
        st.insert("@", at: st.index(st.startIndex, offsetBy: a!.x))
        bd[a!.y] = st
        a = a!.parent
    }
    bd.forEach {print("\($0)")}
    print("------------")
    num += 1
}

var num = 0
for i in 0..<N {solve(x: i, y: 0)}
print("\n\(num) answers.")

Swift はまだ全然慣れていないので、移植するだけなのに時間がかかってしまいました。普段は Ruby を使っているので、Swift の文字列処理の貧弱さには悩みました。それから、Optional型は Ruby にはないのでだいぶハマりました。深さ優先探索も最初どうやってコーディングしたらいいかわからなかったです。ただ、コンパイルが通ればおおよそ OK というのはさすがに静的型付け言語ですね。自分は Ruby で軽く実装してみて Swift に移植というのがよさそうです。

ちなみに、ベンチマークをとってみると Ruby よりべら棒に速いというほどでもないですね。このコードではせいぜい Ruby の二倍の速さくらいです。Swift らしく書けばまたちがうのかも知れません。
（追記：最適化オプションをつけてコンパイルすると、もう少し速くなります。Ruby版の三倍くらい。）
　
　
※参考
どこよりも分かりやすいSwiftの"?"と"!" - Qiita
Swift 2.0 で追加された guard のいいところ - Qiita
String - Swift Standard Library | Apple Developer Documentation