sdk0001

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

• (by K, 2019.04.01)

(1) はじまり （2013年の7月ごろ）

• 川合は、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: 000000012000000003002300400001800005060070800000009000008500000900040500470006000  q2=99551
  #05: 980700600007090050000000907400300020006020500000001000100004000030800000002070005  q2=99516
  #06: 980700000600090000005008900500004600004070030000200001050007800000300020000010007  q2=99508
  #07: 000100020000030400005006007400000000086007000709000005000400300000020010060008009  q2=99480
  #08: 000000120000003040004020003500006000070000008009010300600007000030500009001080030  q2=99421
  #09: 000010200000300040005006007008000090060008000570000008000200030006003009300040100  q2=99420
  #10: 000000100000020003004001056407000000006100800090005060700006040009010002040300008  q2=99417
  #11: 000000000000010002003004056006000003030700200400003068004090000805400000060005084  q2=99415
  #12: 000010020000300400050006007008000100079000000500008009000060000007005006600420030  q2=99407
  #13: 000010200000300040005006007060000008850009000007080090040000030006007004000240100  q2=99405
  #14: 000010020000300400050006007080000090005008000607000008000400300001020000070005006  q2=99404
  #15: 000010020000300400005006007008000040096000800500008009000020030060005004700460100  q2=99403
  #16: 000010200000300040005006007050000008870009000006080090010020000007001006000400310  q2=99402 (sc125=16554)
  #17: 000001002000300400005060070058000000067000004900070080000006300006002001090080060  q2=99402 (sc125=10927)
  #18: 000000001000020000003004056006000030030700100400003068004090000805400000060005084  q2=99399
  #19: 000010002000300004005002060007000200250007000860000070000900300006005080090040001  q2=99397
  #20: 000000001000020000003004056000700100006000030040003068034090000085400000600005084  q2=99396
  #21: 000010002000300400005006070050000004600008020002030900006100000807000009020007050  q2=99394
  #22: 000000010020000000003014005006000004700000036004063100000005001080900500005031060  q2=99393
  #23: 000100002000030400050006070080000007609000080005008009000200001003040000070005090  q2=99392
  #24: 000010000020300001004005060070000000005006080300200700009000004500080090000009605  q2=99390
  #25: 000001020020300000004050006010000700300007000006080005000090850009800040080006009  q2=99386 (sc125=20138)
  #26: 000100002000030400005006070008000900750000080960008007010200000000040003007009060  q2=99386 (sc125=18854)
  #27: 000000100000020003004005060400000070007060008850007000000100009090030200005006080  q2=99386 (sc125=17336)
  #28: 000000010000230000004005002600000100002050007080004090090000800003500001100007060  q2=99385 (sc125=20916)
  #29: 000010002001003000000405100060000007800000090003040500004030000070004060900700008  q2=99385 (sc125=17588)
  #30: 000000001020030400005600030000007000030020040008000209007008000010090004500006010  q2=99383 (sc125=17336)
  #31: 000010020000300040005006007500000300008020000070009008097000400800007006056100000  q2=99383 (sc125=15784)
  #32: 000001002000300400005060070086000000500090060079006004000002300000400001090070040  q2=99382
  #33: 001000000000001230000450001060000000000070050005004003080000090904005002002903004  q2=99381 (sc125=19382) ← 後に注目される問題（後述）
  #34: 000010002000300400005006070068000000097000001500009060000020300050007080009400007  q2=99381 (sc125=16806)
  #35: 000100020000030004005006100007000000800009700096000018000200030500040001070008600  q2=99379 (sc125=17065)
  #36: 000000001000120003003004050005000300060000070700006504080090000007005040200800900  q2=99379 (sc125=16045)
  #37: 100000000020003004000520010004000006002006700060070030008000900070002003000890050  q2=99378 (sc125=17832)
  #38: 000001020000034000003500006070000800200000090001050003090000000800600700004005001  q2=99378 (sc125=20139)
  #39: 000000000000010000002003045004000020020600700300002084003090000805000007040005038  q2=99377 (sc125=20920)
  #40: 000001002000300004005060070080000200500080060076003000007000001050070090900004006  q2=99377 (sc125=19887)
  #41: 000000001000001230001300450600000070070080000005002004980000000003004005050090600  q2=99377 (sc125=18865)
  #42: 000100002000030400005006070600000050570008000008000907000400001030020000007009080  q2=99377 (sc125=18857)
  #43: 000100020000030400005006007008000070960000008050008600030200000000040010009007006  q2=99377 (sc125=18612)
  #44: 000010020000300400005006007007000000860000009950008700010020000000400030008005006  q2=99377 (sc125=16297)
  #45: 000010020000300400005006003003000040500700010080009005008000200300008006096070000  q2=99377 (sc125=16291)
  #46: 000010020000300400050006007060000000805000009709008060000020000090007005001400030  q2=99377 (sc125=16047)
  #47: 000010020000300004050006700500008600068000040079000008000200030700040001005009400  q2=99376
  #48: 000010020000300004005006700500008900068000040097000008000000010050007400009240003  q2=99375 (sc125=19882)
  #49: 010002000000300001004050060000007800020000050009080006005090600090700005300005049  q2=99375 (sc125=19631)
  #50: 000010000000200030004005006057000000068000900400008005000900100006030020080004007  q2=99375 (sc125=19120)
  #51: 000100020000030400005006007008000700900008060650000008030400000000020010009007005  q2=99375 (sc125=19117)
  #52: 000000001000002300004050060000003700005000002060080090089100000500040080046008007  q2=99375 (sc125=16804)
  #53: 000010020000300400005006007068000000057000010900007005000020300009400000080009006  q2=99375 (sc125=15784)
  #54: 000001002000003004050060010007800000500010070019000400070000200600008003005090060  q2=99366

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

つづく

• 続きはこちら: sdk0002

こめんと欄