川合秀実の数独研究に関するドキュメント#4
(11) sc125f （2018年02月ごろ）
- Exocetショックから1年間、私はq2 ratingに代わる難易度指標の自作に取り組んできました。
- それでようやくまあこんなものかと思えるレベルに達しました。それを説明します。
- (a)数独は正解を探すゲームではなく、ペンシルマークを消していくゲームである。
- 私はそれまで数独は「正解を探すゲーム」だと思っていました。だから問題が与えられたときに、正解に至る経路に注目し、そこまでに解法アルゴリズムが適用できない（＝仮置きが必要な）局面が何度あるかを重視していました。
- でも http://www.sudokuwiki.org/sudoku.htm などの数独ソルバーはそのようには問題を解きません。これらの数独ソルバーは列挙された解放テクニックを使って、「不正解のペンシルマークを消していく」ことで数独を解いていきます。だから正解に至る経路などどうでもいいのです。いかに不正解を不正解だと判断するのが困難になっているのか、つまりはそこなのです。
- ということで、sc125fでは盤面の不正解ペンシルマークのすべてに点数を付けます。このペンシルマークを不正解だと見抜くのはどれほど難しいのか、それだけを評価するわけです。
- そしてもっとも点数が低いところのペンシルマークを消します。そしたらまたその状態で残りの不正解ペンシルマークのすべてに点数をつけなおし、またその中で一番低いところを消して・・・ということをすべての不正解ペンシルマークが消えるまで繰り返します。こうしてすべての不正解ペンシルマークが消えるまでに最大で何点のペンシルマークを攻略する必要があったのかを覚えておいて、それをこの問題のスコアだとするのです。
- (b)全工程内での最大値のみを採用し、そこに至るまでの手間やそれ以降の手間の程度は一切加味しない。
- 一番難しい局面に至る前に、それよりは易しいテクニックをいくつか使わせるような問題はよく見かけますが、そういうときに、その分を評価して何らかの加算するべきかどうかという問題があります。sc125fでは加算しないことにしています。なぜなら私が重視しているのは、数独ソルバで解けるかどうかなのであって、それ以外の些細なことの積み重ねで、ソルバに解ける問題がソルバに解けない問題よりも難しいなどと誤判定するかもしれないリスクを避けたかったからです。
- (c)解法アルゴリズムをそのまま実装することはしない。
- 解法アルゴリズムをそのまま実装するのは、以前挫折しているので、これをやろうとはしていません。別の観点から解法アルゴリズムを整理して一般化し、解法の高度さをレベル分けして、難易度の計算に使っています。これについては後で詳しく説明します。
- (d)sc125fによる評価例。
- 細かい理屈よりも、具体的にどういう問題が評価されるのかを確認するほうがわかりやすいと思うので、まずは難問集の中の代表的な計算値を挙げます。
- カッコ内の数字は補助的な値で、本質的な意味はないので、気にしないでください。
- 参考: 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)
000004005000007010000380400009040300008290000050006000002400800010000007900000060 sc125=26539 lv1=103 pms1=171 time=43840000 sn=000327 clues=22
000200000000001023002040500020006007010302000800090200060700002205000080400020900 sc125=26539 lv1=103 pms1=171 time=30760000 sn=000044 clues=25 二択数=03 9+2x8=25型
980700600500090000004000090300050000020800007000000100060100002000200800000030040 sc125=26301 lv1=102 pms1=189 time=69130000 sn=000036 clues=21
000000006020004070007090800000001000006050003040203000009000508070000010800030607 sc125=26285 lv1=102 pms1=173 time=63460000 sn=000777 clues=23 二択数=05 転置＋対角線＋市松
000000012000003400005040630004007300010800000900000001006005070020900003800070000 sc125=26284 lv1=102 pms1=172 time=26960000 sn=002237 clues=23
980000000007900600000050000700400900006030020000005001070500800004010050000002003 sc125=26039 lv1=101 pms1=183 time=44030000 sn=000041 clues=22
000000001000002030004050600000001070070000002800040900037005000608900500900080000 sc125=26037 lv1=101 pms1=181 time=37060000 sn=000007 clues=22
000000001000002030004050600000001072070005000800040900037000000500060000609500800 sc125=26030 lv1=101 pms1=174 time=39890000 sn=000006 clues=22
090400700408000039000000024030900070000050000100006900500008000040300007006010000 sc125=26030 lv1=101 pms1=174 time=28750000 sn=000290 clues=23
000000003000004060000020105000006070009010500040800000001030200080700000305000009 sc125=26029 lv1=101 pms1=173 time=29550000 sn=000019 clues=21 二択数=06 転置＋対角線＋市松
980700600700090080005000007600900040090050003002001000040800070000020001000003000 sc125=26026 lv1=101 pms1=170 time=31530000 sn=000017 clues=23
000000001002003040050060700000002010003000084600800900004001050090700000800050000 sc125=26019 lv1=101 pms1=163 time=29500000 sn=000043 clues=22
020400000007009000600030500000000000004001090800000301500060003000010608006700020 sc125=25779 lv1=100 pms1=179 time=37570000 sn=000460 clues=22
000000001002003000040050060000070015001800970070000806009008000010060007300200000 sc125=25772 lv1=100 pms1=172 time=34260000 sn=000007 clues=23
000000012000013040001200500004000005060007000830090000006400050090086000700000600 sc125=25770 lv1=100 pms1=170 time=23220000 sn=000731 clues=23
000000001002003000040050060000040015070000806500800900009008000010060007300200000 sc125=25767 lv1=100 pms1=167 time=33650000 sn=000032 clues=22
000002001030000040005040600000600050002030900600007008009070400070100000800003007 sc125=25766 (100:166) clues=23 二択数=07 川合の作問#2 [2018.12.04(月)] 転置
100400000000009002080030004200070003060000800500001020000000300004500090070060008 sc125=25761 lv1=100 pms1=161 time=37770000 sn=000952 clues=22
000000012003004000050060700000003001004000025800500900002001060060800000700090000 sc125=25760 lv1=100 pms1=160 time=25700000 sn=000058 clues=22
000000000001002003040050060000003007002807000970040000000100008060000970500070040 sc125=25515 lv1=099 pms1=171 time=35990000 sn=000050 clues=22
003050700400009000000203000200001006000820500007030020060000004008300200900000010 sc125=25514 lv1=099 pms1=170 time=33490000 sn=000047 clues=23
000001002070050090003400500001200000080060005700003000007000400090000057600070089 sc125=25514 lv1=099 pms1=170 time=25600000 sn=000516 clues=24 転置
(12) 二択数
(13) 解の個数判定ルーチン高速化競争 （2018年11月ごろ）
(14) 希少数字・純希少数字・希少二択
(15) 転置対称性・対角線対称性・市松対称性 （2018年12月ごろ）
![[K Wiki]](k.jpg "[K Wiki]")
