Lösen Sie die Anzahl der Deutschen mit einer Tiefenprioritätssuche. Die Priorität der Programmerstellung ist
Ich habe es in der Reihenfolge von gemacht. Ich opfere Geschwindigkeit.
Es wird durch ein allgemeines zweidimensionales Array dargestellt.
def values_from_grid(grid):
"Erstellen Sie zweidimensionale Array-Werte aus Text"
values = []
digits = "123456789"
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
grid_int = map(lambda x: int(x) if x != "." else 0, chars)
count = 0
row = []
for i in grid_int:
row.append(i)
count += 1
if count % 9 == 0: #Zeile für Zeile teilen
values.append(row)
row = []
return values
Eine Funktion, die Text liest und in ein zweidimensionales Array konvertiert. Das Textformat ist ein Leerzeichen, das durch 0 oder 0 ausgedrückt wird. Andere Zahlen werden der Reihe nach registriert. Wenn es 81 Zeichen sind, ist es OK. Es entspricht den folgenden Textformaten.
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
Überprüfen Sie rekursiv mit Tiefenprioritätssuche. Wie rufe ich an?
values = values_from_grid(Höchste Daten)
solver(values)
ist. Übergeben Sie Werte an die Solver-Funktion. Nach dem Lösen sind Werte eine Reihe von Antworten.
Wenden Sie von der oberen linken Zelle zur unteren rechten Zelle die Zahlen 1 bis 9 nacheinander an. Zu diesem Zeitpunkt wird die Nummer nur angewendet, wenn sich die anzuwendende Nummer nicht im Quadrat "vertikal / horizontal / 3x3" befindet. x ist die horizontale Achse und y ist die vertikale Achse. Wenn x 8 erreicht, dh wenn es das Ende der horizontalen Achse erreicht Überprüfen Sie die erste Zelle in der unteren Reihe mit der vertikalen Achse nach unten und der horizontalen Achse auf 0. Wenn die letzte Zelle erreicht ist, wurde das Problem behoben und True wird zurückgegeben.
def solver(values, x=0, y=0):
"Löse die Nummer"
if y > 8: #Schließen Sie ab, wenn der Zeiger das Ende erreicht hat
return True
elif values[y][x] != 0: #Wenn es nicht leer ist, überspringen Sie es
if x == 8: #Fahren Sie mit der nächsten Zeile fort, nachdem Sie 8 Spalten erreicht haben
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
else:
for i in range(1, 10):#Probieren Sie alle Zahlen von 1 bis 9 aus
if check(values, x, y, i): #Überprüfen
values[y][x] = i #Wenn OK, geben Sie eine Nummer ein
if x == 8: #Fahren Sie mit der nächsten Zeile fort, nachdem Sie 8 Spalten erreicht haben
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
values[y][x] = 0 #Kehren Sie bei der Rückkehr zu 0 zurück
return False
Der Rückgabewert ist "True" oder "False". Wenn Sie es lösen können, ist es "wahr".
Überprüfen Sie den Bereich der horizontalen Achse, der vertikalen Achse und 3 * 3. Eine Funktion, die jede Funktion aufruft.
def check(values, x, y, i):
if row(values, y, i) and column(values, x, i) and block(values, x, y, i):
return True
return False
Nimmt den Wert der vertikalen Achse, der die aktuelle Zeile angibt, als Argument, um die horizontale Achse zu überprüfen. Ich bin die Nummer, die Sie eingeben möchten. Überprüfen Sie die horizontale Achse nacheinander, wenn sie mit der Zahl übereinstimmt, die Sie eingeben möchten. Wenn nicht, ist sie falsch Erstellen Sie eine Liste von True und überprüfen Sie sie mit der Funktion all. Wenn alle True sind, wird True ohne doppelte Zahlen zurückgegeben. Wenn es nur ein Duplikat gibt, wird False zurückgegeben.
def row(values, y, i):
"Überprüfen Sie die Seite"
return all(True if i != values[y][_x] else False for _x in range(9))
Ich habe gerade die Prüfung auf der horizontalen Achse in die vertikale Achse geändert.
def column(values, x, i):
"Vertikal prüfen"
return all(True if i != values[_y][x] else False for _y in range(9))
Die folgende Funktion wurde unter Bezugnahme auf Implementieren eines deutschen Lösers in Python erstellt. Wenn Sie die Zahl von 0 auf 8 durch 3 teilen und den Wert mit den mit 3 entfernten Brüchen multiplizieren, erhalten Sie 0, 3 bzw. 6. Die Theorie ist, dass Sie den Block sehen können, zu dem das Quadrat gehört.
def block(values, x, y, i):
"Überprüfen Sie 3x3 Blöcke"
xbase = (x // 3) * 3
ybase = (y // 3) * 3
return all(True if i != values[_y][_x] else False
for _y in range(ybase, ybase + 3)
for _x in range(xbase, xbase + 3))
Problem
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
Antworten
[8, 5, 9, 6, 1, 2, 4, 3, 7]
[7, 2, 3, 8, 5, 4, 1, 6, 9]
[1, 6, 4, 3, 7, 9, 5, 2, 8]
[9, 8, 6, 1, 4, 7, 3, 5, 2]
[3, 7, 5, 2, 6, 8, 9, 1, 4]
[2, 4, 1, 5, 9, 3, 7, 8, 6]
[4, 3, 2, 9, 8, 1, 6, 7, 5]
[6, 1, 7, 4, 2, 5, 8, 9, 3]
[5, 9, 8, 7, 3, 6, 2, 4, 1]
Dieses Programm hat in meiner Umgebung ungefähr 23 Sekunden gedauert, um dieses Rätsel zu lösen. Das Programm in Löse jedes Sudoku-Rätsel löst es in 0,01 Sekunden. Dies ist Löse alle deutschen Rätsel und sagt: "Wenn Sie eine Zelle füllen, die einen möglichen Wert bestimmen kann, tun die anderen Zellen dasselbe. Dies liegt daran, dass die Strategie des "Ausfüllens" ausgeführt wird und die noch nicht ausgefüllten Quadrate nur nach den Werten durchsucht werden, die für jedes Quadrat verwendet werden können, um eine Lösung zu finden. Dieses Programm prüft von 1 bis 8, auch wenn es nur 9 Quadrate enthält. Wenn Sie vertikale, horizontale und 3x3-Quadrate prüfen, treten überlappende Quadrate auf, die jedoch auch einzeln geprüft werden. tun. Es ist also langsam.
Löse alle deutschen Rätsel Implementierte einen deutschen Löser in Python
Recommended Posts