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

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
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という難易度指標があります。これは結構定番っぽいので、「もう難しいことは考えないでこのスコアでの最高記録を目指そう」と考えました。・・・この方法なら、仮に弱い問題を見つけてしまったとしても、このレイティングのせいにするという言い訳も可能です（笑）。責任転嫁のように見えるかもしれませんが、分業の考え方です。

先人たちの研究により、上位5位はこんな感じになっていました。

#1: 000000001000002340003010250001005004060000700800900000002004003070080000900600000  q2=99743
#2: 000000001000002340003000250001005604060070000800600000002004005090800000700090000  q2=99587
#3: 280100700700020030005000200400060000010507000007008000300090400004000003000000069  q2=99578
#4: 980700600007090050000000907400300020006020500000001000100004000030800000002070005  q2=99516
#5: 980700000600090000005008900500004600004070030000200001050007800000300020000010007  q2=99508

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