川合秀実の数独研究に関するドキュメント#2
(4) 富士型 （2015年07月ごろ）
- そうこうしているうちに大した成果も出ないまま、2年が過ぎていました。
- 私の仮説として、難問は何らかのパターンを有しているというのがあります。・・・つまりこういうことです。高得点の難問を集めてじっと見つめていると、共通のパターンが見えてきて、そのパターンを見出した後は、そのパターンを有する問題を大量生産してgsf's -q2 ratingをひたすら計算すれば、きっと未知の超絶難問を見つけることができるだろう、ということです。
- 要するに「既知の難問に似た問題を作りまくっていれば、そのうち何とかなるでしょう、・・・何とかなったらいいな、・・・何とかなってくれ！」という安直なアイデアです（笑）。
- いやだって、もう自分たちの計算力を考えたら、全探索なんて全く望めないわけで、そうなれば「（正解が）ありそうなところを必死で探す」しか戦略はないわけです。
- 富士型がどういう形なのか当初はわかっていなかったのですが、研究が進むにつれて簡潔に表せるようになってきました。ここでは簡潔に紹介します。
- この図は、q2=99480の問題を同値変形（後述）して、 http://www.sudokuwiki.org/sudoku.htm に入力して見やすくしたものです。
- この中で数字の背景が青のものは、位置だけではなく数字の値もこの値に固定できます。
- 緑の背景は、位置は固定ですが、数字の値は問題によって変わる部分です。
- 黄色の部分は、位置も値も変わる部分です。
- なぜこのパターンに注目したかですが、まずA〜C行を3行まとめた「ボックス行」（勝手に命名）に注目してください。この中にあるヒント数字は、7つあります。・・・これは同様に、D〜Fのボックス行やG〜Jのボックス行にも当てはまります。さらに、1〜3列をまとめたボックス列、4〜6列をまとめたボックス列、7〜9列をまとめたボックス列についても、ヒント数字はきっかり7つです。
- したがって自動的にこの数独問題の総ヒント数は21になるわけですが、だからこの数独問題はどのボックス行・列にも均等にヒントが配されていることになります。
- また中央のヒントを5つ含んでいるボックスはちょっと特別なので除外して、それを含まない4本のボックス行・列については、7つのヒント数字は全く重複がありません。
- また使われているヒント数字の出現回数ですが、どれも2〜3回になっています。これは、9種類の数字があって数字は全部で21回出さなければいけないとすると、均等な出現回数を目指せば同じ数字は2〜3回出るしかないわけですが、まったくその通りになっているのです。
- おおなんと美しい！・・・美しいといえば富士山ですよね、だから富士型と命名しました。
- 私はq2ランキングの上位問題をぼんやり眺めていて、ヒント数=21の問題に注目してみたら、いくつかがこの「どのボックス行・列にも均等にヒントが配されている、かつボックスごとのヒント数は、5個ボックスx1,3個ボックスx4,1個ボックスx4になっている」パターンがあることに気付き、それを同値変形しまくって、上図の一般化に成功したのでした。
- さてここまで限定できれば、あとは総当たりで問題を作ってq2のratingを計算するだけです。・・・結果は・・・結局、99480を超えることはできませんでした。つまり富士型の最高得点は、#07の問題で、既出だったのです。
- しかし富士型に関する研究は、私たちを大いに盛り上げました（特に私が盛り上がりました）。パターンを見出して探しまくるという手法が一通りやれたわけです。・・・何よりまずパターンを見つけたときに、ものすごく盛り上がります。これはいける！と思うわけです。そして探索プログラムを走らせて、次こそは未知の超難問が出力されるんじゃないかと、すごくわくわくするわけです。・・・そしてそんなものが出てこないと判明すると「ああ、このパターンはすでに掘りつくされていたのか・・・」と思うわけです。
- この富士型の探索も含めて、一般に私の探索のやり方の場合、コンピュータの処理時間の大半は「解の一意性判定」になります。これは自分の決めたパターンに数字を配してみても、それだけでは数独の問題として成立しているとは限らないので、解はあるのか、解があったとしてもその解はちゃんと一つだけになっているのか、を確認しなければいけないのです。これが探索処理全体としては一番CPU時間がかかるのです。
- パターンなんかに頼らず、まず数独の解（81マスがすべて埋まったもの）を用意して、そこから数字を抜いて作問する方式なら、少なくとも解が0個になる心配はありません。そうすると高速化できそうなのですが、その場合はパターンを満たしていない数独問題がいくつもできてそれを捨てなければいけなくて、むしろ遅くなってしまうので、私のやり方には使えないのです。
(5) 数独の同値変形について
- 数独は、A行とB行をごっそりと全部入れ替えても、難易度は全く変わりません。それぞれの空きマスへのヒントやマス同士の排他関係などが何も変わらないためです。・・・しかし、A行とD行の入れ替えは同値変形ではありません。それは関係するボックスが違ってしまうからです。
- またABCボックス行とDEFボックス行をごっそりと全部入れ替えても、難易度は変わりません。・・・しかし、ボックスを勝手に入れ替えるのはもちろんアウトです。ボックス行ごと入れ替える（もしくはボックス列ごと入れ替える）からこそ許されるのです。
- ほかに、左右を反転したり上下を反転したり、対角線を軸に反転したり（＝転置）、どれも同値変形になります。
- また数字の付け替えも問題の難易度を全く変えません。
- ちなみに、この同値変形をいくら行っても、上記に挙げた富士型の性質（ボックス列内のヒント数など）は不変に保たれます。
(6) 総ヒント数=17はそんなに難しくない
つづく
こめんと欄
|
![[K Wiki]](k.jpg "[K Wiki]")
