Sudoku

Skip to main content

Section 9.2 Sudoku

In this section, we explore a curious application of linear programming. Solving sudokus!

Exploration 9.2.1.

Consider the following sudoku puzzle:

$A sudoku puzzle.$

Note that the rules for sudoku are that we fill in each entry with an integer

1, \dots, 9

so that:

Each row contains exactly one of each number.
Each column contains exactly one of each number.
Each $3 \times 3$ “block” contains exactly one of each number.

(a)

Solve the above sudoku if you feel like it.

Remark 9.2.2.

We consider the standard sudokus like the one above an order sudoku: we have

3 \times 3

“blocks”, each with

3 \times 3

entries. Potential values range from

1

through

3^{2} .

Other orders are also possible.

More sudokus may be found at https://www.websudoku.com/

¹

www.websudoku.com/

Activity 9.2.3.

Consider a general order

3

sudoku puzzle. We want to define a linear maximization problem that solves a given puzzle. Let

x_{i j k} = 1

is a solution has value

k

in entry

i, j

(measured from the bottom left), and

x_{i j k} = 0

otherwise.

(a)

For the

i, j

th entry, write a linear equality constraint which ensures a value is chosen.

(b)

For row

i,

write 9 equality conditions so that this row contains one of each entry.

(c)

For column

j,

write 9 equality conditions so that this column contains one of each entry.

(d)

For an arbitrary block, write 9 equality conditions so that this block contains one of each entry.

(e)

Now consider the sudoku puzzle from Exploration 9.2.1. How could we write out appropriate equality conditions fixing each entry?

(f)

Are there any other constraints we need?

(g)

What should the objective function be? (Does it matter?)

Obviously, this would be an absolutely absurdly large problem to even fully write out, much less solve. We consider something simpler.

Activity 9.2.4.

Consider the following order 2 sudoku puzzle:

$An order 2 sudoku puzzle.$

(a)

Following Activity 9.2.3, write out the linear optimization problem which would compute the solved puzzle.

(b)

If you really want to, solve this problem (there are 64 decision variables so...):

xxxxxxxxxx
 
%display typeset
A = (FIXME)
b = (FIXME)
c = (FIXME)
P = InteractiveLPProblem(A, b, c,
 [FIXME], 
 constraint_type = [FIXME],
 variable_type = "",
 problem_type = FIXME)
P

xxxxxxxxxx
 
print(P.optimal_solution())
print(P.optimal_value())

This provides an oppourtunity for an enteprising student to engage in some further exploration.

Project 9.2.5.

Write effecient code in Sage where one inputs a

9 \times 9

matrix representing a sudoku puzzle (with maybe 0’s for blank entries), and the code produces the appropriate linear optimization problem and solves it.

For more advanced or experienced coders, generalize this to allow the order of the sudoku puzzle to be a parameter.