数独のテクニック勉強中

最近プログラミングのネタがなくて暇してたら、思いついた。以前数独を解くプログラムを作ったことがある。
あれはバックトラックを使うことで、絶対に解けるけど時間がかかる。
確かMacBook Proで0.1秒程度だったけど、iPhone4では1秒くらいかかった気がする。
目標としてはiPhone4で0.3秒以内くらいのものを作りたい。
CPUが高速化したiPhone5でやってもおもしろくないし。
本来、バックトラックを使ったものは人間がやると超めんどくさくて時間かかるけど、コンピュータにやらせるのは簡単。
ならばコンピュータに人間のテクニックを使わせたら速いんじゃね?というのが発端。

まず自分がナンプレを解く手順をプログラムでやってみた。
スタックと再帰でバックトラックさせるのはすごい簡単でシンプルなコードだったけど、人間の手法は複雑だなぁ……
で、俺のレベルではナンプレ道場というサイトの上級まで解けた。
超上級はルールが違うのでスルー。
「ナンプレ 難問」で検索して出てきた超難問ナンプレ自動生成出題で生成した問題をやってみた。
解けない。

 

俺の手法は基本ルールに基づくものばかりだったから、いろんなナンプレの解説サイトを見て勉強することにした。
そこで使えそうなのがn国同盟とか定員確定と呼ばれるもの。
定員確定はこれ以降の上級テクニックの基本となるらしいけど、定員確定の定義というか、方法がよくわからん……
例えばある2つのマスの両方に[1, 5]が入る可能性があるとして、他のマスには[1, 5]は入らない、というのはわかる。
3つのマスに[1, 2] [1, 3] [2, 3]が入る可能性があるとしたら他のマスに[1, 2, 3]は入らない、というのがよくわからん。
いや、実際当てはめたらそうなるんだけど、解説サイトだともっと複雑な組み合わせでこれがこう成り立ちますとか書かれても、理解できない。
そして上の例をソースコードでどう表現しようかというのも思いつかない。

 

実はそろそろ飽きてきた。
一応、もう何も思いつかないってとこまではやりたいから、Illustratorでこんなの作ってみた。

numple

これをiPadのPenultimateとか、画像を読み込むことのできるお絵かきアプリとかで使うと便利。
定員確定とかの候補の数字を探すという用途に限っては

関連記事:


コメントを残す

メールアドレスが公開されることはありません。

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <img localsrc="" alt=""> <pre class="" title="" data-url=""> <span class="" title="" data-url="">