[PYTHON] Versuchen Sie, Sudoku mit explosiver Geschwindigkeit mit Numpy zu lösen
Was ist Sudoku?
Sudoku ist eines der Bleistiftpuzzles, bei dem Zahlen von 1 bis 9 in einen quadratischen 9x9-Rahmen eingefügt werden, der in 3x3-Blöcke unterteilt ist. Auch als "Number Place (Nampure)" bezeichnet. (Aus Wikipedia)
Es scheint.
Natürlich füllt es die Zahlen nicht ohne nachzudenken aus und es gibt die folgenden Einschränkungen.
- Die gleiche Nummer darf nicht in einer Spalte vorhanden sein
- Die gleiche Nummer darf nicht in einer Zeile stehen
- Die gleiche Nummer darf nicht in einem Block vorhanden sein
(Ich habe es von einer Website ausgeliehen, die interessante und nützliche Dinge in der Mathematik zusammenfasst)
Ich wollte dies zu einem Problem für Junioren machen, die neu in der Programmierung sind, aber ich werde es schreiben, weil es nur wenige Artikel gab, die unerwartet geschrieben wurden.
Politik
Nun, es macht einfach das Gleiche wie ein Mensch.
Betrachten Sie die folgende Nummer.
Wenn Sie beispielsweise nach 1 suchen, finden Sie ** eine Stelle, an der nur 1 in jede Spalte, Zeile und jeden Block passen kann **.
Wir setzen ein Flag, dass jede Nummer für jede Zelle existiert, und codieren die Arbeit des Findens von Spalten, Zeilen und Blöcken, für die die Gesamtzahl der Flags 1 beträgt.
Für jedes Quadrat gibt es eine bestimmte Nummer
- Masse, die existieren kann ... 1
- Eine Masse, die möglicherweise nicht existiert ... 0
Im oben genannten Obersten Deutschland kann das Existenzflag wie folgt auf "1" gesetzt werden. (Im Folgenden wird ein zweidimensionales Array, das diesen Regeln folgt, als Ebene bezeichnet.) Unten ist ein Bild. (Rote und Zahlenquadrate ... 0, grün ... 1)
Berechnen Sie dann die Summe für jede Zeile, jede Spalte, jeden Block. Wenn die Summe 1 wird, wird die Nummer bestätigt **.
In diesem Beispiel finden Sie genau drei Stellen zum Aktualisieren. 
Auf diese Weise scheint es einfach zu lösen, wenn nur das Existenzflag eingeführt wird.
Lassen Sie uns nun den Code schreiben.
Überprüfen Sie jede Zeile
def check_row(layer):
rows = np.where(np.sum(layer, axis=1)==1)[0]
w = np.where(layer[rows] == 1)
cols = w[1][np.argsort(w[0])]
return rows, cols
Auf diese Weise werden im Grunde genommen np.sum und np.where verwendet, um die Zellen zu extrahieren, die die Bedingungen erfüllen.
Überprüfen Sie jede Spalte
Gleiches gilt für Spalten.
def check_col(layer):
cols = np.where(np.sum(layer, axis=0)==1)[0]
w = np.where(layer[:,cols] == 1)
rows = w[0][np.argsort(w[1])]
return rows, cols
Überprüfen Sie jedes Raster
def check_grid(layer):
rows, cols = list(), list()
for row in range(3):
for col in range(3):
grid = self.layer[row*3:(row+1)*3, col*3:(col+1)*3 ]
if np.sum(grid) == 1:
point = np.where(grid==1)
rows.append(point[0][0]+row*3)
cols.append(point[1][0]+col*3)
return rows, cols
Funktionsprüfung
Lassen Sie uns nun die Funktionen bis zu diesem Punkt ausprobieren.
layer = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 1, 0, 1]])
print(check_row(layer))
#(array([3], dtype=int64), array([5], dtype=int64))
print(check_col(layer))
#(array([8], dtype=int64), array([6], dtype=int64))
print(check_grid(layer))
#([4], [8])
Es funktioniert gut.
Überprüfen Sie jede Schicht
Nun, es funktioniert tatsächlich, aber da es eine große Sache ist, werde ich eine weitere Funktion hinzufügen.
Bisher haben wir uns nur auf eine Ebene konzentriert. Da Sugoku jedoch aus neun Zahlen von 1 bis 9 besteht, sollten Sie auch einen Vergleich der Ebenen in Betracht ziehen. Mit anderen Worten, ** in jeder Zelle kann der Ort bestimmt werden, wenn das Existenzflag für jede Schicht in nur einer Schicht gesetzt ist **.
def check_all_layer(layers):
nums = list()
sum_map = np.sum(layers, axis=0)
if np.any(sum_map==1):
rows, cols = np.where(sum_map==1)
for row, col in zip(rows, cols):
idx = np.where(layers[:,row,col])[0][0]
nums.append(idx+1)
return rows, cols, nums
layers = np.zeros((9,9,9))
layers[3,5,7] = 1
print(check_all_layer(layers))
#(array([5], dtype=int64), array([7], dtype=int64), [4])
Update, wenn eine Nummer vergeben ist
Wenn die Zahlen festgelegt sind, müssen auch die Ebenen aktualisiert werden. Unter Berücksichtigung einer 9x9x9 3D-Array-Ebene kann die Funktion zum Aktualisieren der Ebene wie folgt geschrieben werden:
def update(layers, idx, row, col):
layers[idx,row, : ] = 0 #Zeilenrichtung
layers[idx, : ,col] = 0 #Spaltenrichtung
layers[ : ,row,col] = 0 #Ebenenrichtung
row, col = row//3*3, col//3*3
layers[idx, row:row+3, col:col+3] = 0 #Reichweite
Schließlich
Ich habe es überhaupt nicht überprüft, weil es nur ein kleiner Code ist, den ich geschrieben habe, als ich aufgeregt war, mit meinen Senioren zu sprechen () Wenn Sie Fehler haben, kontaktieren Sie mich bitte.
Vielen Dank für das Lesen bis zum Ende.
Tatsächlicher Code
Da es in einer Klasse implementiert wurde, unterscheidet es sich geringfügig vom obigen Code, aber dies löst die Zahl in etwa 0,01 Sekunden.
Ich habe es in Kleber geschrieben, daher habe ich die Operation überhaupt nicht bestätigt, aber es funktioniert wahrscheinlich.
sudoku.py
class sudoku_solver(object):
def __init__(self, question):
self.p = np.array(problem)
self.layer = np.ones((9,9,9))
self.__init_layer()
self.update_list = list()
def solve(self):
count=0
while np.sum(self.layer)!=0 or count<100:
for i in range(9):
self.check_row(i)
self.check_col(i)
self.check_grid(i)
self.check_all_layer()
self.__update()
count+=1
#Update-Funktion
def __update(self):
for idx, row, col in self.update_points:
self.__update_point(idx, row, col)
self.update_points=list()
def __update_point(self, idx, row, col):
#Antwort Update
self.p[row, col] = idx+1
#Ebenenaktualisierung
self.layer[idx,row, : ] = 0 #Zeilenrichtung
self.layer[idx, : ,col] = 0 #Spaltenrichtung
self.layer[ : ,row,col] = 0 #Ebenenrichtung
row, col = row//3*3, col//3*3
self.layer[idx, row:row+3, col:col+3] = 0 #Reichweite
#Schichtinitialisierungsfunktion
def __init_layer(self):
for idx in range(9):
(rows, cols) = np.where(self.p==idx+1)
for row, col in zip(rows, cols):
self.__update_point(idx, row, col)
#Zeilenbestätigungsfunktion
def check_row(self, idx):
rows = np.where(np.sum(self.layer[idx], axis=1)==1)[0]
w = np.where(self.layer[idx][rows] == 1)
cols = w[1][np.argsort(w[0])]
for row, col in zip(rows, cols):
self.update_list.append((idx, row, col))
#Spaltenbestätigungsfunktion
def check_col(self, idx):
cols = np.where(np.sum(self.layer[idx], axis=0)==1)[0]
w = np.where(self.layer[idx][:,cols] == 1)
rows = w[0][np.argsort(w[1])]
for row, col in zip(rows, cols):
self.update_list.append((idx, row, col))
#Bereichsbestätigungsfunktion
def check_grid(self, idx):
for row in range(3):
for col in range(3):
grid = self.layer[idx, row*3:(row+1)*3, col*3:(col+1)*3 ]
if np.sum(grid) == 1:
point = np.where(grid==1)
row = point[0][0]+row*3
col = point[1][0]+col*3
self.update_list.append((idx,row,col))
#Funktion zur Bestätigung der Ebenenrichtung
def check_all_layer(self):
sum_map = np.sum(self.layer, axis=0)
if np.any(sum_map==1):
rows, cols = np.where(sum_map==1)
for row, col in zip(rows, cols):
idx = np.where(self.layer[:,row,col])[0][0]
self.update_list.append((idx,row,col))