日経サイエンス  2006年9月号

数独の科学

J.-P. デラヘイ(仏リール科学技術大学) 【ダウンロードお試しキャンペーン開催中!】

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

 

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

 

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

 

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

 

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

 

 

【ダウンロードお試しキャンペーン開催中!】

この分野への理解が深まる記事とセットになったPDF「ゲームと遊びの数学」を
ダウンロードサイトで,特価200円でお求め頂けます。(期間限定)

著者

Jean-Paul Delahaye

仏リール科学技術大学で情報科学の教授を務める。同大学にある仏国立科学研究センター(CNRS)リール計算科学研究所(LIFL)の研究員を兼任。研究対象は計算ゲーム理論(繰り返し囚人ジレンマなど),複雑性理論(コルモゴロフ複雑性など),これら理論の遺伝子解析や経済学への応用。この記事はPour la Science誌(SCIENTIFIC AMERICANのフランス版)の2005年12月号に掲載されたものがもとになっている。

原題名

The Science behind Sudoku(SCIENTIFIC AMERICAN June 2006)

サイト内の関連記事を読む

キーワードをGoogleで検索する

バックトラッキングラテン方陣ナンバープレース