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

つらねの日記

プログラムの進捗やゲームをプレイした感想などを書き連ねる日記。

Processingで数独の解に光明を

数独

縦・横の各列と太線の正方形内に同じ数字が入らないように1~9までの数字を各セルに入れていくパズルゲーム

本当はナンプレと呼ぶほうがいいらしい.

デジタルでやりたい

数独を解くにあたり,基本は紙で解くことが多いと思うが,そうすると紙がもったいない&間違えたときの処理がいろいろと面倒くさい.あと終ったときにちゃんとあってるかどうかを確認するのに99+99+9*9のセル確認が必要なので面倒くさい.

ということでパソコン上でできたら紙も無駄にならないし,便利だなと考えた.

欲しい機能

  • 解くときには,確定したセルと同じグループに属するセルから数字を消していくので1~9であとどの数字が残っているかを表示したい
  • 紙でやると1~9を小さく書いて,丸をつけるとかだったので分かりにくい.よって,確定した数字は大きく表示したい.
  • 終了した時にあっているかどうかをシステム側で判断してほしい.

もっと自動化したい

上記の機能を実装したところ,確定したセルと同じグループのセルを判断して一個一個ポチポチ消していくのも面倒になってきた.ならば確定したセルと同じグループのセルからその数字を消して欲しい.というかそれなら消したときにセルが確定したならそのセルについても同様にやって欲しい.

っていうか全部自動化すればよくないか?

完成品

というわけで,問題を入力すると,それの解を求めてくれるプログラムをProcessingで作った.

pv github.com

問題を数字キーで入力して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演算で数独の解を求めるプログラムになっていた. でも思ったよりも劇的な効果は得られなかったというのが正直な感想.

最近個人的なブームがsatsugarあたりなのでJ4Satとかで書いたりしてみたい.

余談ですが,

Sudokuという名前のディレクトリにしているのでcd(省略可能) Sudokuするときにsudo<TAB><ENTER>(kが遠い)とやろうとするため,sudoが意図せず発動してました.