Symmetric Sudoku-Type Games from Perfect Codes

技術的概要：完全符号に基づく対称性を持つ数独型ゲーム

問題提起
標準的な $9 \times 9$ 数独は、豊かな対称性を持つよく研究された組合せ対象であるが、多くのバリエーション（ジグソー数独など）は、回転対称性や鏡像対称性を破壊する形でグリッドの分割を変更する。この対称性の喪失は、多くの標準的な解法戦略や理論的ツールの適用を不可能にする。本論文は、古典的なゲームと同様の高い対称性を維持しつつ、新たな構造的変種を提供する数独型ゲームを構築するための一般化された枠組みの必要性に取り組む。

方法論
著者は、整数の剰余環 $\mathbb{Z}_n$ 上のリー距離完全符号および直径完全符号に基づく構築手法を提案する。

1. 理論的基盤: この手法は、これらの符号の「タイリング性質」を利用する。完全符号 $C$ は、空間 $\mathbb{Z}_n^2$ を半径 $t$ の互いに素な球に分割する。「直径完全符号」は、符号 - 反符号境界において等号を満たし、特定の直径を持つ反符号を用いて空間を分割する。
2. グリッド構築:
   • 各セル $(x, y)$ に、その座標を含む符号語の球（または反符号の平行移動）に基づいて記号を割り当てるパレットグリッド $I$ を構築する。
   • 数独グリッド $S$ を、パレットグリッド $I$ と直交する $n$ 次のラテン方格として定義する。この直交性により、符号のタイリングによって定義される領域内において、各記号が正確に 1 回現れることが保証される。
3. 同値関係: 著者は、生成されたグリッドに対して以下の同値類を定義する。
   • ラベル付け替え: 記号の置換。
   • 剛体運動: 基礎となる符号構造を保存する回転、鏡像、平行移動によって生成される特定の群 $G_S$。
4. ケーススタディ: この枠組みは、2 つの最小ケースに適用される。
   • $5 \times 5$ 数独: $\mathbb{Z}_5^2$ 内の 1 誤り訂正完全符号（ここで $n=5$）から構築される。
   • $8 \times 8$ 数独: $\mathbb{Z}_8^2$ 内の 3 直径完全符号（ここで $n=8$）から構築される。
5. 難易度評価: 遊びやすさを評価するために「人間のようなソルバー」を実装する。このソルバーは、試行錯誤フェーズと組み合わせた基本的な論理的推論（裸のシングルと隠れたシングル）のみを使用する。難易度は、初期の手がかりを超えて必要な試行錯誤の挿入回数によって定量化される。

主要な貢献と結果

• 解の列挙:
  • $5 \times 5$ の場合、著者は 2,040 個の有効グリッドを特定した。ラベル付け替えと剛体運動群の作用を考慮すると、これらは 17 個の非同値解に帰着する。
  • $8 \times 8$ の場合、2 種類の異なる直径完全符号タイプが分析された。最初のタイプは約 $2.80 \times 10^{11}$ 個の有効グリッドを生み出し、232,735 個の非同値解に帰着した。2 番目のタイプは約 $1.95 \times 10^{11}$ 個の有効グリッドを生み出し、304,014 個の非同値解に帰着した。
• 最小数独の分析:
  • $5 \times 5$ の場合、著者は一意の解を持つために必要な最小の手がかり数を持つ最小数独パズルを列挙した。その結果、手がかり数が 4 から 7 の範囲で、合計 15,898,200 個の最小パズル（同値を除くと 35,759 個）が見つかった。
  • $8 \times 8$ の場合、最小パズルの完全な列挙は計算上非現実的と判断された。代わりに、著者は手がかり数が 10 から 18 の範囲にある最小パズルを特定した。
• 特殊グリッド: この研究は、構築に使用された特定の符号だけでなく、与えられたパラメータを持つ任意の完全符号に対しても数独の制約を満たす「特殊な数独グリッド」を特定した。$5 \times 5$ には 240 個、$8 \times 8$ には $4 \times 8!$ 個のそのようなグリッドが存在する。
• 難易度分布: 人間のようなソルバーを用いた $5 \times 5$ ゲームの分析は、難易度レベルのバランスの取れた分布を明らかにした。パズルは、易しい（スコア 0）、中級（スコア 1–10）、難しい（スコア >10）に分類された。結果は、基本的な論理で解けるパズルと、大幅な試行錯誤を必要とするパズルが混在する実用的な難易度の混合を示した。

意義と主張
本論文は、完全符号が、対称性を持つ数独型ゲームを生成するための体系的かつ数学的に厳密な枠組みを提供すると主張する。主な意義は、以下の点を示すことにある。

1. 対称性の維持: 不規則なバリエーションとは異なり、これらの符号に基づく構築は、古典的な数独に見られる回転対称性と鏡像対称性を本質的に維持し、標準的な群論的分析の適用を可能にする。
2. 構造的な多様性: この枠組みは、構造的に多様な有効グリッドを生成し、標準的な $9 \times 9$ フォーマットを超えて数独の領域を拡大する。
3. 実用的な遊びやすさ: 難易度の分析は、これらゲームが単なる理論的構成物ではなく、「易しいものから難しいものまで、バランスの取れた難易度レベルの分布」を提供することを確認し、娯楽としての従来の数独に対する実用的な代替手段となることを示している。

著者は、このアプローチが符号理論と娯楽数学を橋渡しし、豊かな代数的構造を持つ論理パズルを生成するための新たな道を開くと結論づけている。今後の研究として、これらの構築を他の環や距離尺度（例えば、マンハイム距離やランク距離）に拡張することが提案されている。