ElmでN-Queenしてみた
説明
題名の通り、ElmでN-Queen問題をやってみました。リアルタイムにクイーンを配置していくので、アニメーションとして楽しめます。
N-Queen問題ではバックトラック法を使うわけですが、木構造を深さ優先探索していないので、厳密な意味でのバックトラック法ではないかなと思います。
N-Queenの場合、縛りのせいで最大2手戻ればすべて網羅できるので、そのせいで解けています。
2014-08-16追記: 良く考えるとツリーをすべて網羅しているということはバックトラック出来ているということですよね。
書いてて思ったのはやはりリストをがっつり扱えるElmという言語のパワーです。特にクイーンの配置をチェックする部分が物凄くきれいに書けます。
斜めチェック用のリストを生成している部分です。
-- left down to right top ldrtCoords w h = let xys = xyCoords w h in map (\(x, y) -> y - x) xys -- right down to left top rdltCoords w h = let xys = xyCoords w h in map (\(x, y) -> y + x) xys
それを使ってチェックします。
-- チェッカー関数 nはそれぞれチェックするグループIDを示す rowCheck n = filter (\(x, cellState) -> x == n) <| zip (yCoords bw bh) xyq colCheck n = filter (\(y, cellState) -> y == n) <| zip (xCoords bw bh) xyq ldrtCheck n = filter (\(ldrt, cellState) -> ldrt == n) <| zip (ldrtCoords bw bh) xyq rdltCheck n = filter (\(rdlt, cellState) -> rdlt == n) <| zip (rdltCoords bw bh) xyq checkFn = (>=) 1 -- チェックフラグ rowCheck' = all checkFn <| log "row" <| map (countQueens . rowCheck) [1 .. bw] colCheck' = all checkFn <| log "col" <| map (countQueens . colCheck) [1 .. bh] ldrtCheck' = all checkFn <| log "ldrt" <| map (countQueens . ldrtCheck) [(1 - bw) .. (bw - 1)] rdltCheck' = all checkFn <| log "rdlt" <| map (countQueens . rdltCheck) [2 .. (bw + bh)]
Cなどの手続き型で書かれたN-Queen問題のソースコードは結構ぐちゃっとしてる場合が多いと思うのですが、やはりここは関数型の簡潔さ・スマートさを感じますね。
ちなみにRosetta Codeというサイトでいろんな言語のN-Queen問題の解法を見ることができます。