Techniques for Solving Sudoku Puzzles

Eric C. Chi, Kenneth LangearXiv 2012 · OpenReview

TL;DR

This paper explores three distinct algorithmic approaches—backtracking, simulated annealing, and alternating projections—for solving Sudoku puzzles. While backtracking proves most effective for Sudoku's specific constraints, the paper highlights the value of simulated annealing and alternating projections as generalizable techniques for tackling more complex, high-dimensional combinatorial optimization problems, particularly for educational purposes.

What Problem Does This Paper Address?

The paper addresses the challenge of solving Sudoku puzzles, a popular combinatorial problem. While many heuristics exist, the authors aim to provide a structured comparison of three generic algorithmic techniques: backtracking, simulated annealing, and alternating projections. The motivation extends beyond Sudoku itself; it's about illustrating powerful, broadly applicable optimization methods to students in mathematical sciences, especially those that might scale better to larger, more complex problems where brute-force approaches like backtracking falter. Sudoku serves as a concrete, engaging example to introduce these concepts.

Methods

The paper details and compares three algorithms:

  • Backtracking: This is a systematic, depth-first search approach. It builds a partial solution step-by-step, and if a constraint is violated, it "backtracks" to the previous valid state and tries a different path. The paper notes its infallibility for Sudoku but acknowledges its potential scalability issues for higher-dimensional problems.
  • Simulated Annealing: Inspired by statistical physics, this method explores a solution space by making probabilistic moves. Moves that improve the solution are always accepted, while moves that worsen it are accepted with a probability that decreases over time (controlled by a "temperature" parameter). This allows the algorithm to escape local optima. It's presented as an analog to Markov Chain Monte Carlo (MCMC) methods.
  • Alternating Projections: This technique is used to find a point in the intersection of convex sets. For Sudoku, this involves formulating a continuous relaxation of the problem and then iteratively projecting candidate solutions onto various constraint sets (e.g., row, column, and subgrid constraints). This method aims to handle problems of higher dimensionality by converting discrete problems into continuous ones.

Datasets

The paper does not introduce new datasets. Instead, it uses a collection of Sudoku puzzles:

  • 87 easy puzzles
  • 130 medium puzzles
  • 100 hard puzzles
  • 95 very hard benchmark puzzles

These puzzles were generated from existing code and filtered to exclude those solvable by simple direct inference.

Key Insights and Ideas

  • Sudoku as an educational tool: The paper emphasizes Sudoku's value as an accessible yet non-trivial problem for teaching fundamental algorithmic concepts in combinatorial optimization.
  • Backtracking's strength for Sudoku: For the specific constraints of a 9x9 Sudoku, backtracking is shown to be the most reliable and often fastest method, successfully solving all tested puzzles.
  • Scalability trade-offs: While backtracking is excellent for Sudoku, it's acknowledged that its performance degrades significantly with increasing problem dimensionality. This motivates the exploration of simulated annealing and alternating projections.
  • Alternating projections for continuous relaxation: The paper demonstrates how to transform the discrete Sudoku problem into a continuous optimization problem, allowing for the application of projection techniques. This opens doors for tackling larger, more complex combinatorial challenges.
  • Simulated annealing's struggle with local minima: The paper highlights that simulated annealing can get trapped in local minima, especially on very hard Sudoku puzzles with many constraint violations.

Key Results

  • Success Rates: Backtracking successfully solved 100% of all tested puzzles. Simulated annealing also achieved 100% success on easy and medium puzzles, but dropped to 97% on hard and 41% on the "Top 95" very hard puzzles. Alternating projections had success rates of 85% (easy), 89% (medium), 72% (hard), and 41% (Top 95).
  • CPU Time: Backtracking was consistently the fastest method, with median CPU times in the order of milliseconds across all difficulty levels. Simulated annealing was generally slower, especially on harder puzzles, with maximum times reaching over 7 seconds. Alternating projections showed variable performance, sometimes faster than simulated annealing but generally slower than backtracking, with maximum times around 0.5 seconds on hard puzzles.
  • Alternating Projections vs. Backtracking on Hard Puzzles: For the hardest puzzles, the paper suggests that alternating projections, when successful, might find solutions more quickly than backtracking, as indicated by a scatterplot of solution times.

Limitations and Future Work

  • Limitations of Simulated Annealing: The paper notes that simulated annealing struggles with very hard puzzles that have many local minima, leading to failures or long run times.
  • Limitations of Alternating Projections: While promising for high-dimensional problems, alternating projections did not perform as well as backtracking on easier and medium Sudoku puzzles in terms of success rate and speed.
  • Future Work: The authors implicitly suggest that further exploration of alternating projections and its continuous relaxation approach is warranted for tackling significantly larger combinatorial optimization problems beyond Sudoku. They also point to the availability of their code for further research.

Summary updated

Abstract

Solving Sudoku puzzles is one of the most popular pastimes in the world. Puzzles range in difficulty from easy to very challenging; the hardest puzzles tend to have the most empty cells. The current paper explains and compares three algorithms for solving Sudoku puzzles. Backtracking, simulated annealing, and alternating projections are generic methods for attacking combinatorial optimization problems. Our results favor backtracking. It infallibly solves a Sudoku puzzle or deduces that a unique solution does not exist. However, backtracking does not scale well in high-dimensional combinatorial optimization. Hence, it is useful to expose students in the mathematical sciences to the other two solution techniques in a concrete setting. Simulated annealing shares a common structure with MCMC (Markov chain Monte Carlo) and enjoys wide applicability. The method of alternating projections solves the feasibility problem in convex programming. Converting a discrete optimization problem into a continuous optimization problem opens up the possibility of handling combinatorial problems of much higher dimensionality.
BibTeX
@misc{chi2012techniques,
  author = {Eric C. Chi and Kenneth Lange},
  title = {{Techniques for Solving Sudoku Puzzles}},
  year = {2012},
  eprint = {1203.2295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1203.2295},
}
Figure