Pourquoi sais-tu

PuLP, une bibliothèque de programmation linéaire pour Python introduite la dernière fois http://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17 Donc, je peux résoudre le nombre, alors je vais essayer de le résoudre.

PyConJP Talk Comment résoudre des énigmes par optimisation mathématique https://pycon.jp/2014/schedule/presentation/23/ Et documentation https://pythonhosted.org/PuLP/CaseStudies/a_sudoku_problem.html Depuis qu'il est écrit, je l'ai essayé moi-même. L'histoire.

Qu'est-ce qu'un nombre?

Un jeu de puzzle qui remplit les nombres de 1 à 9 en fonction de contraintes.

Ce sont des contraintes

Le même numéro ne vient pas sur une ligne horizontale
Le même numéro ne vient pas dans une rangée verticale
Le même numéro ne vient pas dans un bloc 3x3

Exemple de document Sugoku

Si vous résolvez cela, Solution numérique Ce sera comme ça. Donc, si ça sort, c'est OK

Convertir les mathématiques en un problème de planification linéaire

Ce qu'on appelle la modélisation. C'est la clé de ce genre de problème et j'ai été très impressionné.

Tout d'abord, créez un objet problème avec PuLP

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

Il n'y a pas de fonction objectif particulière, définissez donc une constante telle que 0.

Conception variable

L'idée clé est d'utiliser un grand nombre de variables binaires qui ne prennent que la valeur ** 0 ou 1 **.

Plus précisément, il existe 9 types, 9 carrés horizontaux, 9 carrés verticaux et 1 à 9 valeurs. 9 x 9 x 9 = 729 variables, Variable Cell_v_x_y = 1 lorsque le nombre de cellules dans les positions horizontale x et verticale y est v Sinon, définissez Cell_v_x_y = 0.

En d'autres termes, préparez 9 variables pour chaque cellule, Un seul d'entre eux vaut 1 et les 8 autres valent 0.

Le code pour générer les variables est ci-dessous

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

Cela générera 729 variables pour Cell_1_1_1, ..., Cell_9_9_9, Vous pouvez maintenant y accéder comme choix [1] [1] [1]. La variable est un entier et peut prendre une valeur de 0 ou 1.

Concevoir des contraintes à partir des règles du jeu

Une seule valeur peut tenir dans une cellule

Par exemple, un seul de 1-9 est dans le carré à la coordonnée (2, 3), Cela devient une telle 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

Si vous écrivez dans le code

ys = range(1, 10)
xs = range(1, 10)
numbers = range(1, 10)
for y in ys: #Avec chaque colonne
    for x in xs: #Pour chaque ligne
        prob += pulp.lpSum([choices[v][x][y] for v in numbers]) == 1 
        #Additionnez tous les nombres pour obtenir 1.

Ici, «lpSum» représente une expression obtenue en ajoutant toutes les variables du tableau. Il est souvent utilisé car il est simple pour exprimer le total.

Chaque fois qu'un nombre est déjà rempli, seul ce nombre entre dans le carré.

board [y] [x] contient le nombre de carrés déjà remplis, S'il est vide, il contient 0.

for x in range(width): #Avec chaque colonne
    for y in range(height): #Examinez chaque colonne,
        if board[y][x] > 0: #Si le nombre est supérieur à 0
            prob += choices[board[y][x]][x+1][y+1] == 1
            #Ajoutez une contrainte pour que le nombre à cet emplacement soit 1.

Nous avons déjà mis dans la contrainte qu'une seule valeur peut être 1 dans la même cellule, donc Vous n'avez qu'à penser au moment où la valeur est 1.

Le même numéro ne peut pas être entré dans la même colonne / ligne / case

Contraintes de ligne

Exemple: dans la première colonne (y), le nombre (v) est 1 dans une seule de toutes les lignes. En d'autres termes, si vous les additionnez tous, ce sera toujours 1. Lorsque v = 1 et y = 1 dans la variable Cell_v_x_y, les restrictions suivantes se produisent.

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

Colonnes et cases omises.

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

Le résultat de l'exécution ressemble à ceci, et il a été résolu.

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

Résoudre des maths avec PuLP