Search Journal of Online Mathematics and its Applications:
Journal of Online Mathematics and its Applications
Page 1 of 1
Integer Programming Model for the Sudoku Problem
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.
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