An Integer Programming Model for the Sudoku Problem

TLDR

Sudoku is a popular logic puzzle requiring an n×n grid to be filled with numbers 1–n so that each row, column, and m×m subgrid contains each integer exactly once. The authors aim to solve and generate Sudoku puzzles by formulating them as a binary integer linear programming feasibility problem and extending this approach to variations. They model Sudoku as a binary integer linear program that seeks at least one feasible solution, and adapt the formulation to handle different puzzle variants. The study presents theorems for generating numerous new puzzles from a single original puzzle and offers exercises and challenges that illustrate optimization, combinatorics, linear algebra, and computer science concepts.

Abstract

Sudoku is the recent craze in logic puzzles. Players must flll 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 flnd 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. Exercises and challenges problems that use principles from optimization, combinatorics, linear algebra, and computer science are presented for students.