Swiftで8人の女王
swift playgrouds での5番目のプログラミング。今回は8Queenパズル。
チェスのクイーンは、チェス盤上で最も自由に動けまわれるコマです。 縦横斜めの8方向に、任意の数だけ駒を進めることが出来ます。将棋でいう飛車と角を合わせた動きです。
このクイーンを8x8のチェス盤上に8個、お互いに取られないように配置するのが8Queenパズルです。
解法は 8Queen から見てゆくとわかりやすいです。
参考文献ではバックトラッキングの例題として書かれて素直に移植したつもりだった。 しかし書いているうちに、深さ優先の検索でなく広さ優先検索になっていた。
作ったクラスの動き
以下のようにチェス版の大きさを指定して、結果を出力させます。sizeは板の大きさです。8Queenなので8の大きさにしてます。
let queen = EQBoard(size:8)
let QueenAnser = queen.resolve()
QueenAnser.map{ $0.debugPrint() }
print("---\(QueenAnser.count)")
出力結果は以下のようになります。
q . . . . . . .
. . . . q . . .
. . . . . . . q
. . . . . q . .
. . q . . . . .
. . . . . . q .
. q . . . . . .
. . . q . . . .
q . . . . . . .
. . . . . q . .
. . . . . . . q
. . q . . . . .
. . . . . . q .
. . . q . . . .
. q . . . . . .
. . . . q . . .
q . . . . . . .
. . . . . . q .
. . . q . . . .
. . . . . q . .
. . . . . . . q
. q . . . . . .
. . . . q . . .
. . q . . . . .
.
.
.
. . . . . . . q
. . . q . . . .
q . . . . . . .
. . q . . . . .
. . . . . q . .
. q . . . . . .
. . . . . . q .
. . . . q . . .
---92
qの文字はQueenの位置を示しています。最後の–92は、結果が92パターンの配置があるとの結果です。
作ったクラスの中み
構造体の名前は “EQBoard” 、プロパティは2つ、メソッド数は 6つ。
初期化メソッドが2つ、デバッグメソッドが1つなので、計算をする部分は事実上3つのメソッドで行なっています。
で、メインの3つのメソッドは以下の通り。
- resolve
- ここで、解を求める
- boardAddAQueen
- 今の盤にqueenを1個追加した盤を返す。resolveの補助。
- tryAddAQueen
- 今の盤に配置可能かのチェックを行う。resolveの補助。
ソースはこんな感じ。
func resolve() -> [EQBoard]
{
precondition(queens.count <= self.sizeN)
func resolve_intarnal( _ count:Int, _ boards:[EQBoard]) -> [EQBoard]
{
if count == 0
{
return boards;
}
// 与えられた板の次のrawの配置の配列を計算する
return resolve_intarnal( count - 1,
boards.reduce([])// 計算結果を配列にひとまとめにする
{
let i = $1
return $0 + ( 0..<i.sizeN ) // 横のマスの数だけ、置いて試す
.flatMap
{
i.tryAddAQueen($0) ? i.boardAddAQueen($0) : nil
}
})
}
return resolve_intarnal(self.sizeN, [self])
}
// queenを1個追加した盤を返す
func boardAddAQueen(_ newQueen: Int) -> EQBoard
{
precondition(newQueen >= 0)
precondition(newQueen < self.sizeN)
precondition(queens.count < self.sizeN)
return EQBoard(size:self.sizeN, queens: self.queens + [newQueen])
}
// 配置可能かのチェックを行う
func tryAddAQueen(_ newQueen: Int) -> Bool
{
precondition(newQueen >= 0)
precondition(newQueen < self.sizeN)
// 縦方向と左右の斜めにQueenがないかチェックする
return ( self.queens.enumerated().map
{
( $0.element == newQueen) || /* 縦が一致 */
( $0.element == newQueen - self.queens.count + $0.offset ) || /* 斜め左方向が一致 */
( $0.element == newQueen + self.queens.count - $0.offset ) ? /* 斜め右方向が一致 */
false : true
}.filter{ $0==false }.count ) == 0
}
解説は、次回のCocoa勉強会で行います。じゃあね。
参考文献とソースコード
- Logo 人工知能へのアプローチ
- https://www.amazon.co.jp/Logo-人工知能へのアプローチ-ラジオ技術選書-150-祐安-重夫/dp/4844301500