バックトラックとリストモナド - 取り急ぎブログです

ここ2-3週間、暇を見つけては数独ソルバーをHaskellで書いていました…動くもの自体ができるまではそんなにかからなかったのですが（と、一応言っておいて…）、プロファイルをとりながら高速化していくステップで色々と試行錯誤があって、自分的には「なるほどねー」と思ったところがあったりしたので、何回かに分けて書いていきたいと思います。

まずはじめはバックトラッキングの話…

ほかにも色々と種類があるようですが、僕がやったことがある数独は９ｘ９のやつで、僕の頭で楽しく解けるやつはすでに埋まっているマスによる制約をたどっていくだけで全てのマスが埋まってしまうやつなわけです。更に難易度が上がってくると、それだけでは全てのマスの値が決定しなくて、いわゆる｢試行錯誤｣をやることになるわけです。マスaは[1, 5, 6, 7]のどれか一つになるということがわかっていても、それ以上の情報がない場合は、可能な選択を順番に全てのマスが埋まるまで試すという作業が必要になります。

こういった作業をプログラムにさせるのに一般的な考え方はバックトラッキングというやつなわけですが、
例えば未確定なマスが3つあったとすると、

a [1, 5, 6], b [5, 3, 4, 7], d[6, 8, 9]
　　a = 1, b [5, 3, 4, 7], d[6, 8, 9]
　　　　b = 5, d [6, 8, 9]
　　　　b = 3, d [6, 8, 9]
　　　　b = 4, d [6, 8, 9]
　　　　　　:
　　a = 5, b [3, 4, 7], d[6, 8, 9]
　　　　:
　　a = 6, b [5, 3, 4, 7], d [8, 9]
　　　　:

といったように試行するべき組み合わせがツリー構造になってくるわけで、バックトラッキングはこのツリーを深さ優先でトラバースしていく作業とも言えるわけですね…ただ、トラバースといっても一つの試行を試すたびに数独のグリッド全体の内容を更新していかなくてはならないし、その作業をやって初めてその下のレベルののツリー構造が見えてくるので、ツリー構造をしたデータのトラバースほど直接的ではないわけです。

C/C++なんかでバックトラックをやるときは再帰呼び出しを良く使うわけで、すごくいい加減に書けば

bool try(…)
{
	for (int i = 0; i < cChoices; i++)
	{
		if (try (choice[i], …))
		{
			return true;
		}
	}
	
	return false;
}

見たいなことをやるわけですよね…
もちろんHaskellでも同じようなコードを書くことは簡単にできますね…Immutableなデータ型がデフォルトなHaskellではC/C++なんかでバックトラックを書くよりも簡単に書くことができてしまいます…C/C++では往々にして内側のtryが失敗した後にステートの巻き戻しみたいなことをしなくてはいけなかったりするわけで、だからDancingLinkというアルゴリズムがとても強力だったりするわけなんですが…

Haskellでは再帰の格段でデータを変更するたびにコピーが作られているような感じなわけで、メモリーをいっぱい使うけどステートの巻き戻しのことをまったく考えなくて良いわけです…おまけにコピーのほうも何か変えるたびに全てがコピーされるわけではなくて、変化していない部分に関してはある程度のデータ共有なんかもされたりするのが有効なときもあります。

ソルバーを書いていて僕も当然のようにバックトラックのコードを書き始めたのですが、最初に引っかかったのはtry関数のシグネチャでした…ｔｒｙの結果、失敗する可能性もあるので、最初に考えたのは

try :: [Choice] -> SudokuBoard -> Maybe SudokuBoard

だったわけなんですが、帰り値がMaybeだとmapMしたときにNothingが帰ってきた時点でマップが停止してしまいます。僕がやりたいのは逆でNothingが帰ってきているうちはMapを継続して欲しいわけです。うーん、とちょっと考えてやってみたのが

try :: [Choice] -> SudokuBoard -> [SudokuBoard]

です。リストはモナド的に使ったときは

[1, 3, 4] >>= \x -> (replicate x 1)
==> concat $ map (\x -> replicate x 1) [1, 3, 4]
==> concat [[1], [1, 1, 1], [1, 1, 1, 1] ]
==>[1,1,1,1,1,1,1,1]

という動きをしてくれます。つまり、一つのデータから0-ｎ個のデータを返すことができて、それが元のデータを置き換えてくれるわけです。今まで何でこんな不思議なことやってるのかなーと思っていたのですが、この場面ではこの動きが恐ろしく有効です。ｔｒｙの結果、失敗したら[]、成功してもまだチョイスがあったら[choice1, choice2, choice3]とやれば勝手に元のリストに混ぜ込んでくれるわけです。ということでｔｒｙは概略的には次のように書くことができます。

try ::  SudokuBoard -> [SudokuBoard]
try sb = choices >>= updateBoard sb >>= try
	where
		choices = findChoices sb

updateBoard :: SudokuBoard -> Choice -> SudokuBoard
  :

Choiceが消えてしまったのですが、これはSudokuBoardから毎回計算するようにしたからです。こうすることによってバックトラックがとてもシンプルなコードでできるようになりました。

更に強力なのは、このｔｒｙは正解を一つ持って帰ってくるだけではなくて、全ての正解を探すコードにもなっていて、HaskellのLazyさのおかげで、正解をどれだけ探すかはｔｒｙの帰り値を使う側に完全に任されていることです。

そんなにたいしたことじゃないのかもしれませんが、僕はかっこいいなーと思ってしまいました。具体性を書く文章になってしまいましたが要点が伝わればよいなと思います…

ではでは。