[PYTHON] Solve Sudoku with PuLP

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

  1. The same number does not come in a horizontal row
  2. The same number does not come in a vertical row
  3. 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

Recommended Posts

Solve Sudoku with PuLP
Solve Sudoku with Python
Solve AtCoder 167 with python
Linear Programming with PuLP
Solve POJ 2386 with python
[Python] Solve equations with sympy
Solve AtCoder ABC166 with python
Combine Sudoku and solve optimally
I want to solve Sudoku (Sudoku)
Solving Sudoku with Python (Part 2)
Solve AtCoder ABC 186 with Python
solver> Link> Solve Excel Solver with python
Solve ABC163 A ~ C with Python
Solve OpenAI Gym Copy-v0 with Q-learning
Solve ABC166 A ~ D with Python
Solve your own maze with Q-learning
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solve ABC168 A ~ C with Python
Getting started on how to solve linear programming problems with PuLP
Solve three-dimensional PDEs with deep learning.
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve OpenAI Gym Copy-v0 with Sarsa
Solve ABC158 A ~ C with Python
Solve your own maze with DQN
I wanted to solve ABC160 with Python
I tried to let optuna solve Sudoku
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Solve the traveling salesman problem with OR-Tools
I tried to solve TSP with QAOA
AtCoder Green tried to solve with Go
Solve Lake Counting (POJ NO.2386) with Python3
I wanted to solve ABC172 with Python