Modeling Sudoku Puzzles with Python
Sean Davis
Matthew Henderson
Andrew Smith
The popular Sudoku puzzles which appear daily in newspapers the world over
have, lately, attracted the attention of mathematicians and computer
scientists. There are many, difficult, unsolved problems about Sudoku
puzzles and their generalizations which make them especially interesting to
mathematicians. Also, as is well-known, the generalization of the Sudoku
puzzle to larger dimension is an NP-complete problem and therefore of
substantial interest to computer scientists.
In this article we discuss the modeling of Sudoku puzzles in a variety of
different mathematical domains. We show how to use existing third-party
Python libraries to implement these models. Those implementations, which
include translations into the domains of constraint satisfaction, integer
programming, polynomial calculus and graph theory, are available in an
open-source Python library sudoku.py developed by the authors and
available at http://bitbucket.org/matthew/scipy2010
sudoku, mathematics, graph theory
DOI10.25080/Majora-92bf1922-009