Abstract
We describe an online, interactive system with a
graphical interface to illustrate the power and operation
of consistency algorithms in a friendly and
popular context, namely, solving Sudoku puzzles.
Our tool implements algorithms for enforcing five
(domain-based) consistency properties on binary
and non-binary constraint models. Our tool is useful
for research, education, and outreach. From
a scientific standpoint, we propose a new consistency
property that can solve the hardest known
9×9 Sudoku instances without search, but leave
open the question of the lowest level of consistency
needed to solve every 9×9 Sudoku puzzle. We
have used the current tool and its predecessor in the
classroom to introduce students to modeling problems
with constraints, explain consistency properties,
and illustrate the operations of constraint propagation
and lookahead. Finally, we have also used
this tool during outreach activities to demystify AI
to children and the general public and show them
how computers think.
Keywords
- Constraints and Satisfiability: Constraint Satisfaction
- Multidisciplinary Topics and Applications: Human-Computer Interaction
