川合秀実の数独研究に関するドキュメント#4
(11) sc125f （2018年02月ごろ）
- Exocetショックから1年間、私はq2 ratingに代わる難易度指標の自作に取り組んできました。
- それでようやくまあこんなものかと思えるレベルに達しました。それを説明します。
- (a)数独は正解を探すゲームではなく、ペンシルマークを消していくゲームである。
- 私はそれまで数独は「正解を探すゲーム」だと思っていました。だから問題が与えられたときに、正解に至る経路に注目し、そこまでに解法アルゴリズムが適用できない（＝仮置きが必要な）局面が何度あるかを重視していました。
- でも http://www.sudokuwiki.org/sudoku.htm などの数独ソルバーはそのようには問題を解きません。これらの数独ソルバーは列挙された解放テクニックを使って、「不正解のペンシルマークを消していく」ことで数独を解いていきます。だから正解に至る経路などどうでもいいのです。いかに不正解を不正解だと判断するのが困難になっているのか、つまりはそこなのです。
- ということで、sc125fでは盤面の不正解ペンシルマークのすべてに点数を付けます。このペンシルマークを不正解だと見抜くのはどれほど難しいのか、それだけを評価するわけです。
- そしてもっとも点数が低いところのペンシルマークを消します。そしたらまたその状態で残りの不正解ペンシルマークのすべてに点数をつけなおし、またその中で一番低いところを消して・・・ということをすべての不正解ペンシルマークが消えるまで繰り返します。こうしてすべての不正解ペンシルマークが消えるまでに最大で何点のペンシルマークを攻略する必要があったのかを覚えておいて、それをこの問題のスコアだとするのです。
- (b)全工程内での最大値のみを採用し、そこに至るまでの手間やそれ以降の手間の程度は一切加味しない。
- 一番難しい局面に至る前に、それよりは易しいテクニックをいくつか使わせるような問題はよく見かけますが、そういうときに、その分を評価して何らかの加算するべきかどうかという問題があります。sc125fでは加算しないことにしています。なぜなら私が重視しているのは、数独ソルバで解けるかどうかなのであって、それ以外の些細なことの積み重ねで、ソルバに解ける問題がソルバに解けない問題よりも難しいなどと誤判定するかもしれないリスクを避けたかったからです。
- (c)解法アルゴリズムをそのまま実装することはしない。
- 解法アルゴリズムをそのまま実装するのは、以前挫折しているので、これをやろうとはしていません。別の観点から解法アルゴリズムを整理して一般化し、解法の高度さをレベル分けして、難易度の計算に使っています。これについては後で詳しく説明します。
- (d)sc125fによる評価例。
- 細かい理屈よりも、具体的にどういう問題が評価されるのかを確認するほうがわかりやすいと思うので、まずは難問集の中の代表的な計算値を挙げます。
- カッコ内の数字は補助的な値で、本質的な意味はないので、気にしないでください。最初は25500点以上のもののリストです。
- 参考: 114*256+168=29352, 110*256+159=28319, ...
#01: 000000005020004070007090800000001000006050003040203000009000508070000010800030607 sc125=29352 (114:168)
#02: 000006000007100006860030000006500070000002061090060400300090600640000800002600050 sc125=28319 (110:159)
#03: 000000001000002030000040506000003080009010600020700000006050400070800000105000009 sc125=27311 (106:175)
#04: 003050009400000000080007100000600800300090002000001070504030020060000000032000005 sc125=27058 (105:178)
#05: 000000001000003020000060405000002080009040100030700000004050006070800000105000900 sc125=27052 (105:172)
#06: 000000001000002030004050600000003007050040800700090020060080000085600900107000000 sc125=26794 (104:170)
#07: 000000000000001002003040050030006007010203000800090030060700003305000800400030090 sc125=26549 (103:181)
#08: 000000001000003020000060405000002080009040500030700000004010600070800000501000009 sc125=26542 (103:174)
#09: 000004005000007010000380400009040300008290000050006000002400800010000007900000060 sc125=26539 (103:171)
#10: 000200000000001023002040500020006007010302000800090200060700002205000080400020900 sc125=26539 (103:171)
#11: 980700600500090000004000090300050000020800007000000100060100002000200800000030040 sc125=26301 (102:189)
#12: 000000006020004070007090800000001000006050003040203000009000508070000010800030607 sc125=26285 (102:173)
#13: 000000012000003400005040630004007300010800000900000001006005070020900003800070000 sc125=26284 (102:172)
#14: 980000000007900600000050000700400900006030020000005001070500800004010050000002003 sc125=26039 (101:183)
#15: 000000001000002030004050600000001070070000002800040900037005000608900500900080000 sc125=26037 (101:181)
#16: 000000001000002030004050600000001072070005000800040900037000000500060000609500800 sc125=26030 (101:174)
#17: 090400700408000039000000024030900070000050000100006900500008000040300007006010000 sc125=26030 (101:174)
#18: 000000003000004060000020105000006070009010500040800000001030200080700000305000009 sc125=26029 (101:173)
#19: 980700600700090080005000007600900040090050003002001000040800070000020001000003000 sc125=26026 (101:170)
#20: 000000001002003040050060700000002010003000084600800900004001050090700000800050000 sc125=26019 (101:163)
#21: 020400000007009000600030500000000000004001090800000301500060003000010608006700020 sc125=25779 (100:179)
#22: 000000001002003000040050060000070015001800970070000806009008000010060007300200000 sc125=25772 (100:172)
#23: 000000012000013040001200500004000005060007000830090000006400050090086000700000600 sc125=25770 (100:170)
#24: 000000001002003000040050060000040015070000806500800900009008000010060007300200000 sc125=25767 (100:167)
#25: 100400000000009002080030004200070003060000800500001020000000300004500090070060008 sc125=25761 (100:161)
#26: 000000012003004000050060700000003001004000025800500900002001060060800000700090000 sc125=25760 (100:160)
#27: 000000000001002003040050060000003007002807000970040000000100008060000970500070040 sc125=25515 (099:171)
#28: 003050700400009000000203000200001006000820500007030020060000004008300200900000010 sc125=25514 (099:170)
#29: 000001002070050090003400500001200000080060005700003000007000400090000057600070089 sc125=25514 (099:170)
(12) 二択数
(13) 解の個数判定ルーチン高速化競争 （2018年11月ごろ）
(14) 希少数字・純希少数字・希少二択
(15) 転置対称性・対角線対称性・市松対称性 （2018年12月ごろ）
![[K Wiki]](k.jpg "[K Wiki]")
