
世界中で人気のこのパズルを解くには,数学どころか算数もまるで必要ない。にもかかわらず,パズルの裏には興味深い数学的問題が隠れている。
数独は平らな正方格子上のパズルだ。全体は9行9列・81個のマス目からなり,これが9つの小さな正方形(ブロックと呼ぶ)に分かれている。各ブロックは9個のマス目からなる。いくつかのマス目にはあらかじめ数字が印刷されている。ゲームでは空のマス目を1から9までの数字で埋めていくのだが,このときそれぞれの行と列,ブロックで,同じ数字が重複してはいけない。
数独は数のゲームなのに,数学的知識が一切なくても解ける。にもかかわらず,数独は数学者やコンピューター科学者に多くの未解決問題を提供している。「数独はいくつ存在するのか」「数独はNP完全問題という難問に属するのか」──といった問題だ。
数独の数について確定した答えはないが,同じ配置に変換できるものを1つと数えると54億7273万0538と推定される。地球上の人口よりもちょっと少ない。「初めに何個以上の数が入っていれば解が必ず1つに定まるか」という問題については,答えは「17」と予想される。しかし「開始時の数字が16個の問題はどれも解が1つに定まらない」ことを証明できるかというと,おそらく不可能だ。逆に「解が1つに定まらない問題は最多で何個の数字を含むか」については,答えは「77」とわかっている。
一方,パズルマニアは数独の攻略法を考案し,いろいろな変種も生み出した。これらについても紹介しよう。
著者
Jean-Paul Delahaye
仏リール科学技術大学で情報科学の教授を務める。同大学にある仏国立科学研究センター(CNRS)リール計算科学研究所(LIFL)の研究員を兼任。研究対象は計算ゲーム理論(繰り返し囚人ジレンマなど),複雑性理論(コルモゴロフ複雑性など),これら理論の遺伝子解析や経済学への応用。この記事はPour la Science誌(SCIENTIFIC AMERICANのフランス版)の2005年12月号に掲載されたものがもとになっている。
原題名
The Science behind Sudoku(SCIENTIFIC AMERICAN June 2006)