数独の科学

世界中で人気のこのパズルを解くには，数学どころか算数もまるで必要ない。にもかかわらず，パズルの裏には興味深い数学的問題が隠れている。

数独は平らな正方格子上のパズルだ。全体は９行９列・81個のマス目からなり，これが９つの小さな正方形（ブロックと呼ぶ）に分かれている。各ブロックは９個のマス目からなる。いくつかのマス目にはあらかじめ数字が印刷されている。ゲームでは空のマス目を１から９までの数字で埋めていくのだが，このときそれぞれの行と列，ブロックで，同じ数字が重複してはいけない。

数独は数のゲームなのに，数学的知識が一切なくても解ける。にもかかわらず，数独は数学者やコンピューター科学者に多くの未解決問題を提供している。「数独はいくつ存在するのか」「数独はNP完全問題という難問に属するのか」──といった問題だ。

数独の数について確定した答えはないが，同じ配置に変換できるものを１つと数えると54億7273万0538と推定される。地球上の人口よりもちょっと少ない。「初めに何個以上の数が入っていれば解が必ず１つに定まるか」という問題については，答えは「17」と予想される。しかし「開始時の数字が16個の問題はどれも解が１つに定まらない」ことを証明できるかというと，おそらく不可能だ。逆に「解が１つに定まらない問題は最多で何個の数字を含むか」については，答えは「77」とわかっている。

一方，パズルマニアは数独の攻略法を考案し，いろいろな変種も生み出した。これらについても紹介しよう。