Haskellの練習がてら数独solverを作成しました。

発端は読み進め中の関数プログラミング実践入門に数独solverのコードがあり、それを見る前に自分で書いてみたいと思ったからなのですが、やってみると自身の力不足を痛感しました。Haskellとしての書き方ももっと明快に書けないかと思うのですが、何より数独の解法が間違っている(というか不足している)ようです。

自分のアプローチでは

  • 各マスに埋められる数字を一覧にする(よくあるメモ書き的なイメージ)
  • 各Row, Column, Box(3x3の領域)に同じ数字は2度出現しないことから選択肢を減らす

という繰り返しでマスを埋めていました。これで確認する限りの数独は解けていたのでオッケーだと思っていたのですが、どうやら問題によっては「仮置き」、つまりあるマスにとりあえず数字を入れてみて探索を続けるという操作が必要になるみたいです。(実際自身のコードでは「世界一難しい数独」と称されるものを解くことはできませんでした)

関数プログラミング実践入門のコードでは「候補の少ないマスに数字を入れて探索を続ける」というような内容になっており、やはりそういったロジックが必要になるようです。Haskellの実装ではListモナドで深さ優先探索を端的に実装でき、なるほどという感じです。

上述したように現在のコードでは不十分な点があるのですが、コード全体はgistに。