月別アーカイブ: 2014年7月

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問題の解法を見ることができます。

続きを読む