1回生か2回生か忘れたが工学部の授業ではCで数独を解かせるらしい。一般教養レベルの問題ということらしいが結構難しいと思う。(単純に実装したらif文の塊になってしまう)

方針

ググってたら山ほど方針が見つかった。結局全部一緒に見えるが

ぐらいにまとめられそう。

1. 総当りとその仲間たち

普通に解いたらこのあたりの解法になりそうである。

総当り
全場合の数をもれなくしらみ潰しにする
バックトラッキング
木探索していて解でないと分かった組み合わせは計算しない。深さ優先探索(DFS)と同義。 stackoverflowを見ていると、グラフと見る方法では他に反復深化深さ優先探索(IDFS)、A*アルゴリズムもある。
Knuth's Algorithm X
dancing linksというデータ構造を使ってうまくとく。名古屋大の授業スライドも同じ方針に見える。

数独のマスを埋めていく作業を制約の伝播と捉える。制約充足問題についてのゆるふわな話によると、CSPソルバに丸投げしてしまうのが良さそう。 SAT ソルバで数独を解く方法に分かり良い解説とrubyのプログラム例がのっている。制約を式に落とすのが面倒くさそうだがHaskellでうまいことやっているQiitaの例

あんまり日本語で情報がない。wikipedia見る。

方針がたくさんありすぎて目が回る。応用範囲が一番広そうなグラフを使うものを明日実装するところからはじめる。