Solving Sudoku with Consistency: A Visual and Interactive Approach

Ian Howell, Robert J. Woodward, Berthe Y. Choueiry, Christian BessiereIJCAI 2018 · DOI

TL;DR

This paper introduces an interactive web-based tool that visualizes constraint satisfaction algorithms for solving Sudoku puzzles. It proposes a new consistency property that can solve the hardest Sudoku instances without search and explores the hierarchy of consistency levels needed for Sudoku.

What Problem Does This Paper Address?

Solving Sudoku puzzles, while seemingly simple, is a computationally challenging problem (NP-complete). Existing online solvers often rely on brute-force search or complex, human-defined rules. This paper aims to bridge the gap between the accessibility of Sudoku and the underlying complexity of constraint satisfaction problems (CSPs). Specifically, it addresses how to effectively teach and demonstrate CSP concepts, particularly consistency properties, using a familiar and engaging context like Sudoku. The authors also investigate the fundamental question of the minimal level of consistency required to solve any given Sudoku puzzle without resorting to search.

Methods

The core of this work is an interactive web application built with HTML, CSS, and JavaScript. This tool implements algorithms for enforcing five different domain-based consistency properties on both binary and non-binary constraint models of Sudoku. These properties, ranging from Arc Consistency (AC) to Double Singleton Arc Consistency (SSAC), are visualized on a Sudoku board. The tool allows users to apply these consistency algorithms and observe how they prune the possible values for each cell. A novel consistency property, which the authors claim can solve the hardest known Sudoku instances without search, is also introduced and implemented. The system also includes a backtrack search mechanism for handling ill-formed puzzles with multiple solutions.

Datasets

The paper mentions a file containing 375 instances of the hardest known Sudoku puzzles, which was used to evaluate the effectiveness of their proposed consistency properties. The tool also includes a database of Sudoku instances with metadata like the number of clues and the weakest consistency level required for solving them without search.

Key Insights and Ideas

  • Sudoku as a pedagogical tool: Sudoku provides an accessible and engaging context for teaching complex AI concepts like constraint satisfaction and consistency propagation.
  • Visualizing consistency: The interactive nature of the tool allows users to directly see how consistency algorithms prune the search space, making abstract concepts tangible.
  • A new, powerful consistency property: The paper introduces a novel consistency property that is capable of solving even the most difficult Sudoku puzzles without any search, highlighting the potential of advanced consistency techniques.
  • Hierarchy of consistency: The work explores the relationship between different consistency levels, demonstrating that stronger properties are more effective at reducing the search space, and raises the question of the minimal required consistency for Sudoku.

Key Results

The paper reports that their proposed consistency property, along with others, can solve all 375 of the hardest known Sudoku instances without search. Specifically, they found that 276 instances required at least SSGAC, 25 required BiSGAC+SSAC, 7 required BiSGAC, and 67 required SSAC. The interactive tool has been successfully used in classrooms to teach constraint modeling and consistency, and in outreach activities to demystify AI to the public.

Limitations and Future Work

The paper acknowledges that the question of the lowest level of consistency needed to solve every 9x9 Sudoku puzzle without search remains open. While their new property solves the hardest instances, a comprehensive analysis of the minimal requirement across all possible Sudoku puzzles is still a research direction. The authors also suggest that the tool could be further enhanced with more advanced visualization mechanisms and potentially extended to other CSP domains beyond Sudoku.

Summary updated

BibTeX
@inproceedings{howell2018solving,
  author = {Ian Howell and Robert J. Woodward and Berthe Y. Choueiry and Christian Bessiere},
  title = {{Solving Sudoku with Consistency: A Visual and Interactive Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/852},
}

Loading related content...

Figure