2012年1月10日火曜日

数独の最小の鍵数

今朝は良い天気だ。 最後の蓬餅をチーズを乗せて焼いて、他に珈琲、ヨーグルトの朝食。 昼食は持参のお弁当。 塩鮭、蒲鉾、大根の漬物。 昼休憩に新刊書店で 「十蘭レトリカ」(久生十蘭著/河出文庫)、 古書店で 「猫はソファをかじる」(L.J.ブラウン著/羽田詩津子訳/ハヤカワ文庫) を買った。 カフェで珈琲豆を買うついでに、 一服しつつ「十蘭レトリカ」より僅か 5 ページの瞬編「胃下垂症と鯨」を読んで後、オフィスに戻る。 夕方退社して帰宅。 夕食は牛鍋。 実家からもらった牛肉を土鍋でさっと焼き、 塩少々を振って酒を加え、白菜、長葱と春菊(実家の庭産)を並べて、 醤油少々をかけて蒸し焼き風にする。 最後に適当にかき混ぜてから、並べ直して完成。溶いた生卵につけて食べる。 後は饂飩にした。大根と蕪の漬物。

数独の最小の鍵数(問題図で見えている数字の数)は、 答が一つだけあるという条件の下で 17 だと判明したらしい ("There is no 16-Clue Sudoku" arXiv:1201.0749)。 鍵数 17 の問題は知られていたが、 鍵数 16 で作れるのかどうかは今まで不明だった。そこに、 コンピュータを使った虱潰しで鍵数 16 の問題が存在しないことが分かった、というプレプリント (この内容を投稿できる査読付き論文誌があるのだろうか……)。 虱潰しとは言え、探索する空間があまりに膨大なため、 現実的な時間で計算可能な程度までいかに空間を削るかが肝で、 なかなか難しい問題だったようだ。 とは言え、 「だから何なんだ」と普段から言われがちの数学者ですら、 「だから何なんだ」と言いたくなるタイプの問題と成果ではある。