# Solving Sudoku with MATLAB

*Today's guest article is by Wesley Hamilton, a STEM Outreach engineer here at MathWorks. Wesley's roles involve popularizing the use of MATLAB and Simulink for younger folk, especially towards mathematical topics, and this blog is an accompanying piece to a workshop being run by the National Museum of Math in New York City.*

Solving Sudoku Puzzles, part 1

Linear Programming

Sudoku as a Linear Program

Box constraints

Row constraints

Column constraints

Subgrid constraints

Solving Sudoku Puzzles, part 2

Ordering of decision variables

Box constraints

Row constraints

Column constraints

Subgrid constraints

The givens

Further directions

Just the code

## Rules and History of Sudoku

- Every row of the grid contains each of the digits 1-9, and each digit only appears once,
- Every column of the grid contains each of the digits 1-9, and each digit only appears once,
- Every 3x3 subgrid contains each of the digits 1-9, and each digit only appears once.

## Solving Sudoku Puzzles, part 1

- Every row of the grid contains each of the digits 1-4, and each digit only appears once,
- Every column of the grid contains each of the digits 1-4, and each digit only appears once,
- Every 2x2 subgrid contains each of the digits 1-4, and each digit only appears once.

## Linear Programming

- an optimization problem is a problem in which one seeks the maximum (or minimum) of an objective function, i.e. find a value for x that maximizes a given function $ f(x) $;
- an objective function is the function we want to maximize or minimize. We could just call it a function, but often in optimization problems multiple functions come in to play, including functions that add constraints to the problem, in addition to the function we're optimizing;
- a linear objective function is an objective function that is linear, i.e. takes the form $ f(x) = a_1 x_1 + \cdots + a_n x_n $, for a vector $ x = \pmatrix{x_1 \cr \vdots \cr x_n} $. Writing $ a = \pmatrix{a_1 \cr \vdots \cr a_n} $, this function can also be expressed $ f(x) = a^t x $, where the t superscript means we're taking the matrix transpose of a vector.
- a constraint is a rule for which values of x are feasible, i.e. x must be non-negative, or if x is a vector then all of the components of x must be non-negative;
- a linear constraint is a constraint that's written in the form of a linear equation. For example, if we're working with a vector $ x = \pmatrix{x_1 \cr x_2 \cr x_3} $, then a linear constraint might look like $ x_1 - x_2 + 3 x_3 \leq 0 $. If we write $ b=\pmatrix{1 \cr -1 \cr 3} $, then this linear constraint can also be written $ b^t x \leq 0 $, where the t superscript means we're taking the matrix transpose of a vector.

## Sudoku as a Linear Program

- What are the variables that we're solving for?
- What are the constraints we want to impose?
- What is the function we want to maximize?

### Box constraints

### Row constraints

### Column constraints

### Subgrid constraints

- $ x_{i,j,1} + x_{i,j,2} + x_{i,j,3} + x_{i,j,4} = 1 $ for $ i = 1,...,4 $ and $ j=1,...,4 $, (box constraint)
- $ x_{i,1,k} + x_{i,2,k} + x_{i,3,k} + x_{i,4,k} = 1 $ for $ i = 1,...,4 $ and $ k=1,...,4 $, (row constraint)
- $ x_{1,j,k} + x_{2,j,k} + x_{3,j,k} + x_{4,j,k} = 1 $ for $ j = 1,...,4 $ and $ k=1,...,4 $, (column constraint)
- $ x_{1,1,k} + x_{1,2,k} + x_{2,1,k} + x_{2,2,k} = 1 $ for $ k=1,...,4 $, (top-left subgrid constraint)
- $ x_{1,3,k} + x_{1,4,k} + x_{2,3,k} + x_{2,4,k} = 1 $ for $ k=1,...,4 $, (top-right subgrid constraint)
- $ x_{3,1,k} + x_{3,2,k} + x_{4,1,k} + x_{4,2,k} = 1 $ for $ k=1,...,4 $, (bottom-left subgrid constraint)
- $ x_{3,3,k} + x_{3,4,k} + x_{4,3,k} + x_{4,4,k} = 1 $ for $ k=1,...,4 $. (bottom-right subgrid constraint)

## Solving Sudoku Puzzles, part 2

### Ordering of decision variables

- Order the variables by incrementing the digit index first, then the column index, then the row index: $ x_{1,1,1}, x_{1,1,2}, ..., x_{1,1,4}, x_{1,2,1}, x_{1,2,2}, ... $ This enumeration will list all the digit design variables first before going to a new box.
- Order the variables by incrementing the row index first, then the column index, then the digit index: $ x_{1,1,1}, x_{2,1,1}, ..., x_{4,1,1}, x_{1,2,1}, x_{2,2,1}, ... $ This enumeration will iterate through the entire grid by going down columns then across rows, before increment the digit index and iterating through again.
- Order the variables by incrementing the column index first, then the row index, then the digit index: $ x_{1,1,1}, x_{1,2,1}, ..., x_{1,4,1}, x_{2,1,1}, x_{2,2,1}, ... $ This is similar to the previous possible enumeration, except we traverse the grid along rows first, then along columns, then along digits.
- Order the variables randomly.

- for each of the $ n^2 $ grid boxes we have a single constraint, totalling $ n^2 $ constraints,
- for each of the n rows, and each of the n digits, we have a constraint, totalling $ n^2 $ constraints,
- for each of the n columns, and each of the n digits, we have a constraint, totalling $ n^2 $ constraints,
- for each of the n subgrids, we have n constraints telling us each digit must appear in that subgrid, totalling $ n^2 $ constraints,
- we start with $ |G| = \# $of rows of G entries already filled in, totalling $ |G| $ constraints.

### Box constraints

### Row constraints

### Column constraints

### Subgrid constraints

### The givens

- intcon, or the variables in x that should be integers. We want all of the components of x to be integers, so this should be the array 1:numVariables,
- numVariables, or the length of the variable x ($ n^3 $ in this case),
- lb, the vector of lower bounds for each of the variables. Since each $ x_{ijk} $ is 0 or 1, lb will be a vector of 0s,
- ub, the vector of upper bounds for each of the variables. Since each $ x_{ijk} $ is 0 or 1, ub will be a vector of 1s.

## Further directions

- What happens if we don't add any givens to the linear program, i.e. we start with an empty Sudoku board? We should end up with a solution - is it unique? How might we interpret this solution? (The solver may take a bit longer to find the solution, but it will find a solution.)
- How might you impose other constraints to transform the Sudoku puzzle into something possibly more difficult? Two options might be: (a) requiring that each diagonal of the Sudoku grid contains each of the digits 1-9 once and only once, and (b) requiring that the middle boxes of each subgrid form their own subgrid requiring each of the digits 1-9 once and only once.
- Pick another variant of Sudoku and implement those constraints, such as if the subgrids are shaped differently.

## Just the code

## Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.