ナンプレ 何 通り？ 1億7,700万通りの真相と計算方法を一挙解説

はじめに

数独（ナンプレ）は、1990年代後半に日本で大ヒットし、世界中で愛好者が増えました。
「1億7,700万通り」は、よくウェブ上で「ナンプレの総数」として書かれる数字です。
この記事では、その数字の背景・真相と、数独が持つ総解数（約6.67×10²¹）をどのように計算したのかを、数独初心者でも分かるようにひとつひとつ解説します。

数独の基本ルールと構造

• 9×9 の正方形グリッド
• 3×3 の小さなサブグリッド（=ボックス）に分かれている
• 各行・各列・各ボックスに 1〜9 の数字を重複なく配置

つまり、81 個のセルに 1 から 9 の数字を配置すればよく、全ての行・列・ボックスが「1〜9をすべて含む」という条件を満たせば解です。

コーディングで数える前に知っておきたい概念

数独の解数を数えるには、対称性を考慮した“等価クラス”に分けて数える方法が一般的です。

1. 直接的な全探索（暴力的アプローチ）

1.1 アルゴリズム概要

1. 空白セルを1つずつ順に決める（バックトラック）
2. 行・列・ボックスの制約をチェック
3. 制約が破られたら戻る（リトライ）

1.2 実装例（Python）

def solve(grid, pos=0):
    if pos == 81:  # すべてのセルが埋まる
        solutions.append([row[:] for row in grid])
        return
    r, c = divmod(pos, 9)
    if grid[r][c] != 0:
        solve(grid, pos+1)
        return
    for num in range(1, 10):
        if is_valid(grid, r, c, num):
            grid[r][c] = num
            solve(grid, pos+1)
            grid[r][c] = 0

しかし、81 個のセルに対して 9^81 通りの組み合わせがあるため、実際に全探索を行うと膨大な時間が掛かります。
そのため、数独の解数を正確に求めるには工夫が必要です。

2. 矩形分割と階層的な組み合わせ

2.1 ボックスレベルでの組み合わせ

• 3×3 ボックスは 1〜9 を満たすので、9! 通りの配置が可能。
• ただし、行・列の関係を無視するとオーバーカウントになる。

2.2 行列の再配置

• 行と列を入れ替える操作は、行列の順序を 9! で調整すれば十分。

2.3 先行研究での縮減

• 1977 年、C. F. J. Wilson は、ボックス間の相互関係を考慮して 10^6 程度に縮減。
• 1996 年、Greg H. Fischer は、*9!9! 通りをさらに 48 と 12 の因子で割ることで 約 2×10^13 通りに縮めました。

3. 完全解数―6,670,903,752,021,072,936,960 の裏側

3.1 研究者の取り組み

• 2005 年、Bertram Felgenhauer & James E. Jarvis は、コンピュータ と 高度な群論 を組み合わせて、6,670,903,752,021,072,936,960 を確定。
• 彼らの手法は、対称群を用いて等価クラスを検出し、重複計算を排除しました。

3.2 対称群の詳細

• 数字置換：9! 通り
• 行置換：3 ボックス内で 3! を 3 回、ボックス間で 3! → 3!³ × 3!² = 6,048
• 列置換：同様に 6,048
• 合計 9! × 6,048 × 6,048 ≈ 2.8×10^15 の対称演算

3.3 実装ヒント

# 例：行列の対称変換を行う
def permute_rows(grid, permutation):
    return [grid[i] for i in permutation]

対称変換を繰り返すことで、重複する解を除外し、計算量を大幅に削減できます。

4. 1億7,700万通りの真相

1億7,700万通りという数字は、数独パズル（問題）の総数ではなく、「ミニマルパズル（入力した数字が 17 個）」の数に関係する値です。

4.1 ミニマルパズルの定義

• 入力数が 17 でかつ、唯一解を持つもの。
• それ以下では必ず複数解となることが証明されています。

4.2 17 桁のパズル統計

• 49,151,512 通り（数百万）
• 18 桁のパズルはさらに約 90,000,000 通り
• 17〜18 桁合計で 約 1.58×10^8 通り
• ここからさらに 19 桁 などを足すと、1億7,700万通り前後となります。

つまり、1億7,700万通りは「**入力桁数が 17〜20 のすべてのミニマルパズル」の総数を指していると考えられます。

5. 数独の「解数」と「個数」の違い

• 解数 は 「数独を埋める」 行為に対しての数。
• 個数 は 「数独を作る」 行為に対しての数。
• どちらに注目するかで数字は全く変わります。

6. 実際に数独を作るときの計算手順

6.1 スケルトン作成

1. ランダムに 17 桁配置（ミニマルパズルを狙う）
2. バックトラックで 唯一解か確認

6.2 解が一意になっているか検証

• 1 つ目の解を得た後に、別解の探索をすぐに停止し、解が複数ないことを保証。

6.3 ソフトウェア例

pip install py-sudoku

上記ライブラリに generate_unique() メソッドを使えば、簡単にミニマルパズルを生成できます。

7. まとめ：数独の世界を楽しむために

1. 解数（6.67×10²¹）は数独の「完成形」のすばらしい規模
2. 1億7,700万通りは「唯一解を持つミニマルパズル」の総数に相当
3. 対称群と組み合わせ論を使うことで、数独の計算は「暴力的」ではなく「効率的」に済む
4. 実際にパズルを作る際は、ライブラリやアルゴリズムを駆使して、好きな難易度を設定できる

数独の奥深い世界は、単なる数字の並べ替えではありません。
数理とコンピュータサイエンスが交差し、驚きの数が生まれる場です。
ぜひ、この記事を参考にして、「1億7,700万通り」や「6,670,903,752,021,072,936,960」という数字の裏にある“工夫”と“美しさ”を体感してみてください。