Sudoku-Löser Python

1. Verwenden Sie den Backtracking-Algorithmus in Python, um Sudoku zu lösen
2. Abschluss

Sudoku ist ein auf Logik basierendes Zahlenpuzzlespiel, das vor allem bei Menschen beliebt ist, die in Logik und Argumentation verliebt sind. Das Lösen von Sudoku-Rätseln hilft dem Gehirn, die Konzentration und das logische Denken zu verbessern.

Dieser Artikel beschreibt, wie wir Sudoku mit Python lösen können.

Verwenden Sie den Backtracking-Algorithmus in Python, um Sudoku zu lösen

Bei der Suche nach Lösungen für Rechenprobleme verwenden wir häufig den Backtracking-Algorithmus. Beim Lösen von Sudoku prüft es, ob die Ziffern der ausgefüllten Kästchen gültig sind oder nicht.

Wenn es nicht gültig ist, überprüft es andere Zahlen von 1 bis 9. Wenn es keine gültige Ziffer findet, kehrt es zur vorherigen Option zurück.

Wenn wir eine Sackgasse erreichen und zur vorherigen Wahl zurückkehren, haben wir unsere Wahl getroffen und werden sie ändern, was zu einer anderen möglichen Lösung führt.

Nehmen wir den Ansatz, den Sudoku-Löser zusammen mit dem Backtracking-Algorithmus zu implementieren.

Zuerst müssen wir das Brett aufbauen, indem wir das Puzzle bilden.

def setBoardFunc(puz):
    global grid
    print("\n---------------Sudoku Solver---------------\n")
    print("Here is the Sudoku Problem :")
    for i in range(0, len(puz), 9):
        row = puz[i : i + 9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()

Hier habe ich eine Funktion namens setBoardFunc() definiert, um das Puzzle zu bilden. Während der Schleife setzt es ein 9x9-Puzzle und initialisiert die leeren Zellen mit 0.

Nach Abschluss der Operationen der Funktionen druckt es die im puz gegebenen Eingaben aus. Dann müssen wir das Raster drucken; Dieser Schritt druckt das 9x9-Raster mit den gegebenen Eingaben aus.

def printGridFunc():
    global grid
    for row in grid:
        print(row)

Als nächstes werden wir prüfen, ob der aktuelle Wert innerhalb des aktuellen Felds platziert werden kann.

def checkValidFunc(row, column, num):
    global grid
    for i in range(0, 9):
        if grid[row][i] == num:
            return False
    for i in range(0, 9):
        if grid[i][column] == num:
            return False
    square_row = (row // 3) * 3
    square_col = (column // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[square_row + i][square_col + j] == num:
                return False
    return True

Dieser Schritt prüft, ob die angegebene Nummer für die jeweilige Box gültig ist. Die Nummer sollte keines der Kästchen der gleichen Reihe, Spalte oder Blockkästchen sein, um sie an der aktuellen Stelle zu platzieren.

Wenn die Zahl diese Anforderung erfüllt und true zurückgibt, können wir zum nächsten Wert übergehen; Wenn nicht, wird die Nummer abgelehnt. Dann müssen wir alle Blöcke durchlaufen, die sich an den Backtracking-Algorithmus anpassen.

def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1, 10):
                    if checkValidFunc(row, column, num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print("\nSolution for the Sudoku Problem: ")
    printGridFunc()

Der letzte Teil dieses Code-Chunks prüft, ob die Nummer gültig ist oder nicht. Hier hat es den Funktions-Backtracking-Algorithmus eingeführt.

Zuerst sucht es nach einer leeren Zelle; Wenn es gefunden wird, ist das gelöste Sudoku da und es druckt die Lösung des gegebenen Sudoku. Wenn es ein leeres Kästchen findet, würde es durch Iteration eine Zahl von 1 bis 9 erraten.

Wenn eine gültige Zahl existiert, ruft sie solveFunc() auf und bewegt sich zur nächsten leeren Zelle, aber wenn keine der Vermutungen gültig ist, setzt der vorherige Aufruf der Funktion den Wert der Zelle auf 0 zurück und fährt fort Iterieren, um die folgende gültige Zahl zu finden.

Wenn der Algorithmus die leeren Kästchen bis zur Sackgasse mit gültigen Zahlen füllt, verfolgt er den Prozess zurück und wiederholt den gesamten Prozess. Lassen Sie uns zum Schluss das Gitter passieren und die Funktion aufrufen, um das angegebene Sudoku zu lösen.

puz = (
    "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()

Vollständiger Quellcode:

def setBoardFunc(puz):
    global grid
    print("\n---------------Sudoku Solver---------------\n")
    print("Here is the Sudoku Problem :")
    for i in range(0, len(puz), 9):
        row = puz[i : i + 9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()


def printGridFunc():
    global grid
    for row in grid:
        print(row)


def checkValidFunc(row, column, num):
    global grid
    for i in range(0, 9):
        if grid[row][i] == num:
            return False
    for i in range(0, 9):
        if grid[i][column] == num:
            return False
    square_row = (row // 3) * 3
    square_col = (column // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[square_row + i][square_col + j] == num:
                return False
    return True


def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1, 10):
                    if checkValidFunc(row, column, num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print("\nSolution for the Sudoku Problem: ")
    printGridFunc()


puz = (
    "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()

Ausgang:

Abschluss

Obwohl es mehr Lösungsmöglichkeiten gibt, macht die Verwendung des Backtracking-Algorithmus die endgültige Ausgabe des Sudoku genauer, aber es dauert länger, da es aus vielen Iterationen besteht. Das Lösen von Sudoku-Rätseln verbessert jedoch das logische Denken einer Person und ist eine aufregende Art, die Freizeit zu verbringen.