Why sudoku

The Python linear programming library PuLP introduced last time http://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17 So, I can solve Sudoku, so I will try to solve it.

PyConJP Talk How to solve puzzles by mathematical optimization https://pycon.jp/2014/schedule/presentation/23/ And documentation https://pythonhosted.org/PuLP/CaseStudies/a_sudoku_problem.html Since it is written in, I tried it myself. The story.

What is Sudoku?

A puzzle game that fills numbers from 1-9 based on constraints.

These are constraints

The same number does not come in a horizontal row
The same number does not come in a vertical row
The same number does not come in a 3x3 block

Document example Sudoku

If you solve this, Sudoku It will be like this. So, if this comes out, it's OK

Convert Sudoku into a Linear Programming Problem

So-called modeling. This is the key to this kind of problem, and I was quite impressed.

First, create a problem object with PuLP

import pulp
prob = pulp.LpProblem('Sudoku', pulp.LpMinimize)
prob += 0 # No objective function

There is no particular objective function, so set a constant such as 0.

Variable design

The key idea is to use a lot of binary variables that only take the value ** 0 or 1 **.

Specifically, there are 9 types, 9 squares in width, 9 squares in height, and 1-9 values. 9 x 9 x 9 = 729 variables, Variable Cell_v_x_y = 1 when the number of cells in the horizontal x and vertical y positions is v Otherwise, set Cell_v_x_y = 0.

In other words, prepare 9 variables for each cell, Only one of them is 1 and the other 8 are 0.

The code to generate the variables is below

numbers = range(1, 10)
xs = range(1, 10)
ys = range(1, 10)
choices = pulp.LpVariable.dicts("Cell",(xs, ys, numbers),0,1,pulp.LpInteger)

This will generate 729 variables for Cell_1_1_1, ..., Cell_9_9_9, You can now access it like choices [1] [1] [1]. The variable is an integer and can take a value of 0 or 1.

Designing constraints from game rules

Only one value can fit in a cell

For example, only one of 1-9 is in the square at coordinates (2, 3), so It becomes such an expression.

Cell_1_2_3 + Cell_2_2_3 + Cell_3_2_3 +
Cell_4_2_3 + Cell_5_2_3 + Cell_6_2_3 +
Cell_7_2_3 + Cell_8_2_3 + Cell_9_2_3 = 1

When written in code

ys = range(1, 10)
xs = range(1, 10)
numbers = range(1, 10)
for y in ys: #With each column
    for x in xs: #For each line
        prob += pulp.lpSum([choices[v][x][y] for v in numbers]) == 1 
        #Add all the numbers to get 1.

Here, lpSum represents an expression obtained by adding all the variables of the array. It is often used because it is simple when expressing the sum.

Whenever a number is already filled, only that number enters the square.

board [y] [x] contains the numbers of the cells that have already been filled. If it is empty, it contains 0.

for x in range(width): #With each column
    for y in range(height): #Examine each column,
        if board[y][x] > 0: #If the number is greater than 0
            prob += choices[board[y][x]][x+1][y+1] == 1
            #Add a constraint so that the number at that location is 1.

We've already put in the constraint that only one value can be 1 in the same cell, so You only have to think about when the value is 1.

The same number cannot be entered in the same column / row / box

Row constraints

Example: In the first column (y), the number (v) is 1 in only one of all rows. In other words, if you add them all up, it will always be 1. When v = 1 and y = 1 in the variable of Cell_v_x_y, the following restrictions occur.

Cell_1_1_1 + Cell_1_2_1 + Cell_1_3_1 + 
Cell_1_4_1 + Cell_1_5_1 + Cell_1_6_1 + 
Cell_1_7_1 + Cell_1_8_1 + Cell_1_9_1  = 1

for v in numbers:
    for y in ys:
        prob += pulp.lpSum([choices[v][x][y] for x in xs]) == 1

Columns and boxes omitted.

code

import pulp
import numpy

# make problem
board = """
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079"""

# board = map(lambda line: map(int, line.rstrip()), open("sudoku.txt").readlines())
board = [map(int, list(line)) for line in board.strip().split("\n")]
print board
width = len(board[0])
height = len(board)


## initialize
# Create a problem
prob = pulp.LpProblem('Sudoku', pulp.LpMinimize) # or minimize

## objective
# No objective function
prob += 0

# make 
numbers = range(1, 10)
xs = range(1, 10)
ys = range(1, 10)
choices = pulp.LpVariable.dicts("Choice",(xs, ys, numbers),0,1,pulp.LpInteger)


## constraints
# Add given-value constraints
for x in range(width):
    for y in range(height):
        if board[y][x] > 0:
            prob += choices[board[y][x]][x+1][y+1] == 1

# one cell must have one value
for y in ys:
    for x in xs:
        prob += pulp.lpSum([choices[v][x][y] for v in numbers]) == 1, ""

# horizontal line must have different values
for v in numbers:
    for y in ys:
        prob += pulp.lpSum([choices[v][x][y] for x in xs]) == 1

    for x in xs:
        prob += pulp.lpSum([choices[v][x][y] for y in ys]) == 1

    for x in [1, 4, 7]:
        vs = []
        for y in [1, 4, 7]:
            print [[choices[v][x+i][y+j] for i in range(3) for j in range(3)]]
            prob += pulp.lpSum([[choices[v][x+i][y+j] for i in range(3) for j in range(3)]]) == 1


# print prob

s = prob.solve()
# solve it

print pulp.LpStatus[s]

# print result
for y in ys:
    for x in xs:
        for v in numbers:
            if choices[v][x][y].value() == 1:
                print v,
    print

The execution result looks like this, and it was solved.

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

Solve Sudoku with PuLP