Integer Programming Model for the Sudoku Problem

Author(s): 
Andrew Bartlett, Timothy P. Chartier, Amy N. Langville, and Timothy D. Rankin

Author Information

Andrew Bartlett graduated from the College of Charleston Master's in Mathematics program in 2007 and is now pursuing a Ph.D. in Statistics at the University of Georgia. Tim Chartier is an Assistant Professor of Mathematics at Davidson College. Amy Langville is an Assistant Professor of Mathematics at the College of Charleston. Tim Rankin is a 2007 graduate of Davidson College and is now pursuing a Ph.D. in mathematics at Duke University.

Abstract

Sudoku is the recent craze in logic puzzles. Players must fill in an n × n matrix, which contains some given entries, so that each row, column, and m × m submatrix contains each integer 1 through n exactly once. Two issues associated with these puzzles interest us mathematically: puzzle solution and puzzle creation. A Sudoku puzzle can be solved by creating a feasibility problem where the goal is to find at least one feasible solution to the puzzle. We present a binary integer linear program to solve this feasibility problem. Further, such an approach is extended to variations on the traditional Sudoku puzzle. In addition, we speculate as to how Sudoku puzzles are created, and provide several theorems for generating many new puzzles from one given original puzzle. Java applets allow for exploration with a variety of the ideas. Readers with Matlab and its Optimization Toolbox can solve Sudoku puzzles directly from an applet. Exercises and challenge problems that use principles from optimization, combinatorics, linear algebra, and computer science are presented for students.

Technologies Used in This Article

  • This article uses jsMath to display mathematical expressions. You will need the free jsMath fonts installed on your computer.
  • jsMath and other elements in the article use JavaScript. You will need JavaScript enabled in your browser.
  • The applets in this article are written in Java. You will need the Java Plug-in (version 1.5 or later).
  • One applet requires a computer to have Matlab and the Matlab Optimization Toolbox to solve a Sudoku puzzle as a binary integer linear program.

Publication Data

  • Published May 2008, article ID 1798
  • Copyright © 2008 by Andrew C. Bartlett, Timothy Chartier, Amy N. Langville, and Timothy D. Rankin

Article Link