アイルランドの数学者が、複雑なアルゴリズムとスーパーコンピューターを用いて数百万時間に及ぶ演算を行い、数独に関する重要な問題を解決した。数独は日本から広まったパズルで、与えられている数字をヒントにして、9╳9のマスに1から9までの数字を入れて解盤面を完成させる。このとき、縦、横、および太い線で区切られた3╳3のブロック内のすべてで、1から9までの数字を1回ずつ使うようにしなければならない。新聞紙上の数独の大半は25個前後のヒントが与えられているが、ヒントの数が増えるほど、難度は低くなる。

2012年1月1日、ユニバーシティカレッジ・ダブリン（アイルランド）のGary McGuireは、数独の問題が成立するには最少で17個のヒントの数字が必要であるという論文をオンラインで発表した¹。16個以下のヒントでは解が1つに定まらず、有効な問題にならない。

この発表に対し、1月7日に米国マサチューセッツ州ボストンで開かれたある学会に参加していた数学者たちの間では、McGuireの証明はおおかた理にかなっているし、数独の数学という新興分野に重要な進展をもたらしたという意見が多数を占めた。

ジェームズ・マジソン大学（米国バージニア州ハリソンバーグ）の数学者Jason Rosenhouseは、「彼のアプローチは合理的で、信頼できそうです。慎重な楽観論として受け止められたと思います」と言う。Rosenhouseは、同じ大学の数学者Laura Taalmanとともに、『Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle（数独をまじめに考える：世界で最も人気のあるペンシルパズルの背後にある数学）』という本を昨年12月末に出版している。

数独愛好家たちは、以前から、ヒントが17個の数独はあるが、16個の有効な数独は見当たらないことに気付いており、16個のヒントで解が1つに決まるようなものは存在しないのではないかという推測が広がっていた。これを証明する方法の1つは、考えられるすべての解盤面につき、その盤面を解とするヒントが16個の有効な数独問題があるかどうかを検証することだが、演算に時間がかかりすぎる。

そこでMcGuireは、「ヒッティング・セット・アルゴリズム」を設計して、この問題を単純化した。ポイントは、ある解盤面に並んだ数字のうち、互いに入れ替えることで別の解盤面が得られるような部分（これを「不可避集合」と呼ぶ）を探すことにある。不可避集合を含む盤面が数独問題の唯一の解になるには、ヒントと不可避集合との間に重なり（これを「ヒット」と言う）がなければならない。だとすれば、すべての解盤面につき不可避集合を見つけて、それらとヒットするヒント数16の有効な数独問題がないことを示せばよいことになる。

McGuireらは、2年かけてこのアルゴリズムのテストを行い、その後、アイルランド・ハイエンド・コンピューティング・センター（ダブリン）のコンピューターにより、考えられるすべての解盤面につき、ヒッティング・セット・アルゴリズムを用いて検証した。この作業には700万CPU時間を要した。

ウェスタン・オーストラリア大学（パース）の数学者Gordon Royleは、McGuireらとは別のアルゴリズムを用いて、ヒントが17個の数独問題を数え尽くそうとしており、「コンピューティングと数学の技術を極限まで高めなければならない難問です。エベレストに登るようなものです」と語る。

McGuireは、今回の方法は、ほかの分野でも成果を挙げる可能性があると言う。ヒッティング・セットの概念は、遺伝子の塩基配列の決定や細胞ネットワークに関する論文でも用いられており、彼は、自分のアルゴリズムがほかの研究にも利用されればと期待している。「今回の成果で、もっとさまざまな人が興味を持ってくれることを願っています」。

皮肉なことに、McGuireは、この問題に取り組むようになってから、楽しく数独をすることが少なくなったと言う。「確かに数独は気分転換になりますが、正直なところ、最近はクロスワードのほうが好きなのです」。

翻訳：三枝小夜子、要約：編集部