Binary Integer Linear Program

A linear program is an algorithm of use when the objective function, or goal, can be expressed as an equation that is linear in the decision variables, and all constraints are likewise linear in the decision variables. An Binary Integer Linear Program is a linear program where the decision variables can take on only two values, 0 and 1.

Sudoku can be programmed as a binary integer linear program by defining the decision variables

x(i,j,k) = 0 if cell i, j in the grid is not equal to k

x(i,j,k) = 1 if cell i, j in the grid is equal to k

The x(i,j,k) can then be limited by the four constraint types.

Using the terminology of linear programming, Sudoku is a constraint satisfaction problem (or feasibility problem), meaning that the objective function is arbitrary, and the goal is to simply find a feasible solution, i. e. one that does not violate any constraint.

Integer programming (IP) problems are often solved using the branch and bound algorithm. IPs are frequently found in operations research.

Reference

Barlett, Andrew C. and Amy N. Langville (2006), An Integer Programming Model for the Sudoku Problem, College of Charleston Working Paper.