川合秀実の数独研究に関するドキュメント#1
(1) はじまり (2013年の7月ごろ)
- 川合は、2013年の7月くらいから、東京大学の渡辺宙志さんの数独の難しい問題を作る研究にjoinしています。
- この研究に誘ってもらえたきっかけは、
- (1)私と渡辺さんは、2002年度未踏ユースの同期生だったこと、
- (2)数独の高速化」という記事を2012年の12月に書いていたこと、
- の二つです。
- この後とても楽しい経験ができたので、本当にいいきっかけがもらえたと思っています。
(2) gsf's rating 利用以前
- 初期の方針は、渡辺さんが最初に発表した難問が「コンピュータで解くにはたくさんの再帰呼び出しを要するのにもかかわらず、人間が一般的な数独解法を使うだけでスイスイと解けてしまった」ことに着目して、「一般的な解法が適用できるときはそれをどんどん使って、行き詰まったら再帰させることにして、その再帰の深さや幅をスコアとする」ものでした。
- 私たちは「一般的な解法」として、以下を参照しています。
- しかしこの計画はいきなり苦戦します。なぜなら、番号の若い解法は私たちでも理解できるし難なく実装もできるのですが、番号が大きくなるにつれて、「なぜこの解法でいけるんだ?」「そもそもどういう解法なんだ?」「どう実装すればまともな速度で実行できるんだ??」が多発し、どうにも進まなくなってしまったのです。
(3) gsf's -q2 rating メインの時期へ
- 数独の世界では、gsf's -q2 ratingという難易度指標があります。これは結構定番っぽいので、「もう難しいことは考えないでこのスコアでの最高記録を目指そう」と考えました。・・・この方法なら、仮に弱い問題を見つけてしまったとしても、このレイティングのせいにするという言い訳が可能です(笑)。責任転嫁のように見えるかもしれませんが、難易度指標を作るのがうまい人がすでにいるのならその人に任せてしまおうという、分業の考え方です。
つづく
こめんと欄
|