Symmetric Sudoku-Type Games from Perfect Codes

Technical Summary: Symmetric Sudoku-Type Games from Perfect Codes

Problem Statement
While standard $9 \times 9$ Sudoku is a well-studied combinatorial object with rich symmetry, many variants (such as Jigsaw Sudoku) alter grid partitions in ways that destroy rotational and reflective symmetries. This loss of symmetry renders many standard solving strategies and theoretical tools inapplicable. The paper addresses the need for a generalized framework to construct Sudoku-type games that preserve high levels of symmetry analogous to the classical game, while offering new structural variations.

Methodology
The authors propose a construction method based on Lee distance perfect codes and diameter perfect codes over rings of integers modulo $n$ ($\mathbb{Z}_n$).

1. Theoretical Foundation: The method utilizes the "tiling property" of these codes. A perfect code $C$ partitions the space $\mathbb{Z}_n^2$ into disjoint balls of radius $t$. A "diameter perfect code" achieves equality in the Code-Anticode Bound, partitioning the space using anticodes of a specific diameter.
2. Grid Construction:
   • A palette grid $I$ is constructed where each cell $(x, y)$ is assigned a symbol based on which codeword's ball (or anticode translate) contains that coordinate.
   • A Sudoku grid $S$ is defined as a Latin square of order $n$ that is orthogonal to the palette grid $I$. This orthogonality ensures that every symbol appears exactly once within the regions defined by the code's tiling.
3. Equivalence Relations: The authors define equivalence classes for the resulting grids under:
   • Relabeling: Permutation of symbols.
   • Rigid Motions: A specific group $G_S$ generated by rotations, reflections, and translations that preserve the underlying code structure.
4. Case Studies: The framework is applied to two minimal cases:
   • $5 \times 5$ Sudoku: Constructed from a 1-error-correcting perfect code in $\mathbb{Z}_5^2$ (where $n=5$).
   • $8 \times 8$ Sudoku: Constructed from 3-diameter perfect codes in $\mathbb{Z}_8^2$ (where $n=8$).
5. Difficulty Assessment: A "human-like solver" is implemented to evaluate playability. This solver uses only elementary logical deductions (Naked Single and Hidden Single) combined with a trial-and-error phase. Difficulty is quantified by the number of trial-and-error insertions required beyond the initial clues.

Key Contributions and Results

• Enumeration of Solutions:
  • For the $5 \times 5$ case, the authors identified 2,040 valid grids. Up to relabeling and the action of the rigid motion group, these reduce to 17 inequivalent solutions.
  • For the $8 \times 8$ case, two distinct types of diameter perfect codes were analyzed. The first type yielded approximately $2.80 \times 10^{11}$ valid grids, reducing to 232,735 inequivalent solutions. The second type yielded approximately $1.95 \times 10^{11}$ valid grids, reducing to 304,014 inequivalent solutions.
• Minimal Sudoku Analysis:
  • For the $5 \times 5$ case, the authors enumerated minimal Sudoku puzzles (those with the minimum number of clues required for a unique solution). They found a total of 15,898,200 minimal puzzles (35,759 up to equivalence) with clue counts ranging from 4 to 7.
  • For the $8 \times 8$ case, a full enumeration of minimal puzzles was deemed computationally infeasible. Instead, the authors identified minimal puzzles with clue counts ranging from 10 to 18.
• Special Grids: The study identified "special Sudoku grids" which satisfy the Sudoku constraints for any perfect code of the given parameters, not just the specific one used for construction. There are 240 such grids for $5 \times 5$ and $4 \times 8!$ for $8 \times 8$.
• Difficulty Distribution: The analysis of the $5 \times 5$ games using the human-like solver revealed a balanced distribution of difficulty levels. Puzzles were classified as Easy (score 0), Medium (score 1–10), and Hard (score >10). The results showed a viable mix of difficulties, with many puzzles solvable by basic logic and others requiring significant trial-and-error.

Significance and Claims
The paper claims that perfect codes provide a systematic and mathematically rigorous framework for generating symmetric Sudoku-type games. The primary significance lies in demonstrating that:

1. Symmetry Preservation: Unlike irregular variants, these code-based constructions inherently preserve the rotational and reflective symmetries found in classical Sudoku, allowing for the application of standard group-theoretic analysis.
2. Structural Diversity: The framework generates structurally diverse valid grids, expanding the landscape of Sudoku beyond the standard $9 \times 9$ format.
3. Practical Playability: The difficulty analysis confirms that these games are not merely theoretical constructs but offer a "balanced distribution of difficulty levels, ranging from Easy to Hard," making them viable alternatives to traditional Sudoku for recreational play.

The authors conclude that this approach bridges coding theory and recreational mathematics, offering a new avenue for generating logic puzzles with rich algebraic structures. Future work is suggested to extend these constructions to other rings and distance metrics (e.g., Mannheim or rank metrics).