Processingで数独の解に光明を
数独
縦・横の各列と太線の正方形内に同じ数字が入らないように1~9までの数字を各セルに入れていくパズルゲーム
本当はナンプレと呼ぶほうがいいらしい．
デジタルでやりたい
数独を解くにあたり，基本は紙で解くことが多いと思うが，そうすると紙がもったいない&間違えたときの処理がいろいろと面倒くさい．あと終ったときにちゃんとあってるかどうかを確認するのに99+99+9*9のセル確認が必要なので面倒くさい．
ということでパソコン上でできたら紙も無駄にならないし，便利だなと考えた．
欲しい機能
- 解くときには，確定したセルと同じグループに属するセルから数字を消していくので1~9であとどの数字が残っているかを表示したい
- 紙でやると1~9を小さく書いて，丸をつけるとかだったので分かりにくい．よって，確定した数字は大きく表示したい．
- 終了した時にあっているかどうかをシステム側で判断してほしい．
もっと自動化したい
上記の機能を実装したところ，確定したセルと同じグループのセルを判断して一個一個ポチポチ消していくのも面倒になってきた．ならば確定したセルと同じグループのセルからその数字を消して欲しい．というかそれなら消したときにセルが確定したならそのセルについても同様にやって欲しい．
っていうか全部自動化すればよくないか?
完成品
というわけで，問題を入力すると，それの解を求めてくれるプログラムをProcessingで作った．
問題を数字キーで入力してENTERを押すと解を求めてくれる． 一応元来の目的の援助ツールとしても有用な作りにはなっていると思う．
仕組みとか
public class abstract Solve implements Runnable
- 解いているときに主Theadが止まってしまうと困るので
Runnableに． - 解く手法は幾つかあるのでSolveをextendsしてつかえるようにabstract methodを作成
- これの子クラスとして消去や二国同盟だとかそれぞれを実装すれば完全分離できてかっこいい
111111111 -> 000000001
データ構造
各セルには9bitの変数を持たせる．1bitごとに1~9の整数が残っているかどうかを表わす． 初めは111111111からスタートして段々消していき，000000001などといった，1bitのみが立っている状態になったとき，確定セルといえる．
ex
111111111 = 全て 111111011 = 3ではない 000000011 = 1か2 000000010 = 1で確定
数字の削除
同じグループに属するセルからその数字を消すとき，bitを使うといい感じに書ける． 確定セルのbitの反転と&算をとると，綺麗にその数だけが消える． 既に消えていた場合には悪影響が全くない．
ex
111011011 = 3と6でない 100000000 = 9を消したい 011111111 = 9のbit反転 1,3式で&算 011011011 = 3,5,9でない 000000001 = 1で確定 011111111 = 9の反転 000000001 = &算をとっても影響しない
エラーがないか
同じグループに属するセルを全て足しあわせたものと，全てから算をとったものが，111111111になるとき，正しいと言える．
ex
000000001 000000010 000000100 ... 100000000 これらはorでも+でも111111111になる 000000001 000000001 000000100 ... 100000000 あやまって2が1になってしまった場合は111111111にならない
まとめ
数独を解くときの支援ツールを作ろうとしていたら，bit演算で数独の解を求めるプログラムになっていた． でも思ったよりも劇的な効果は得られなかったというのが正直な感想．
最近個人的なブームがsatやsugarあたりなのでJ4Satとかで書いたりしてみたい．
余談ですが，
Sudokuという名前のディレクトリにしているのでcd(省略可能) Sudokuするときにsudo<TAB><ENTER>(kが遠い)とやろうとするため，sudoが意図せず発動してました．
