以前 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