sdk0000 のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
sdk0000 へ行く。
- 1 (2019-04-01 (月) 17:41:23)
- 2 (2019-04-01 (月) 19:44:57)
- 3 (2019-04-01 (月) 21:49:13)
- 4 (2019-04-02 (火) 07:07:38)
- 5 (2019-04-02 (火) 08:50:03)
- 6 (2019-04-02 (火) 16:46:00)
- 7 (2019-04-04 (木) 07:38:58)
- 8 (2019-04-04 (木) 15:43:10)
- 9 (2019-04-04 (木) 15:43:10)
- 10 (2019-04-08 (月) 19:39:51)

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

(by K, 2019.04.01)

↑

(1) はじまり

川合は、2013年の7月くらいから、東京大学の渡辺宙志さんの数独の難しい問題を作る研究にjoinしています。
- スパコンで力任せに数独の難しい問題を作ったつもりが簡単な問題だった件
- http://web.archive.org/web/20180708045022/http://apollon.issp.u-tokyo.ac.jp/~watanabe/sample/sudoku/index_j.html
この研究に誘ってもらえたきっかけは、
- (1)私と渡辺さんは、2002年度未踏ユースの同期生だったこと、
- (2)数独の高速化」という記事を2012年の12月に書いていたこと、
  - https://blog.cybozu.io/entry/1692
の二つです。

この後とても楽しい経験ができたので、本当にいいきっかけがもらえたと思っています。

↑

(2) gsf's rating 以前

初期の方針は、渡辺さんが最初に発表した難問が「コンピュータで解くにはたくさんの再帰呼び出しを要するのにもかかわらず、一般的な数独解法を使うだけでスイスイと解けてしまった」ことに着目して、「一般的な解法が適用できるときはそれをどんどん使って、行き詰まったら再帰させることにして、その再帰の深さや幅をスコアとする」ものでした。
- 私たちは「一般的な解法」として、以下を参照しています。
  - Sudoku Solver
  - http://www.sudokuwiki.org/sudoku.htm
しかしこの計画はいきなり苦戦します。なぜなら、番号の若い解法は私たちでも理解できるし難なく実装もできるのですが、番号が大きくなるにつれて、「なぜこの解法でいけるんだ？」「そもそもどういう解法なんだ？」「どう実装すればまともな速度で実行できるんだ？？」が多発し、どうにも進まなくなってしまったのです。

↑

(3) gsf's -q2 rating メインの時期へ

数独の世界では、gsf's -q2 ratingという難易度指標があります。これは結構定番っぽいので、「もう難しいことは考えないでこのスコアでの最高記録を目指そう」と考えました。・・・この方法なら、仮に弱い問題を見つけてしまったとしても、このレイティングのせいにするという言い訳も可能です（笑）。責任転嫁のように見えるかもしれませんが、分業の考え方です。

私たちはまず、ここにある難問集のgsf's -q2 ratingを計算して、上位を並べてみました。
- https://code.google.com/archive/p/skfr-sudoku-fast-rating/downloads
- ちなみに全部合わせて重複を取り除くと55万問くらいあります。

上位50位はこんな感じになりました（かっこ内のsc125は重要ではないのでとりあえず気にしないでください）。

#01: 000000001000002340003010250001005004060000700800900000002004003070080000900600000  q2=99743
#02: 000000001000002340003000250001005604060070000800600000002004005090800000700090000  q2=99587
#03: 280100700700020030005000200400060000010507000007008000300090400004000003000000069  q2=99578
#04: 980700600007090050000000907400300020006020500000001000100004000030800000002070005  q2=99516
#05: 980700000600090000005008900500004600004070030000200001050007800000300020000010007  q2=99508
#06: 000100020000030400005006007400000000086007000709000005000400300000020010060008009  q2=99480
#07: 000000120000003040004020003500006000070000008009010300600007000030500009001080030  q2=99421
#08: 000010200000300040005006007008000090060008000570000008000200030006003009300040100  q2=99420
#09: 000000100000020003004001056407000000006100800090005060700006040009010002040300008  q2=99417
#10: 000000000000010002003004056006000003030700200400003068004090000805400000060005084  q2=99415
#11: 000010020000300400050006007008000100079000000500008009000060000007005006600420030  q2=99407
#12: 000010200000300040005006007060000008850009000007080090040000030006007004000240100  q2=99405
#13: 000010020000300400050006007080000090005008000607000008000400300001020000070005006  q2=99404
#14: 000010020000300400005006007008000040096000800500008009000020030060005004700460100  q2=99403
#15: 000010200000300040005006007050000008870009000006080090010020000007001006000400310  q2=99402 (sc125=16554)
#16: 000001002000300400005060070058000000067000004900070080000006300006002001090080060  q2=99402 (sc125=10927)
#17: 000000001000020000003004056006000030030700100400003068004090000805400000060005084  q2=99399
#18: 000010002000300004005002060007000200250007000860000070000900300006005080090040001  q2=99397
#19: 000000001000020000003004056000700100006000030040003068034090000085400000600005084  q2=99396
#20: 000010002000300400005006070050000004600008020002030900006100000807000009020007050  q2=99394
#21: 000000010020000000003014005006000004700000036004063100000005001080900500005031060  q2=99393
#22: 000100002000030400050006070080000007609000080005008009000200001003040000070005090  q2=99392
#23: 000010000020300001004005060070000000005006080300200700009000004500080090000009605  q2=99390
#24: 000001020020300000004050006010000700300007000006080005000090850009800040080006009  q2=99386 (sc125=20138)
#25: 000100002000030400005006070008000900750000080960008007010200000000040003007009060  q2=99386 (sc125=18854)
#26: 000000100000020003004005060400000070007060008850007000000100009090030200005006080  q2=99386 (sc125=17336)
#27: 000000010000230000004005002600000100002050007080004090090000800003500001100007060  q2=99385 (sc125=20916)
#28: 000010002001003000000405100060000007800000090003040500004030000070004060900700008  q2=99385 (sc125=17588)

000010020000300040005006007500000300008020000070009008097000400800007006056100000 q2=99383 000000001020030400005600030000007000030020040008000209007008000010090004500006010 q2=99383 000001002000300400005060070086000000500090060079006004000002300000400001090070040 q2=99382 001000000000001230000450001060000000000070050005004003080000090904005002002903004 q2=99381 000010002000300400005006070068000000097000001500009060000020300050007080009400007 q2=99381 000000001000200300400005067005080000006000010040006095070000000090050100004009076 q2=99381 000100020000030004005006100007000000800009700096000018000200030500040001070008600 q2=99379 000000001000120003003004050005000300060000070700006504080090000007005040200800900 q2=99379 100000000020003004000520010004000006002006700060070030008000900070002003000890050 q2=99378 000001020000034000003500006070000800200000090001050003090000000800600700004005001 q2=99378 000100020000030400005006007008000070960000008050008600030200000000040010009007006 q2=99377 000100002000030400005006070600000050570008000008000907000400001030020000007009080 q2=99377 000010020000300400050006007060000000805000009709008060000020000090007005001400030 q2=99377 000010020000300400005006007007000000860000009950008700010020000000400030008005006 q2=99377 000010020000300400005006003003000040500700010080009005008000200300008006096070000 q2=99377 000001002000300004005060070080000200500080060076003000007000001050070090900004006 q2=99377 000000001000001230001300450600000070070080000005002004980000000003004005050090600 q2=99377 000000000000010000002003045004000020020600700300002084003090000805000007040005038 q2=99377 000010020000300004050006700500008600068000040079000008000200030700040001005009400 q2=99376 010002000000300001004050060000007800020000050009080006005090600090700005300005049 q2=99375 000100020000030400005006007008000700900008060650000008030400000000020010009007005 q2=99375 000010020000300400005006007068000000057000010900007005000020300009400000080009006 q2=99375 000010020000300004005006700500008900068000040097000008000000010050007400009240003 q2=99375 000010000000200030004005006057000000068000900400008005000900100006030020080004007 q2=99375 000000001000002300004050060000003700005000002060080090089100000500040080046008007 q2=99375 000001002000003004050060010007800000500010070019000400070000200600008003005090060 q2=99366

要するにこの記録を超える問題を見つければいいのです。こちらには渡辺さんのスパコンもあることですし、まあちょろいもんですよねきっと。
もっとも単純に考えた場合、数独の問題を片っ端からすべて作問し（総当たり）、それぞれにレイティング計算をして、最大のものを出せばよさそうです。それで数独の問題が全部でいくつくらいあるのかを簡単に見積もったところ、1.32e+34という数が出ました。・・・えっ？
仮に超絶に最適化して1コア当たり1ナノ秒で1つのスコア計算ができるとしても、1日で処理できる問題数はせいぜい9e+13で、そんなコアが100万個あるような架空のスパコンがあって、それを1年間占有できるとしても、3.3e+22個しか終わりません。これじゃあ11桁以上足りないわけで、この方法では到底だめだということがよくわかります。・・・私がいくら高速化バカだといってもさすがにこれは無謀です。
となれば、壮大な枝刈りをして、効率よく探す方法を考えるしかありません。