Warum weißt du das?

PuLP, eine lineare Programmierbibliothek für Python, die zuletzt eingeführt wurde http://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17 Also kann ich die Zahl lösen, also werde ich versuchen, sie zu lösen.

PyConJP Talk So lösen Sie Rätsel durch mathematische Optimierung https://pycon.jp/2014/schedule/presentation/23/ Und Dokumentation https://pythonhosted.org/PuLP/CaseStudies/a_sudoku_problem.html Da es geschrieben steht, habe ich es selbst versucht. Die Geschichte.

Was ist eine Nummer?

Ein Puzzlespiel, das Zahlen von 1 bis 9 basierend auf Einschränkungen füllt.

Dies sind Einschränkungen

Die gleiche Nummer kommt nicht in einer horizontalen Reihe
Die gleiche Nummer kommt nicht in einer vertikalen Reihe
Die gleiche Nummer kommt nicht in einem 3x3-Block

Dokumentbeispiel Sugoku

Wenn Sie dies lösen, Numerische Lösung Es wird so sein. Wenn dies herauskommt, ist es in Ordnung

Umwandlung von Mathematik in ein lineares Planungsproblem

Sogenannte Modellierung. Dies ist der Schlüssel zu dieser Art von Problem, und ich war ziemlich beeindruckt.

Erstellen Sie zunächst ein Problemobjekt mit PuLP

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

Es gibt keine bestimmte Zielfunktion, setzen Sie also eine Konstante wie 0.

Variables Design

Die Schlüsselidee besteht darin, viele binäre Variablen zu verwenden, die nur den Wert ** 0 oder 1 ** annehmen.

Insbesondere gibt es 9 Typen, 9 horizontale Quadrate, 9 vertikale Quadrate und 1-9 Werte. 9 x 9 x 9 = 729 Variablen, Variable Cell_v_x_y = 1, wenn die Anzahl der Zellen in den horizontalen x- und vertikalen y-Positionen v ist Andernfalls setzen Sie "Cell_v_x_y = 0".

Mit anderen Worten, bereiten Sie 9 Variablen für jede Zelle vor. Nur einer von ihnen ist 1 und die anderen 8 sind 0.

Der Code zum Generieren der Variablen ist unten

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

Dadurch werden 729 Variablen für Cell_1_1_1, ..., Cell_9_9_9, generiert. Sie können jetzt wie "Auswahl [1] [1] [1]" darauf zugreifen. Die Variable ist eine Ganzzahl und kann den Wert 0 oder 1 annehmen.

Designbeschränkungen aufgrund von Spielregeln

In eine Zelle kann nur ein Wert passen

Zum Beispiel befindet sich nur eines von 1-9 im Quadrat an der Koordinate (2, 3). Es wird so ein Ausdruck.

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

Wenn Sie in Code schreiben

ys = range(1, 10)
xs = range(1, 10)
numbers = range(1, 10)
for y in ys: #Mit jeder Spalte
    for x in xs: #Für jede Zeile
        prob += pulp.lpSum([choices[v][x][y] for v in numbers]) == 1 
        #Addiere alle Zahlen, um 1 zu erhalten.

Hier stellt lpSum einen Ausdruck dar, der durch Hinzufügen aller Variablen des Arrays erhalten wird. Es wird oft verwendet, weil es einfach ist, die Summe auszudrücken.

Immer wenn eine Zahl bereits gefüllt ist, betritt nur diese Zahl das Quadrat.

board [y] [x] enthält die Anzahl der bereits ausgefüllten Quadrate, Wenn es leer ist, enthält es 0.

for x in range(width): #Mit jeder Spalte
    for y in range(height): #Untersuche jede Spalte,
        if board[y][x] > 0: #Wenn die Zahl größer als 0 ist
            prob += choices[board[y][x]][x+1][y+1] == 1
            #Fügen Sie eine Einschränkung hinzu, sodass die Nummer an dieser Stelle 1 ist.

Wir haben bereits die Einschränkung eingeführt, dass nur ein Wert in derselben Zelle 1 sein kann Sie müssen nur darüber nachdenken, wann der Wert 1 ist.

Dieselbe Nummer kann nicht in dieselbe Spalte / Zeile / Box eingegeben werden

Zeilenbeschränkungen

Beispiel: In der ersten Spalte (y) ist die Zahl (v) in nur einer aller Zeilen 1. Mit anderen Worten, wenn Sie alle addieren, ist es immer 1. Wenn v = 1 und y = 1 in der Variablen "Cell_v_x_y" sind, treten die folgenden Einschränkungen auf.

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

Spalten und Kästchen weggelassen.

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

Das Ausführungsergebnis sieht folgendermaßen aus und wurde gelöst.

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

[PYTHON] Löse Mathe mit PuLP