読者です 読者をやめる 読者になる 読者になる

tak0kadaの何でもノート

発声練習、生存確認用。

医学関連は 医学ノート

数独をコンピュータに解いてもらう(その1、アルゴリズム事始め)

アルゴリズム 数独

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

方針

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

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

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

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

2. 制約プログラミング

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

3. グラフ彩色問題

wikipedia電通大のスライドを見る。

4. ヒューリスティック

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

感想

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

参考

http://en.wikipedia.org/wiki/Sudoku_solving_algorithms
AlgorithmX with Python
Rで「充足可能性問題(3-SAT)を解く乱択アルゴリズム」