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

4x4のスドクは12種類しかない！…あるいは、何をもって異なる解とみなすかによりますが、288通りです。 何が、なぜ、そして正確には何なのか 今日の探求は、ユニークな4x4スドクの解（および可能なパズル）がいくつあるか、です。なぜかって？私にも分かりませんが、その疑問がふと頭に浮かび、その答えはちょっと面白いと思ったのです。 もし馴染みがない方のために説明すると、4x4スドクとは、行、列、そして2x2のボックスに分割された4x4のグリッドで、各セルを1から4までの数字で埋めることを目指すパズルです。各行、各列、各ボックスで、すべての数字がちょうど一度ずつ現れるようにします。 ╔═══╤═══╦═══╤═══╗ ║ │ ║ │ ║ ╟───┼───╫───┼───╢ ║ │ ║ │ ║ ╠═══╪═══╬═══╪═══╣ ║ │ ║ │ ║ ╟───┼───╫───┼───╢ ║ │ ║ │ ║ ╚═══╧═══╩═══╧═══╝ これは、より一般的な9x9スドク（同様に3x3ボックスに分割されている）の小さいケースにあたります。これはN×Nのスドクに一般化され、N=n^2となるような整数nが存在します。n=2の場合は4x4スドクになり、次のステップはn=3で9x9スドクです。 通常、これらのパズルは部分的に埋められたグリッドから始まります（空のグリッドの解を見つけるのは簡単だからです）。しかし、今回は、空の開始位置から、有効なすべての埋め方を「解」とみなします。 例えば、ここに3つの異なる有効な4x4スドクの解があります。 (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を互いに交換しただけです。 通常の（つまり、バリアントではない）スドクの文脈では、グリッドを埋めるために使用する数字は単なる無意味な記号です。もし望むなら、「🔴, 🟣, 🔵, 🟢」を「1, 2, 3, 4」の代わりに使って同じパズルを解くことができます。パズルは全く同じままです。同様に、数字を色の形に交換するのではなく、数字と数字を交換しても、パズルは同じままです。 この観点から、解(A)と(B)は同じパズルの異なる記号を使っていると理解できます。それらは同じ基盤構造を持っています。逆に、(A)と(C)は構造的に異なります。数字をいくら交換しても、解(A)では行2列1と行1列4のセルは同じ記号を含んでいますが、解(C)では同じセルが異なる記号を含んでいます。 したがって、私たちが尋ねている質問は次のとおりです。 4x4スドクの解はいくつ存在しますか？そして、これらの解のうち、構造的に実際に異なるものはいくつありますか？ 初期回答と、ひどいPythonコード 簡単な質問から始めましょう：同じ構造を持つ可能性のある4x4スドクの解はいくつ存在しますか？幸いなことに、扱っている数字は非常に小さいので、これは一瞬でブルートフォースで解決できます。 その（素朴な）方法は、空のグリッドから始めて、各セルについて残りの可能な値を特定し、深さ優先で各可能な値を再帰的に探索することです。 CodeHelpers python 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)) python 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)} 約半秒で、このコードは次のように出力します。 Number of total solutions: 288 わずか288通り！これは、n=3の次のステップである9x9標準スドクの6,670,903,752,021,072,936,960通りと比較すると、ごくわずかな数です！[2] 同時に、非常に不正確なナプキン計算で、Nの関数としての可能な解の数を非常に大まかに近似できます。列とボックスの制約を無視し、行の制約のみを考慮すると、各行にはN!通りの可能な組み合わせがあり、N行あるため、可能な組み合わせの総数はN!^N = (n^2!)^(n^2)となります。 これはひどい上限値であることに注意してください。n=3でこの公式を使用すると約10^50となり、正しい答えである約6.6×10^21をはるかに超えます。 それでも、n=2は小さく、n=3は大きいです！ 実際に異なる解を数える 次に、実際に異なる解、つまり解が持ちうる異なる構造を数えたいと思います。 すでに見たように、任意の解が与えられた場合、数字1, 2, 3, 4の任意の順列を適用して新しい解を得ることができます。4! = 24通りの順列があるので、すべての構造は24倍過大評価されていることになります。したがって、理論上、実際に異なる解の数は次のようになります。 288 / 24 = 12通りの異なる解 この質問にアプローチする別の方法があり、それは以前のひどいPythonコードを再利用することを可能にします。重要な事実は次のとおりです。 数字を単なる記号として扱います。それが実際に何であるかは気にしません。それらは何でもよく、それらの任意の順列は有効です。 任意の解において、最初の行（他の行と同様に）は4つの異なる記号を含むことが保証されています。 次に、アイデアは次のとおりです。任意の解構造が与えられた場合、最初の行の最初の記号を1、最初の行の2番目の記号を2、そして3と4についても同様に呼び出します。このようにして、最初の行に1 2 3 4で始まる対応する解で各構造を表すことができます。 2つの異なる解S1、S2が両方とも1 2 3 4で始まる場合、それらは構造的にも異なる必要があることに注意してください。 もしそれらが同じ構造を持っていたら、数字の順列σが存在し、σをS1に適用するとS2が得られるはずです。 しかし、もしσが任意の数字を交換する場合、それをS1に適用すると、1 2 3 4で始まらない解が得られるため、S2と等しくなることはできません。 同様に、もしσがすべての数字をそのままにしておく場合、それをS1に適用すると、正確にS1が得られます。これは仮定によりS2と等しくありません。 したがって、そのようなσは存在できません。