科学・技術

4x4 スドクは12種類しかない（そして最小部分集合を見つけるクールなトリック）

There are only twelve 4x4 sudokus (and a cool trick for finding minimal subsets) (baldino.dev)

29 pointsby Fran3142026年9月14日10 コメント

要約

この記事では、4x4のスドク（数独）のユニークな解の構造が12種類しかないことを解説しています。数字の置換を同一視した場合、総解数288通りから12通りの構造的な違いに絞り込めることを、具体的な例と計算方法を用いて説明しています。さらに、最小部分集合を見つけるための興味深いトリックも紹介しています。

全文翻訳

4x4 スドクは12種類しかない（そして最小部分集合を見つけるためのクールなトリック）

2026年9月14日
sudoku
recreational-math

14 分で読めます

4x4 スドクは12種類しかないのです！…あるいは、何をもって異なる解とみなすかによりますが、288種類です。

何が、なぜ、そして正確には何

今日の探求は、ユニークな4x4 スドクの解（および可能なパズル）がいくつあるかということです。なぜかって？私にも分かりませんが、その疑問がふと頭に浮かび、その答えはわずかに興味深いと思ったからです。

もし馴染みがない方のために説明すると、4x4 スドクとは、行、列、および2x2のボックスに分割された4x4のグリッドで、各セルを1から4までの数字で埋め、各行、各列、各ボックスで各数字がちょうど1回だけ現れるようにすることを目指すものです。

╔═══╤═══╦═══╤═══╗
║   │   ║   │   ║
╟───┼───╫───┼───╢
║   │   ║   │   ║
╠═══╪═══╬═══╪═══╣
║   │   ║   │   ║
╟───┼───╫───┼───╢
║   │   ║   │   ║
╚═══╧═══╩═══╧═══╝

これは、より一般的な9x9 スドク（同様に3x3のボックスに分割されている）の小さいケースです。これはN×NN \times N スドクに一般化され、N=n2N = n^2 となるような整数nnが存在します。n=2n=2 の場合、4x4 スドクが得られ、次のステップはn=3n=3 の9x9 スドクです。

通常、これらのパズルは部分的に埋められたグリッドから始まります（空のグリッドの解を見つけるのは簡単だからです）。しかし、ここでは一時的に、空の開始位置からでも、解とは有効なすべての埋め込みを指すものとします。

例えば、ここに4x4 スドクの3つの異なる有効な解を示します。

       (A)
╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 2 │ 1 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

       (B)
╔═══╤═══╦═══╤═══╗
║ 2 │ 1 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 1 │ 2 ║
╟───┼───╫───┼───╢
║ 1 │ 2 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

       (C)
╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╚═══╧═══╩═══╧═══╝

与えられた解を詳しく見ると、それらがすべて同じように「区別」されているわけではないことに気づきます。解 (B) は、実際には解 (A) で1をすべて2に、2をすべて1に置き換えただけです。

通常のスドク（つまり、バリアントスドクではない）の文脈では、グリッドを埋めるために使用する数字は単なる意味のない記号です。もし望むなら、「1, 2, 3, 4」の代わりに「🔴, 🟣, 🔵, 🟢」を使って同じパズルを解くことができ、パズルはまったく同じままです。同様に、数字を色の付いた形に置き換える代わりに、数字を数字に置き換えても、パズルは同じままです。

この観点から、解 (A) と (B) は同じパズルの異なる記号を使用していると理解できます。それらは同じ根本的な構造を持っています。逆に、(A) と (C) は構造的に異なります。数字をどれだけ入れ替えても、解 (A) では行2列1と行1列4のセルは同じ記号を含みますが、解 (C) では同じセルは異なる記号を含みます。

したがって、私たちが問うている質問は次のとおりです。

4x4 スドクの解はいくつ存在しますか？そして、これらの解のうち、いくつが実際に区別されますか（構造的に）？

最初の答えと、いくつかのひどいPythonコード

簡単な質問から始めましょう。同じ構造を持つ可能性のある4x4 スドクの解はいくつ存在しますか？幸いなことに、扱っている数字は非常に小さいため、ブルートフォースで一瞬でこの質問に答えることができます。

（単純な）方法は、空のグリッドから始め、各セルについて残りの可能な値を特定し、深さ優先方式で各可能な値を再帰的に探索することです。

N = 4

def findSolutions(sudoku: list[int], curr: int) -> list[list[int]]:
    if curr == N**2: # 残りのセルを埋める必要がない、解が見つかった
        return [sudoku]

    # チェックするすべてのセル：同じ行のセル、同じ列のセル、同じ正方形のセル。
    _cells2Check = sameRowCells[curr] + sameColCells[curr] + sameBoxCells[curr]
    # インデックスがiより小さいセルのみをチェックします。他のセルはまだ設定されていません。
    cells2Check = {other for other in _cells2Check if other < curr}
    othersValues = {sudoku[other] for other in cells2Check}
    allowedValues = {value for value in range(1, N + 1) if not value in othersValues}

    if len(allowedValues) == 0: # 有効な数字がないため、有効な解はありません。空を返します
        return []

    solutions = []
    for value in allowedValues:
        newSudoku = sudoku.copy()
        newSudoku[curr] = value
        solutions += findSolutions(newSudoku, curr + 1)
    return solutions


emptySudoku = [0] * (N**2)
allSolutions = findSolutions(emptySudoku, 0)
print("Number of total solutions:", len(allSolutions))

SQRT_N = int(math.sqrt(N))

def _index2pos(i: int) -> tuple[int, int]:
    return (i % N, i // N)

def _pos2index(x: int, y: int) -> int:
    return x + y * N

def _sameRowCells(i: int) -> list[int]:
    (_, y) = _index2pos(i)
    return [_pos2index(cx, y) for cx in range(N)]

def _sameColCells(i: int) -> list[int]:
    (x, _) = _index2pos(i)
    return [_pos2index(x, cy) for cy in range(N)]

def _sameBoxCells(i: int) -> list[int]:
    (x, y) = _index2pos(i)

    # セルiが含まれるBOXのxとy座標
    bx = x // SQRT_N
    by = y // SQRT_N
    return [
        _pos2index(bx * SQRT_N + cx, by * SQRT_N + cy)
        for cx in range(SQRT_N)
        for cy in range(SQRT_N)
    ]

# 効率化のため、すべての可能な値を事前に計算します
sameRowCells = {i: _sameRowCells(i) for i in range(N**2)}
sameColCells = {i: _sameColCells(i) for i in range(N**2)}
sameBoxCells = {i: _sameBoxCells(i) for i in range(N**2)}

約0.5秒で、このコードは以下を出力するはずです。

Number of total solutions: 288

わずか288の可能な解です！これは、n=3n=3 の9x9 標準スドクの 6,670,903,752,021,072,936,960 の可能な解と比較すると、ごくわずかな数です[1]。これはn=3n=3 の次のステップです！[2]

同時に、非常に不正確な計算で、NNの関数としての可能な解の数の非常に大まかな近似を与えることができます。行の制約のみを考慮し、列とボックスの制約を無視すると、各行にはN!N!の可能な組み合わせがあり、NN行があるため、可能な組み合わせの総数は N!N
=(n2!)n2N!^N = (n^2!)^{n^2} となります。

これはひどい上限値であることに注意してください。この公式をn=3n=3 に使用すると、約1050\approx 10^{50} となり、正しい答えである約6.6×1021\approx 6.6 \times 10^{21} をはるかに超えます。

それでも、n=2n=2 は小さく、n=3n=3 は大きいです！

実際に区別される解のカウント

次に、実際に区別される解、つまり区別される構造をカウントします。

任意の解に対して、数字1、2、3、4の任意の置換を適用して新しい解を得ることができることをすでに確認しました。4! = 24 の置換があるため、すべての構造は24倍で過剰にカウントされていることになります。したがって、理論上、実際に区別される解の数は次のようになります。

288 / 24 = 12 の区別される解

この質問にアプローチする別の方法があり、以前のひどいPythonコードを再利用できます。重要な事実は次のとおりです。

数字を単なる記号として扱います。それが実際に何であるかは気にしません。何であってもよく、それらの任意の置換は有効です。
任意の解において、最初の行（他の行と同様）は4つの異なる記号を含むことが保証されています。

次に、考え方は次のとおりです。任意の解構造を与え、最初の行の最初の記号を1、最初の行の2番目の記号を2、そして3と4についても同様に呼び出します。このようにして、最初の行に1 2 3 4で始まる対応する解で、すべての構造を表すことができます。

2つの異なる解 S1,S2S_1, S_2 が両方とも1 2 3 4で始まる場合、それらは構造的にも異なるはずです。

もしそれらが同じ構造を持っていたなら、数字の置換σ\sigma が存在し、σ\sigma を S1S_1 に適用すると S2S_2 が得られるはずです。
しかし、もしσ\sigma が任意の数字を入れ替えるなら、S1S_1 にそれを適用すると 1 2 3 4 で始まらない解が得られるため、S2S_2 と等しくなることはありません。
同様に、もしσ\sigma がすべての数字をそのままにするなら、S1S_1 にそれを適用した結果は正確に S1S_1 であり、仮定により S2S_2 とは等しくありません。
したがって、そのようなσ\sigma は存在できず、2つの解は構造的に異なる必要があります。

これにより、可能な構造の数と 1 2 3 4 で始まる可能な解の数との間に1対1の対応が得られます。したがって、すべての可能な構造の数を取得するには、1 2 3 4 で始まるすべての可能な解の数を数えるだけで済みます。これらの数を数えるには、コードの emptySudoku を 1 2 3 4 で始まるように初期化するだけです。

emptySudoku = [0] * (N**2)
emptySudoku[0:N] = [value for value in range(1, N + 1)]

distinctSolutions = findSolutions(emptySudoku, N)
print("Number of distinct solutions:", len(distinctSolutions))

# 注意：もし事前に allSolutions を計算していたなら、
# distinctSolutions を最初から計算する代わりに、
# allSolutions から `1 2 ... N` で始まるすべての解を取得するだけで済みます。
# ```python
# distinctSolutions = [sol for sol in allSolutions if sol[0:N] == list(range(1, N + 1))]
# ```

これを実行すると…

Number of distinct solutions: 12

やった！私たちのひどいPythonコードは、理論から期待されるのと同じ結果をもたらしました。数字の置換によるすべての可能な区別される解を以下に示します。

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 3 ║ 4 │ 1 ║
╟───┼───╫───┼───╢
║ 4 │ 1 ║ 2 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 4 │ 1 ║ 2 │ 3 ║
╟───┼───╫───┼───╢
║ 2 │ 3 ║ 4 │ 1 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 4 │ 3 ║ 2 │ 1 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 4 │ 3 ║ 1 │ 2 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 2 │ 1 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 4 ║ 1 │ 3 ║
╟───┼───╫───┼───╢
║ 3 │ 1 ║ 4 │ 2 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 1 ║ 4 │ 2 ║
╟───┼───╫───┼───╢
║ 2 │ 4 ║ 1 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 1 │ 2 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

パズルのカウント

これまでは、スドクパズルの重要な部分である初期設定を無視してきました。スドクパズルは、以下のようなグリッドのように、いくつかの数字がすでに埋められた状態で始まります。

╔═══╤═══╦═══╤═══╗
║ 1 │   ║   │   ║
╟───┼───╫───┼───╢
║   │ 4 ║   │   ║
╠═══╪═══╬═══╪═══╣
║   │   ║   │ 3 ║
╟───┼───╫───┼───╢
║   │   ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

そして、パズルとは残りのグリッドを埋めることです。一般的に、部分的な埋め込みが正確に1つの解を持つことが要求されます。例えば、数字が1つだけ配置されたグリッドは有効なパズルではありません。なぜなら、1つの数字だけが配置された状態から残りを埋める方法は多数存在するからです。

ここで、そのようなパズル（部分的に埋められたグリッド）がいくつ存在するのかをカウントしたいのです。始める前に、明確化が必要です。興味のないパズルは除外したいのです。例えば、以下のパズルは興味がありません。

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │   ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

これは部分的に埋められており、一意の解を持つことは事実ですが、最小ではありません。与えられた数字のいずれかを取り除いても、解が一意でなくなる可能性があります。

したがって、私たちは最小パズルにのみ関心があります。パズルは、与えられた数字を削除しても解が一意でなくなる場合、最小であると言えます。

4x4 最小スドクパズルはいくつ存在しますか？

さらにひどいブルートフォースPythonコードで答えを見つけることができます。アイデアは次のとおりです。

すべての可能な解をループし、各解についてすべての可能な部分集合をループします（これがパズルに含まれる数字になります）。
各部分集合について、その部分集合に同意する他の解がどれだけあるかを確認します。つまり、その部分集合の数字が与えられた場合に可能なすべての解を見つけます。
現在の解が唯一の可能な解ではない場合、部分集合を破棄します（一意の解につながるわけではないため、有効なパズルではありません）。
そうでない場合、最小かどうかを確認します（この部分集合のセル部分集合である他のパズルが存在するかどうかを確認します）。最小であれば、リストに追加します。

allPuzzles = 0
for k, solution in enumerate(allSolutions):
    cellToPosibleSolutions = [
        # 各セルcについて、セルcに値solution[c]を持つすべての解を事前に計算します
        {j for (j, other) in enumerate(allSolutions) if (other[c] == solution[c])}
        for c in range(N**2)
    ]

    puzzles: list[int] = []

    # すべての可能な部分集合を反復処理します
    for subsetMask in range(1, 2 ** (N**2)):
        subset = {i for i in range(N**2) if (subsetMask & (1 << i))}
        possibleSolutions = set.intersection(
            *[cellToPosibleSolutions[i] for i in subset]
        )

        if possibleSolutions != {k}: # 現在の解（k）は唯一の可能な解ではありません。スキップします
            continue

        isMinimal = True
        for other in puzzles:
            if subsetMask & other == other: # otherがsubsetのサブセットである場合
                isMinimal = False
                break

        if isMinimal:
            puzzles.append(subsetMask)

    allPuzzles += len(puzzles)

print("Number of possible puzzles:", allPuzzles)

最小部分集合を見つけるためのクールなトリック

上記のコードを実行すると（2〜3分かかる苦痛の後…）、可能なパズルの数は85632であることがわかりますが、興味深いのはそれを見つけた方法だと思います。

まず、解のすべての部分集合を反復処理する必要があります。Pythonにはネイティブでリストの部分集合のイテレータを作成する関数はありませんが、部分集合をビットマスクとして表現することで自分で作成できます。要素のリストと部分集合が与えられた場合、各要素について、要素が部分集合に存在しない場合は0、存在する場合は1を割り当てます。これにより、部分集合のバイナリ表現が得られます。特に、元のリストのサイズがSSの場合、SSビットを割り当てるため、部分集合に対応するバイナリ数は00から2S−12^S-1 の間になります（この場合、S=N2S = N^2）。したがって、00から2S−12^S - 1 までのすべての数値を反復処理し、各数値をバイナリマスクとして扱うと、すべての部分集合を反復処理できます。

実際のクールなトリックは次のとおりです。受け入れられたパズルが最小であることを確認する必要があったことを思い出してください。つまり、他のパズルが存在しないことを意味します。これはコードで行っていることと似ていますが、微妙な違いがあります。コードでは、パズルを受け入れるために、以前に見られたパズルだけが現在のパズルの部分集合ではないことを確認しています。すべての可能なパズルではなく、知っているパズルのみを確認しています。

しかし、これは同等です！例えば、パズルPPが見つかったが、有効なパズルではないが、最小ではないとします。これは、PPの部分集合である別のパズルQQが存在することを意味します。その場合、QQのビットマスクが1であった場所では、PPのビットマスクも1である必要があります。これにより、ビットマスク演算を使用して「部分集合性」を効率的に確認できます：bitmask(P) & bitmask(Q) == bitmask(Q)。しかし、これも重要ですが、これはbitmask(Q)がbitmask(P)よりも小さい数値であることを意味します。反復処理の順序を考慮すると、PPに到達した時点で、PPのすべての可能なサブサブセットも反復処理されているため、既に見られたものとの確認は、すべての可能なサブサブセットとの確認と同等です！

同様に、最小部分集合ではなく最大部分集合を探している場合にも同じトリックを適用できます。部分集合QQがPPのスーパーセットであるかを確認するには、チェックはbitmask(P) & bitmask(Q) == bitmask(P)となり、反復処理の順序を逆にしなければなりません。

クール！ではn=3でやってみましょう！

いいえ。

n=3n=3 でコードを実行することもできますが、書かれたコードの複雑さは（少なくとも？約？[3]）です。

O(2N2⋅N!) O(2^{N^2 \cdot N!})

n=2n=2 の場合、合理的な時間で実行されたため、幸運でした。上記の近似を使用し、n=2n=2 の場合が約200秒で実行されたことを知ると、n=3n=3 は宇宙の年齢の少なくとも 10884812810^{8848128} 倍かかるはずです。

オンラインで検索すると、9x9 の場合の可能なパズルの数は不明であることがわかります（いくつかの上限と下限が与えられています[4]）。

結論

区別される4x4 解はわずか12種類です！置換を気にしなければ288種類です！そして、可能な開始位置はわずか85632種類で、置換で数えるとわずか3568種類になります。

A4用紙に4cmサイズ（私は快適だと思いますが、もっと小さくすることもできます）で印刷すると、置換を考慮しない場合はわずか102ページ、すべての可能な4x4 パズルを印刷すると2247ページになります！

1日1ページ解いたとすると（そして、慣れれば約30秒で1ページ解けるはずなので、1ページあたり20分未満）、7年未満で（または置換を考慮しない場合は102日で）すべての可能な4x4 を解くことができます。

そして、あなたは「私は4x4 スドクをすべてやった」と言って周りを歩くことができます。文字通り、すべてです。

そうすべきでしょうか？分かりません。多分？1日20分を過ごすより悪い方法がたくさんあります。軽い精神的なエクササイズになり、流れに乗ればリラックスでき、瞑想的になることもあります。そして、「私は4x4 スドクをすべてやった」と言って周りを歩くことができます。

また、これらの数字はわずかに興味深いと思いますが、おそらく同様の数字を期待すべきでした。結局のところ、4x4 スドクはそれほど複雑ではなく、その下の唯一のステップ（2x2 スドク）は些細なものなので、この結果は驚くべきことではないかもしれません。同時に、4x4 スドクをプレイするための書籍やアプリがたくさん販売されていますが、可能な解がわずか288種類しかないというのは少し奇妙です。

未解決の質問

解ごとの可能なパズルの数

すべての解が平等に作られているわけではありません。それらのほとんど（288個中192個）は304個の最小パズルを持っており、それらを解くとそれらに到達しますが、かなりの部分（288個中96個）は284個の最小パズルしか持っていません。なぜでしょうか？一部の解がより多くのパズルを持ち、一部がより少ないパズルを持つ構造の何が原因なのでしょうか？

12個の解を見つけるためのエレガントな方法

述べたように、区別される解は12個あります。つまり、12 = 3x2x2 です。最初の行を固定したまま（これにより区別される構造をカウントできます）、1 2 3 4 とすると、この3x2x2は、グリッド内に3つの可能な数字を持つ1つのセルと、2つの可能な数字を持つ2つのセル（すべて互いに独立している）があり、それらが一意に解を特定できるという事実を示唆している可能性があります。

これは…ほぼその通りですが、完全にはそうではなく、エレガントな議論にする方法が見つかりません。

例えば、ある程度独立しているように見える3つのセルを見てみましょう。r2c1、r3c3、r4c2。

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ ▒ │   ║   ║   ║
╠═══╪═══╬═══╪═══╣
║   ║   ║ ▒ ║   ║
╟───┼───╫───┼───╢
║   ║ ▒ ║   ║   ║
╚═══╧═══╩═══╧═══╝

確かに、r2c1には2つの可能な値（3、4）があり、これは合計12の要因として2を占めます。r3c3には3つの可能な値（1、2、4）があり、これらはすべてr2c1に選択された値とは独立して可能です。これは合計12の要因として3を占めます。しかし、r4c2の場合はもう少し複雑です。

例えば、r3c3 = 2 を選択した場合、r4c2 は 1 または 3 のいずれかになります（どちらも一意の解につながります）。しかし、r3c3 = 1 を選択した場合、r4c2 も 1 に強制されます。r3c3 = 4 の場合さらに悪いです！r3c3 = 4 と r2c1 = 3 を選択した場合、r4c2 は 1 と 3 の2つの可能な値を持つことができますが、3 を選択しても一意の解にはなりません！

私たちは確かに、ツリーのような方法で進み、1つのセルの値を決定し、次に別のセル、次に別のセルを決定し、合計12の葉があることを示すことができます。しかし、次にどのセルを選択するかは、どのブランチにいるかによって異なります。これにより、非常に煩雑な議論になり、書き起こすのが面倒です。

より効率的なサブマスクループ

上記のひどいコードでは、パズルを見つけるためにすべての可能な部分集合を反復処理しました。しかし、これは信じられないほど無駄です。例えば、部分集合にN-2N-2セル未満しかない場合、対応する解は一意ではありません（少なくとも2つの数字が存在しないはずです。それらを解で入れ替えると新しい解が得られますが、パズルは変更されません）。

同様に、部分集合が大きすぎる場合、最小でない可能性が非常に高いです。「大きすぎる」が何を意味するかは問題です。例えば、9x9 の場合、40または41桁のパズルが存在します[1] 。つまり、安全のために部分集合のサイズの Сは少なくとも N2/2N^2 / 2、あるいはそれ以上であるべきです。

部分集合のセル数に上限と下限を決定したら、次のようにフィルタリングできます。

masks = [i for i in range(2 ** (N**2)) if lowerBound <= i.bit_count() <= upperBound]
for subsetMask in masks:
    # [...]

リソース

ひどいPythonコードを含むリポジトリ：github.com/Fran314/how-many-4x4-sudokus

パズルと解（CSV）：

パズルと解（txt/ascii）：

パズルと解（txt/unicode）：

puzzles-with-solutions.tar.gz (tar.gz, 694 KB)

https://en.wikipedia.org/wiki/Mathematics_of_Sudoku ↩︎ ↩︎
興奮、階乗ではない ↩︎
このコードの実際の計算複雑性を知るには、解ごとに可能なパズルの数、または可能な解の数に対する閉じた式を知る必要があると思います。私はこの数を取得するためにハンマーのような近似を行っています。部分集合の反復処理内のロジックを定数としてカウントし、少なくともN!N!の解があると仮定しています（明らかに、はるかに多くの解があります。N!N!は、単一の解のすべての置換から得られるものです）。↩︎
https://math.stackexchange.com/questions/856478/how-many-sudoku-puzzles-are-there-with-at-least-one-solution ↩︎