Redundant Sudoku Rules

Bart Demoen, Maria Garcia de la BandaarXiv 2012 · DOI · OpenReview

TL;DR

This paper investigates the minimum set of rules (constraints) needed to define a valid Sudoku puzzle. The authors prove that out of the standard 27 "big" Sudoku rules (all-different constraints for rows, columns, and boxes), any six can be removed, and the remaining 21 are still sufficient to define Sudoku. They also conjecture that a similar redundancy exists for the "small" pairwise inequality constraints.

What Problem Does This Paper Address?

The standard definition of a Sudoku puzzle involves 27 "big" constraints, each ensuring that a row, column, or 3x3 box contains distinct numbers from 1 to 9. This paper tackles the question of whether all 27 of these constraints are strictly necessary. Specifically, it asks: can we remove some of these constraints and still have a system that uniquely defines a Sudoku solution? This is a question about redundancy in constraint satisfaction problems, with implications for how we model and solve Sudoku and potentially other complex constraint-based puzzles.

Methods

The authors employ a combination of graphical representations and exploratory logic programming (specifically, Prolog) to analyze Sudoku constraints.

  • Graphical Representation: They develop a visual method to represent sets of Sudoku constraints, where shaded areas indicate missing constraints. This allows for an intuitive understanding of which constraints are present and which are absent.
  • Constructive Lemmas: They prove two "positive lemmas" that demonstrate how a subset of constraints can logically entail another constraint. These lemmas act as building blocks for proving redundancy.
  • Exploratory Logic Programming: A Prolog program is used to systematically explore combinations of missing constraints. This program applies the constructive lemmas to see if a model with fewer than 27 constraints can still be proven equivalent to Sudoku.
  • Negative Lemmas: To prove that certain sets of constraints are not redundant (i.e., removing them leads to a system that is not Sudoku), they use "negative lemmas." These involve constructing specific Sudoku grids that are valid solutions for a system with missing constraints but become invalid if those constraints are added back.

Datasets

Not discussed in the paper. The paper focuses on the theoretical properties of Sudoku constraints rather than empirical evaluation on a dataset of puzzles. However, they do mention using a set of over 50,000 minimal Sudoku puzzles from Gordon Royle's website for testing their conjecture about small constraints.

Key Insights and Ideas

  • Significant Redundancy in "Big" Constraints: The most striking finding is that a substantial number of the standard Sudoku rules are redundant. Removing six "big" constraints (leaving 21) still results in a system equivalent to Sudoku. This is a non-trivial reduction and suggests that the standard formulation is more verbose than necessary.
  • Maximality of Redundancy: The paper establishes that six is the maximal number of "big" constraints that can be removed while maintaining Sudoku equivalence. Removing seven or more constraints will, in some cases, lead to a system that is no longer equivalent to Sudoku.
  • Graphical Proofs are Powerful: The authors highlight the effectiveness of their graphical representation in simplifying complex proofs about constraint relationships. This approach could be valuable for analyzing other constraint satisfaction problems.
  • Exploratory Programming as a Discovery Tool: The paper emphasizes how logic programming was crucial for discovering theorems and lemmas, guiding the research process, and managing the combinatorial complexity.
  • Conjecture on "Small" Constraints: While a full classification for "small" (pairwise inequality) constraints is not achieved, the paper conjectures that a significant portion of these are also redundant, with a minimum of 648 constraints potentially being necessary.

Key Results

  • 21 "Big" Constraints are Sufficient: The paper proves that any set of 21 "big" Sudoku constraints (out of the standard 27) is sufficient to define Sudoku.
  • Six is the Maximal Number of Redundant "Big" Constraints: It is impossible to remove more than six "big" constraints and still guarantee Sudoku equivalence.
  • Classification of Missing(6) Models: The research successfully classifies all models with six missing "big" constraints, identifying which ones are still equivalent to Sudoku and which are not.
  • Conjecture on Small Constraints: The paper conjectures that no Sudoku model with fewer than 648 "small" constraints is possible.

Limitations and Future Work

  • Full Classification of Small Constraints: The paper presents a conjecture for the minimum number of "small" constraints but does not provide a complete proof or classification for all possible redundant sets of small constraints. This remains an open problem.
  • Generalization to Other Puzzle Sizes: While the techniques are adaptable to Sudoku puzzles of different sizes (e.g., 4x4), a full investigation for these variations is beyond the scope of this paper.
  • Performance Implications: The authors note that while redundant constraints can sometimes slow down solvers, understanding redundancy is key to developing more efficient encodings and inference techniques. Their work on Sudoku can inform more general inequality inference frameworks.

Summary updated

Abstract

The rules of Sudoku are often specified using twenty seven \texttt{all\_different} constraints, referred to as the {\em big} \mrules. Using graphical proofs and exploratory logic programming, the following main and new result is obtained: many subsets of six of these big \mrules are redundant (i.e., they are entailed by the remaining twenty one \mrules), and six is maximal (i.e., removing more than six \mrules is not possible while maintaining equivalence). The corresponding result for binary inequality constraints, referred to as the {\em small} \mrules, is stated as a conjecture.
BibTeX
@misc{demoen2012redundant,
  author = {Bart Demoen and Maria Garcia de la Banda},
  title = {{Redundant Sudoku Rules}},
  year = {2012},
  eprint = {1207.5926},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.5926},
}
Figure