Sudoku mit Computer Vision lösen / Sudoku

Hey Habr! Sollen wir Sudoku spielen?

Sudoku ist ein Spiel, bei dem das Spielfeld ein 9×9-Quadrat ist, das in kleinere Quadrate mit einer Seite von 3 Zellen unterteilt ist. Somit besteht das gesamte Spielfeld aus 81 Zellen. Darin befinden sich bereits zu Beginn des Spiels einige Zahlen (von 1 bis 9), die als Hinweise bezeichnet werden. Der Spieler muss die freien Felder mit Zahlen von 1 bis 9 ausfüllen, sodass in jeder Reihe, in jeder Spalte und in jedem kleinen 3 × 3-Quadrat jede Zahl nur einmal vorkommt.

Wir werden den Lösungsprozess in mehrere Phasen unterteilen:

  1. Sudoku-Grenzerkennung und Feldausrichtung (OpenCV)

  2. Erkennung von Ausgangsdaten (Hints) (EasyOCR)

  3. Problemlösung (PuLP)

  4. Antwort auf Originalbild anzeigen

Um das erste Problem zu lösen, verwenden wir OpenCV.

Öffnen Sie zuerst das Bild und finden Sie alle Konturen darauf. Dazu müssen Sie das Bild in Grautöne umwandeln, eine Unschärfe anwenden (um das Rauschen zu glätten) und mithilfe der adaptiveThreshold-Schwellenwertfunktion nur die Hauptkonturen auf dem Bild belassen:

# Sudoku-Bild öffnen img = cv2.imread(‘example/test.png’) # Konturen im Bild finden grey = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) blurry = cv2.GaussianBlur(gray, (5, 5) , 5) thresh = cv2.adaptiveThreshold(blurry, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY_INV,57,5) cnts,_ = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE) cnts = sorted(cnts, key = cv2.contourArea, reverse=True)

Um ein Sudoku-Quadrat in einem Foto zu finden, nehmen wir an, dass es das größte Quadrat im Bild ist. Dazu nehmen wir mittels Konturnäherung die größte Kontur mit 4 Seiten und sortieren die Koordinaten der Ecken im Uhrzeigersinn:

# Um nach einem Sudoku-Gitter zu suchen, finde das größte Quadrat im Bild location = None for cnt in cnts: approx = cv2.approxPolyDP(cnt, 15, True) if len(approx) == 4: # Sortiere die Ecken im Uhrzeigersinn rect = np.zeros ((4, 2), dtype = “float32”) cutt = ca[:,0]

diag_1 = cutt.sum(axis = 1) rect[0] = geschnitten[np.argmin(diag_1)]
rechtwinkl[2] = geschnitten[np.argmax(diag_1)]

diag_2 = np.diff(Schnitt, Achse = 1) rect[1] = geschnitten[np.argmin(diag_2)]
rechtwinkl[3] = geschnitten[np.argmax(diag_2)]

location = rect break

Als nächstes erstellen wir ein Quadrat und verwenden getPerspectiveTransform und warpPerspective, um unser Sudoku-Quadrat darin einzupassen:

# Erstellen Sie ein 900 x 900 Quadrat Höhe = 900 Breite = 900 pts1 = np.float32 ([location[0]Lage[1]Lage[3]Lage[2]]) pts2 = np.float32([[0, 0], [width, 0], [0, height], [width, height]]) # Passe das Sudoku in unsere quadratische Matrix ein = cv2.getPerspectiveTransform(pts1, pts2) board = cv2.warpPerspective(img, matrix, (width, height))

Jetzt müssen wir die Hinweise erkennen, mit denen uns EasyOCR helfen wird:

# OCR-Modell laden import easyocr reader = easyocr.Reader([‘en’]) # Einen Datenrahmen und eine Liste erstellen, um erkannte Ergebnisse zu schreiben df = pd.DataFrame(index=range(1, 10), column=range(1, 10)) sudoku_map = []

# Achsen zum Zeichnen von Subplots erstellen fig, ax = plt.subplots(9, 9, figsize=(8,8))

Für eine zukünftige Lösung müssen wir den Hinweiswert, seine Zeilen- und Spaltennummer kennen. Da wir das Bild in 900 x 900 konvertiert haben, können wir die Sudoku-Spalten erhalten, indem wir einfach das Bild durch 9 teilen und dann jede Spalte durch 9 teilen, um die Zellen zu erhalten. Übergeben wir dem Modell den Parameter allowlist=’0123456789′, damit es nur Zahlen erkennt:

# Teilen Sie unser Sudoku in 9 Zeilen und 9 Spalten und erkennen Sie jeden Wert split = np.split(board, 9, axis=1) for col,j in enumerate(split): digs = np.split(j, 9) for row ,d in enumerate(digs): # Beschneide 10 Pixel von jeder Seite der Zelle, um Ränder zu entfernen d = d[10:90,10:90]
cv2.copyMakeBorder(d,10,10,10,10,cv2.BORDER_CONSTANT) ax[row][col].imshow(d)ax[row][col].axis(‘off’) # Erkenne die Zahl in der Zelle und schreibe sie in den Datenrahmen und die Liste mit den Koordinaten text = reader.readtext(d, allowlist=”0123456789″, detail=0) if len(text) > 0: df.iloc[row, col] = Texte[0]
sudoku_map.append([text[0]str(row+1), str(col+1)]) df.fillna(”, inplace=True) df

Erkennungsergebnis:

Wie wir sehen können, wurden alle Nummern korrekt erkannt.

Der letzte Schritt besteht darin, das Sudoku zu lösen. Dazu verwenden wir die PuLP-Bibliothek.

PuLP ist eine Python-Bibliothek für lineare Programmierung. In unserem Fall suchen wir den optimalen Wert für jede Zelle ausschließlich auf der Grundlage der Einschränkungen, da es in der Sudoku-Lösung keine Zielfunktion gibt.

Wir erstellen Listen mit Zahlen von 1 bis 9 (mögliche Werte für die Zelle selbst, Spaltennummer und Zeilennummer) und erstellen daraus eine PuLP-Variable LpVariable. In unserem Fall ist dies ein Wertelexikon von 1 bis 9, in dem der Wert je nach Wahrheit der Aussage 0 oder 1 sein kann. Dann deklarieren wir eine Aufgabe mit einer beliebigen Zielfunktion (Minimierung oder Maximierung), statt der Formel setzen wir 0:

# Erstellen Sie Listen, über die in Pulp nums = iteriert werden soll [*map(str, [*range(1,10)])]# Liste mit Zahlen von 1 bis 9 mit Zeichenfolgentyp rows = nums cols = nums vals = nums # Erstellen Sie ein Pulp-Wörterbuch mit möglichen Antwortvariablen choice = LpVariable.dicts(“Choice”, (vals, rows, cols), 0 , 1 , LpInteger) # Erstellen Sie eine Aufgabe für Pulp prob = LpProblem(“Sudoku”, LpMaximize) prob += 0, “Objective function” # Auf Null setzen, da wir nur daran interessiert sind, einen Wert gemäß den Einschränkungen auszuwählen

Wir fügen Einschränkungen bei der Auswahl von Zahlen zum Modell hinzu. Dazu fügen wir in Zyklen Bedingungen hinzu, dass die Summe der Wörterbuchwerte für jede Zahl, Zeile und Spalte gleich 1 ist:

# Schränken Sie die Bedingung ein, dass jede Zahl in jeder Zeile und jeder Spalte nicht mehr als 1 Mal für r, c in product(rows, cols) wiederholt werden darf: prob += lpSum([choices[v][r][c] for v in vals]) == 1, “” for v, r in product(vals, rows): prob += lpSum([choices[v][r][c] for c in cols]) == 1, “” for v, c in product(vals, cols): prob += lpSum([choices[v][r][c] for r in rows]) == 1, “” # Setze ähnliche Beschränkungen für kleine 3×3 Quadrate grid = (range(3), range(3)) subs = [[(rows[3*i+k],Spalte[3*j+l]) für k,l in product(*grid)]für i,j in product(*grid)]für v,s in product(vals, subs): prob += lpSum([choices[v][r][c] für (r, c) in s]) == 1, “”

Wir fügen Hinweise aus der zuvor erstellten Liste mit erkannten Werten hinzu. Setzen Sie in der angegebenen Zeile und Spalte den Hinweiswert auf 1 (setzen Sie beispielsweise für 1 Zeile und 2 Spalten den Wert 7 auf true):

# Fügen Sie der Aufgabe bekannte, von OCR erkannte Werte für num in sudoku_map hinzu: prob += choice[num[0]][num[1]][num[2]]== 1, “”

Damit ist die Vorbereitung des Modells abgeschlossen und für die Lösung brauchen wir nur noch eine Zeile hinzuzufügen:

# Lösen Sie das Problem prob.solve()

Das Modell optimiert die Zellenwerte im Sudoku nach den gesetzten Grenzen, es bleibt nur noch das Ergebnis zu sehen!

# Zeichne das Endergebnis fig, ax = plt.subplots(1,2, figsize=(15,15)) für a in ax: a.axis(‘off’) a.imshow(board) ax[0].set_title(‘Aufgabe’, Schriftgröße=25) axt[1].set_title(‘Decision’, fontsize=25) # Lösung über Bild schreiben y = 50 für r in Zeilen: x = 50 für c,v in product(cols, vals): if choice[v][r][c].value() == 1: wenn [v,r,c] not in sudoku_map: # Nur übereinstimmende Axtwerte schreiben[1].text(x,y,v, ha=”center”, va=”center”, fontsize=25, color=”tab:green”) x += 100 y += 100

Abschließend möchte ich sagen, dass im Rahmen des Beitrags nur eine der Lösungen betrachtet wurde. Die Zeichenerkennung kann mit einer CUDA-fähigen GPU beschleunigt werden, da EasyOCR auf PyTorch basiert, oder Sie können Ihr eigenes Modell trainieren. Der Substitutionsalgorithmus kann ohne die Hilfe von PuLP implementiert werden, aber im Rahmen des Beitrags wollte ich genau den ungewöhnlichen Weg zeigen, diese Bibliothek für die lineare Programmierung zu verwenden.

Den vollständigen Code finden Sie in Lagerstätten

Similar Posts

Leave a Reply

Your email address will not be published.