川合秀実の数独研究に関するドキュメント#3
(7) 御嶽型
- 御嶽型は、富士型の制約を少し緩めたものです。だから富士型はもれなく御嶽型でもあります。ヒント総数が21であることは変わりませんが、ヒントの出現回数は1〜3回になり、1回を許すようになっています。
- しかし御嶽型も新しい超難問を見つけることはできず、没になりました。
(8) 阿蘇型
(9) 妖精型 （2016年05月ごろ）
- 富士型にせよ阿蘇型にせよ、私はそれまで55万問の難問集の中から特徴がある問題を見つけて、それをモデルとして類似の問題を探すということをしてきました。しかし妖精型は、「こういう性質の問題が存在したらいいのに」という願望で、実在のモデルが見つからないところから出発したので、「妖精」と命名しました。・・・順を追って説明します。
- 阿蘇型を作るときはq2 ratingに不信感を持って独自のsc50での評価を試みた私でしたが、このころはまたq2に戻っていました。結局まずは既存の定番指標であるq2での最高値を更新して見せて自分たちはそれくらいの実力はあると示した上じゃないと、独自指標をいきなり提唱して、それに基づく最高の難問はこれだとか言っても、自作自演でしかないよな、と思ったからです。
- 最初はq2 ratingで#07だった富士型を再掲するところから説明を始めます。
- これのABCボックス行に注目してください。前述のとおり、ここには7つのヒントがありますが、そのヒントに重複は全くありません。そしてボックス内のヒント数に注目すると、これは「重複なしの3-1-3型のボックス行」だといえます。
- 同様にGHJボックス行は「重複なしの3-1-3型のボックス行」ですし、123ボックス列は「重複なしの3-1-3型のボックス列」で、789ボックス列は「重複なしの3-1-3型のボックス列」です。
- このように私は、重複がなくてヒントを7つ含むようなボックス行・列に注目してみたのです。
- #07の問題は、重複なしの3-1-3型が合計で4つあり、残りの2本は重複ありの1-5-1型でした。ボックス行・列は全部で6本なので、これで全部です。
- では他の上位問題はどうでしょうか？特に重複なしに注目します。
#01: 000000001000002340003010250001005004060000700800900000002004003070080000900600000 q2=99743 重複なしの2-3-2型x2, 重複なしの3-1-3型x2
#02: 000000001000002340003000250001005604060070000800600000002004005090800000700090000 q2=99587 重複なしの3-1-3型x2
#03: 280100700700020030005000200400060000010507000007008000300090400004000003000000069 q2=99578
#04: 000000012000000003002300400001800005060070800000009000008500000900040500470006000 q2=99551 重複なしの3-1-3型x1
#05: 980700600007090050000000907400300020006020500000001000100004000030800000002070005 q2=99516 重複なしの3-1-3型x1
#06: 980700000600090000005008900500004600004070030000200001050007800000300020000010007 q2=99508 重複なしの3-1-3型x1
#07: 000100020000030400005006007400000000086007000709000005000400300000020010060008009 q2=99480 重複なしの3-1-3型x4
#08: 000000120000003040004020003500006000070000008009010300600007000030500009001080030 q2=99421 重複なしの2-3-2型x1, 重複なしの3-1-3型x1
#09: 000010200000300040005006007008000090060008000570000008000200030006003009300040100 q2=99420 重複なしの3-1-3型x1
#10: 000000100000020003004001056407000000006100800090005060700006040009010002040300008 q2=99417
- このように、この構造を含んでいる難問は上位問題に多くみられることがわかります。q2 ratingはこの構造が好きみたいです。
- さらにここで出てきたボックスにも特徴があります。3-1-3型や2-3-2型を構成するそれぞれのボックスに注目すると、ボックスには3本の行と3本の列がありますが、どの行や列をとってもヒントの個数は0〜1であり、2以上は一つもないのです。そういうボックスを3つ集めたボックス行、ボックス列になっているのです。
- ここで私は思いつきました、「重複なしの3-1-3型x2, 重複なしの2-3-2型x4」な問題を作問することは果たして可能なのだろうかと。そしてもしこれに成功したら、とんでもない高得点が出るのではないかと。
- 以上をまとめると「妖精型」はこうなります。
- 青の数字は固定して、緑の場所は位置は固定だけど数字は不明、そして黄色の数字については位置も数も不明ということで、重複が全く起こらないように全探索して、解が1つのものがあるかどうかです。
- （上記の画像例では重複があるので妖精型にはなっていません。あくまで説明用の画像です。）
- 55万問の難問集の中にはこれに該当するものは入っていませんでした。
- 最初の解決すべき問題として、「そもそも妖精型は一つでもいいから存在するのか？」というのがあります。・・・答えはyesでした。以下の問題は妖精型の要件を満たしています。しかしq2 ratingとしてはかなり雑魚です。
000100000050020009400003700100000400020090050003000006000400000007050002090006800 q2=05741 （でも「Take Step」連打では解けない）
- そしてこの妖精型をすべて探しつくすという全探索プロジェクトが始まり（妖精狩り）、これは富士型のとき以上に盛り上がりました。私の理解が追いつくより前に問題の対称性を使って重複するパターンを排除する仕組みが考え出されて、ついにはスパコンで全探索が実施されて成功したのです。・・・そして注目の最高得点はこれでした！
800100007000020000060003050400000200050090060007000008000400100003050090020006000 q2=98755 （これも「Take Step」連打では解けない）
- 難問集の中にない難問を見つけたという意味では快挙でしたが、q2=99000にすらいかない結果になりました。・・・これじゃあまだまだです。・・・くうう・・・。
- しかし、難問集から高得点になっている実例を確認できないうちから、「かくかくしかじかの理由でこの形を探せば高得点が取れるのではないか」と理論構築し、そして実際に全探索でq2=98000を超える問題が見つかったわけです。
- 渡辺さんの経験では、パターンを仮定しない場合は、工夫して探してもq2=98000を終える問題は一つも見つからない、とのことでしたので、私のパターン戦略はその有効性を改めて認められました。
- また私のパターン探しのスキルも一定の信頼が得られるようになりました（パターン職人になったわけです・・・笑）。
(10) Exocetショック （2017年02月ごろ）
- こ、これは・・・さすがに良くないと私は思いました。
- 私はもうこれは決定的だと思いました。つまりq2は難易度指標としては不十分で、これの最高記録更新を頑張る必要はもうないと思ったのです。これに代わる難易度指標さえ示すことができれば。
- q2 ratingの計算アルゴリズムによれば、q2はそもそも http://www.sudokuwiki.org/sudoku.htm の Extreme Strategies に示されているような高度な解法アルゴリズムを実装していません。
- それを実装するのは煩雑だと思ったのか、それとも人間はそんなテクニックを使わないで仮置き再帰をやるはずだから再帰の量だけをスコアにすればいいと思ったのか、そのあたりは不明です。でも逆に言うと、難しいテクニックを実装せずに判定している割には、結構よくできているとも言えます。
- しかし、私は自分が見つけた難問がソルバの解法テクニックで突破されてしまったら、やっぱりがっかりしてしまいます。だから上級の解法テクニックに対しても強い難問を探せるような、そんな指標が欲しいと思いました。
- それどころか、現在知られている既知の上級の解法テクニックに対して強いだけではなく、将来発見されるであろう未知の上級の解法テクニックに対しても強い問題が探せるような、夢のような指標が欲しいと思いました。これがあれば、将来新しい解法が見つかってもこの指標でのランキングの上位は脅かされることはなく、ずっと超絶難問として君臨し続けることができるのです。
- 結局、人間にとって難しいかどうかという基準で指標を作ると、主観が入ってしまいます。どういう問題が難しいかは、厳密には人によって違いがあると思うからです。だからもう人間がどう感じるかは全部無視して、解法テクニックに対しての強度をベースに難易度を定義したいと思ったのです。
- これらをすべて満たしている夢の難易度指標が、次に紹介するsc125fです。
つづく
こめんと欄
|
![[K Wiki]](k.jpg "[K Wiki]")
