sdk0003 のバックアップ(No.6) - K-kiwi

[ トップ | 一覧 | 単語検索 | 最終更新 | バックアップ | ヘルプ ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
sdk0003 へ行く。
- 1 (2019-04-03 (水) 13:50:33)
- 2 (2019-04-03 (水) 15:23:01)
- 3 (2019-04-04 (木) 09:58:50)
- 4 (2019-04-04 (木) 13:48:49)
- 5 (2019-04-04 (木) 16:20:03)
- 6 (2019-04-05 (金) 06:50:40)

川合秀実の数独研究に関するドキュメント#3

(by K, 2019.04.03)

(7) 御嶽型

御嶽型は、富士型の制約を少し緩めたものです。だから富士型はもれなく御嶽型でもあります。ヒント総数が21であることは変わりませんが、ヒントの出現回数は1～3回になり、1回を許すようになっています。
しかし御嶽型も新しい超難問を見つけることはできず、没になりました。

(8) 阿蘇型

阿蘇型は、ヒントの数字の配置が特徴的です。
一番上の行に含まれるヒントの数は1つです。2行目は2つです。3行目は3つです。この調子で9行目までを調べると、123-323-331になっています。
次に列を見てみます。一番左から同じように見ていくと、123-323-331になっています。つまり、行と同じパターンなのです。

上図のモデルとなったのは難問集にあった以下の問題です。

000000010230000000004500600000804500000090020007005008006008700010030090000400000  q2=98793

q2 ratingがあまり高くないのにどうしてこの問題に類似の問題を探そうと思ったのかというと、このころの私はq2 ratingに不信感を持っていて、富士型は実はそんなに難しい問題じゃないのではないかと感じ始めていたからです。それで独自の評価指標sc50というのを作って、それにおける難問集内の高得点問題がこれだったので、これをモデルにしたのでした。
しかし結局、その独自指標における最高得点は更新できず、結局私は難問集を全く超えられない状態が続きました。

(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月ごろ）

http://www.sudokuwiki.org/sudoku.htm に、Exocetという新しい解法が追加されました。いつ追加されたのかははっきりとはしていないのですが、201年10月には追加されていなくて、2017年02月には追加されていたので、この中のどこかで追加されたのだと思います。
このExocetは今までの解法とはケタ違いに強力で、人類の最終兵器といっても過言ではないくらいの強さを発揮します。そのため、なんと、
```
#33: 001000000000001230000450001060000000000070050005004003080000090904005002002903004  q2=99381
```
q2 ratingで33位の問題すら、「Take Step」の連打だけで解けるようになってしまったのです。

こ、これは・・・さすがに良くないと私は思いました。

以前よりq2 ratingに不満を感じていた私でした。例えば富士型の探索の時、以下のq1=802点の富士型問題を見つけたのですが（q2値は未測定だったので後日調べます）、この問題は「Take Step」の連打だけでは解けない問題で、「えー、連打で解けないくらいには難しい問題なのに、802点しかくれないのか？！」と思ったのです。
```
000010200000300040050006007140000000006000005075008000000200030000040100008007009  q1=00802
```

またこれは後日スパコンで渡辺さんが見つけてくれた問題ですが、

000020000100700080020000060003000900050300070200001003000103700009005200071009035  q2=95147

この問題は、Exocetなしでも「Take Step」の連打で解けてしまうのに、q2=95147という高い評価になってしまっているのです。

私はもうこれは決定的だと思いました。つまりq2は難易度指標としては不十分で、これの最高記録更新を頑張る必要はもうないと思ったのです。これに代わる難易度指標さえ示すことができれば。

q2 ratingの計算アルゴリズムによれば、q2はそもそも http://www.sudokuwiki.org/sudoku.htm の Extreme Strategies に示されているような高度な解法アルゴリズムを実装していません。
- それを実装するのは煩雑だと思ったのか、それとも人間はそんなテクニックを使わないで仮置き再帰をやるはずだから再帰の量だけをスコアにすればいいと思ったのか、そのあたりは不明です。でも逆に言うと、難しいテクニックを実装せずに判定している割には、結構よくできているとも言えます。

しかし、私は自分が見つけた難問がソルバの解法テクニックで突破されてしまったら、やっぱりがっかりしてしまいます。だから上級の解法テクニックに対しても強い難問を探せるような、そんな指標が欲しいと思いました。
それどころか、現在知られている既知の上級の解法テクニックに対して強いだけではなく、将来発見されるであろう未知の上級の解法テクニックに対しても強い問題が探せるような、夢のような指標が欲しいと思いました。これがあれば、将来新しい解法が見つかってもこの指標でのランキングの上位は脅かされることはなく、ずっと超絶難問として君臨し続けることができるのです。
結局、人間にとって難しいかどうかという基準で指標を作ると、主観が入ってしまいます。どういう問題が難しいかは、厳密には人によって違いがあると思うからです。だからもう人間がどう感じるかは全部無視して、解法テクニックに対しての強度をベースに難易度を定義したいと思ったのです。
これらをすべて満たしている夢の難易度指標が、次に紹介するsc125fです。

つづく

続きはこちら: sdk0004

こめんと欄

コメント	お名前	NameLink