numberLinkのsolverをhaskellで作ってみた

以前ハッカソンで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から順に全探索を行うだけ。ただ、それだけだと処理量が多すぎるので枝刈りする。枝刈りの方法は以下の2つ。
1. 冗長な経路を排除
例えば以下のようになったら無駄な経路。Startが左下の1という想定。

000
110
110
100

この経路は以下の経路と同じことなのでnumberLinkのルール的に排除してよい。

000
000
110
100

現在見ている座標の隣接4マスに2つ以上自分と同じ番号があった場合は冗長な経路として判定している。

2. 孤立マスの存在
どの番号の経路としても使うことができないマスが生じた場合は探索打ち切り。
例えばこのような感じ。

000
110
100
100

この場合左上隅のマスは使うことができないため探索打ち切り。
直前にいたマスの隣接4マスに存在する0のマスを探し、そのマスの隣接4マスにある0のマスの数を計算し1つ以下なら孤立マスとして判定。

探索それ自体はリストモナドで処理。以下のsolveを>>=でつなげる。

solve :: CurrentState -> [CurrentState]

細かいところはこちらで。
numberlink/Main.hs at master · y-kamiya/numberlink · GitHub

9*9の問題を解くのに45secくらいかかる状態なのでもう少し改善してみようと思う。