Upper Bounds for the Number of Solutions to Spatially Coupled Sudokus

Tadahiro Kitazono, Kazushi Mimura

Abstract

Based on combinatorics, we evaluate the upper bounds for the number of solutions to spatially coupled Sudokus, which are popular logic puzzles.

Introduction

The intersection of recreational mathematics and information theory offers unique insights into complex system constraints. This paper explores "spatially coupled" Sudokus—massive puzzles where multiple $9 \times 9$ grids overlap and share blocks. While standard Sudokus are well-characterized, variants like Shogun (11 grids) or Sumo (13 grids) present a significant computational challenge: counting their exact solutions is often impossible via brute force.

By treating these puzzles as a form of error-correcting code, similar to Low-Density Parity-Check (LDPC) codes used in communication systems, the authors derive mathematical upper bounds for their solution space. This framework allows for the measurement of information density and entropy within these interconnected structures.

The Sumo Sudoku, featuring 13 overlapping grids, represents a high-complexity spatially coupled puzzle.

Methodology

The research utilizes combinatorial techniques to establish a theoretical "ceiling" for the number of valid grid assignments. The approach builds on Herzberg’s method of using the permanent of a matrix to count permutations.

  1. Matrix Permanents and Brègman’s Theorem: The authors construct $(0,1)$-matrices where a 1 denotes a permissible digit for a cell. Since calculating the permanent is #P-complete, Brègman’s Theorem is employed to provide a tractable upper bound.
  2. Grid Decomposition: Complex architectures are decomposed into sequences of "partly filled" $n \times n$ Sudokus. A novel formula, $S_U(n; c_1, c_2)$, is derived to calculate the upper bound for a grid where a rectangular area of $c_1 \times c_2$ blocks is pre-filled by an adjacent overlapping grid.
  3. Asymptotic Analysis: Using Stirling’s formula, the authors evaluate the behavior of these bounds as the grid size $n$ approaches infinity, allowing for the study of theoretical infinite chains.

Key Results and Insights

The study reveals that spatial coupling significantly constrains the solution space. Sharing blocks between grids imposes strict limitations on neighbors, which the authors quantify through reduced upper bounds.

  • Standard Sudoku ($3 \times 3$): The upper bound is $\approx 1.7 \times 10^{26}$ (exact count is $\approx 6.67 \times 10^{21}$).
  • Shogun Sudoku: Established an upper bound of $\approx 1.5993 \times 10^{208}$ solutions.
  • Sumo Sudoku: Established an upper bound of $\approx 1.7045 \times 10^{241}$ solutions.

For infinite chains, such as the Stair and Belt variants, the "coding rate" $R$ (a measure of information density) converges to a stable constant. Interestingly, the geometry of the coupling matters: the Belt Sudoku maintains a higher coding rate ($\approx 0.2727$) than the Stair Sudoku ($\approx 0.2609$).

The Stair Sudoku is a theoretical infinite chain of overlapping grids used to study asymptotic coding rates.

Conclusion and Future Work

While the derived bounds provide a necessary theoretical ceiling, they remain several orders of magnitude larger than actual solution counts. This "looseness" stems from the difficulty of simultaneously capturing row, column, and block constraints using current mathematical tools. Future research will aim to develop tighter upper bounds and establish corresponding lower bounds to more precisely bracket the solution space of these complex puzzles.

Summary updated

Abstract

Based on combinatorics, we evaluate the upper bounds for the number of solutions to spatially coupled Sudokus, which are popular logic puzzles.
BibTeX
@inproceedings{kitazono2016upper,
  author = {Tadahiro Kitazono and Kazushi Mimura},
  title = {{Upper Bounds for the Number of Solutions to Spatially Coupled Sudokus}},
  booktitle = {Isita},
  year = {2016},
}
Figure