数独百科事典 · 数学とコンピューター

数独の数学

更新日：2026-10-05

ブロックのあるラテン方陣

ラテン方陣では、各行と各列にすべての記号が1回ずつ現れます。完成した数独は、9つの3×3ブロックのそれぞれにもすべての数字が1回ずつ入るという条件を加えた、9次のラテン方陣です。

盤面は何通りあるか

ベルトラム・フェルゲンハウアー（Bertram Felgenhauer）とフレイザー・ジャーヴィス（Frazer Jarvis）は、2005年に完成した9×9の盤面を数えました。その数は6,670,903,752,021,072,936,960通り、約6.67 × 10²¹通りです。その多くは、見た目を変えた同じ盤面です。数字の置き換え、回転や反転、または盤面がルールを満たす状態を保つ行や列の並べ替えによって、一方を他方に変えられる2つの盤面を同じものと数えると、本質的に異なる盤面は5,472,730,538通り残ります。この数は、エド・ラッセル（Ed Russell）とフレイザー・ジャーヴィスが計算しました。

出典: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

ヒントの最小数は17個

初期数字が16個以下の標準的な9×9の数独で、解がちょうど1つのものはありません。ゲイリー・マクガイア（Gary McGuire）、バスティアン・トゥーゲマン（Bastian Tugemann）、ジル・シヴァリオ（Gilles Civario）は、コンピューターによる網羅的な探索でこれを示し、2012年1月に結果を発表しました。17個は最小数ですが、解が1つであることを保証する数ではありません。初期数字が17個あっても、複数の解を持つ盤面は多くあります。

出典: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

グラフ彩色としての数独

81個のマスそれぞれに対応する頂点を描き、2つのマスが同じ行、列、またはブロックに属する場合に、その頂点を線で結びます。この数独グラフには810本の辺があり、各頂点はちょうど20個の隣接頂点を持ちます。パズルを解くことは、初期数字によって固定された色の指定を広げ、つながっている頂点が同じ色にならないようにすることです。各行、各列、各ブロックは、すべての頂点が互いにつながった9頂点の集まりなので、少なくとも9色が必要です。また、どの完成盤面も、9色で十分であることを示しています。

出典: Wikipedia: Sudoku graph

一般には難しく、9×9なら高速

大きさを際限なく拡張できる数独の盤面、つまりn×nのブロックを持つn²×n²の盤面については、一部が埋まった盤面を完成できるかどうかを判定する問題はNP完全です。この結果は、ヤトウ・タカユキ（Takayuki Yato）とセタ・タカヒロ（Takahiro Seta）が2003年に発表しました。効率的なコンピュータープログラムは、通常の9×9の問題を一般に1秒未満で解きますが、所要時間はプログラム、コンピューター、問題によって異なります。

出典: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

出典

すべての記事 →