以前ハッカソンでnumberLinkのsolverを書いたことがあったが、ちょうどアルゴリズムの勉強がてらC++を勉強中だったので、そのときはC++で書いた。完全に手続き的な書き方だが。今回それを読みなおしてhaskellで書きなおしたので全体の概要やアルゴリズムについてメモしておく。
まず入力はこれ。
1....3 ..4... ...... .321.. ...... 2....4
そして出力はこれ。
133333 134444 132224 132124 111124 222224
定義したデータ型
type Pos = (Int, Int)
data Cell = Cell {
cState :: CellState
, cType :: CellType
} deriving (Eq,Show)
data CellState = Empty | Number Int deriving (Eq,Show)
data CellType = Start | Goal | Normal deriving (Eq,Show)
type Field = M.Map Pos Cell
type CurrentState = (Int, Pos, Field)numberLinkの問題全体をFieldという名前にして、座標と各マス（Cell）の状態をMapで表現した。
各Cellの状態は入っている値（CellState）とそのCellの役割（CellType）。CellTypeは入力に含まれる値のどちらがStart, 他方がGoalとなるようにする。その他はすべてNormal。
CurrentStateは現在探索している番号、注目している座標、Fieldの状態のタプルで、これを各処理の引数として引き回す。
処理自体は1から順に全探索を行うだけ。ただ、それだけだと処理量が多すぎるので枝刈りする。枝刈りの方法は以下の２つ。
1. 冗長な経路を排除
例えば以下のようになったら無駄な経路。Startが左下の1という想定。
000 110 110 100
この経路は以下の経路と同じことなのでnumberLinkのルール的に排除してよい。
000 000 110 100
現在見ている座標の隣接４マスに２つ以上自分と同じ番号があった場合は冗長な経路として判定している。
2. 孤立マスの存在
どの番号の経路としても使うことができないマスが生じた場合は探索打ち切り。
例えばこのような感じ。
000 110 100 100
この場合左上隅のマスは使うことができないため探索打ち切り。
直前にいたマスの隣接４マスに存在する0のマスを探し、そのマスの隣接４マスにある0のマスの数を計算し1つ以下なら孤立マスとして判定。
探索それ自体はリストモナドで処理。以下のsolveを>>=でつなげる。
solve :: CurrentState -> [CurrentState]
細かいところはこちらで。
numberlink/Main.hs at master · y-kamiya/numberlink · GitHub
9*9の問題を解くのに45secくらいかかる状態なのでもう少し改善してみようと思う。
