Conference site ยป Proceedings

Modeling Sudoku Puzzles with Python

Sean Davis
Berea College

Matthew Henderson
Berea College

Andrew Smith
Berea College

Abstract

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

Keywords

sudoku, mathematics, graph theory

Bibtex entry

Full text PDF