Sudoku-Lösung in Python

Das Erstellen von Sudoku-Lösern kann eine großartige Möglichkeit sein, sich mit rekursivem Backtracking und dem Lösen von Algorithmen vertraut zu machen. In diesem Blogbeitrag untersuchen wir einige Hilfsfunktionen eines Befehlszeilen-Sudoku-Spielprojekts, das ich erstellt habe, um diese Methoden zu demonstrieren. Diese Datei enthält wichtige Hilfsfunktionen, die das Lösen von Sudoku-Rätseln erleichtern. Wir werden die Schlüsselfunktionen aufschlüsseln: is_valid, find_empty undsolve.

Überprüfung der Gültigkeit einer Nummer
Die Funktion is_valid prüft, ob die Platzierung einer bestimmten Zahl in einer bestimmten Zelle gemäß den Sudoku-Regeln gültig ist.

def is_valid(board, row, col, num):
    # Check if the number is not present in the same row and column
    if num in board[row] or num in [board[i][col] for i in range(9)]:
        return False

    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False
    return True

Zeilen- und Spaltenprüfung: Stellt sicher, dass die Zahl nicht bereits in derselben Zeile oder Spalte vorhanden ist.
Subgrid Check: Stellt sicher, dass die Nummer nicht im 3x3-Subgrid vorhanden ist.

Eine leere Zelle finden

Die Funktion find_empty sucht die nächste leere Zelle (dargestellt durch 0) auf der Tafel.

def find_empty(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

Iteration: Durchläuft die Tafel, um eine leere Zelle zu finden.
Zurück: Gibt die Koordinaten der ersten leeren Zelle zurück, die gefunden wurde, oder Keine, wenn die Tafel voll ist.

Das Sudoku-Rätsel lösen

Die Lösungsfunktion nutzt Backtracking, um das Sudoku-Rätsel zu lösen.

def solve(board):
    empty_cell = find_empty(board)
    # Board is solved
    if not empty_cell:
        return board

    row, col = empty_cell

    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    random.shuffle(numbers)

    for num in numbers:
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve(board):
                return board
            # Backtrack if current placement doesn't lead to a solution
            board[row][col] = 0
        # No valid number for current empty cell
    return False

Leere Zelle suchen: Verwendet find_empty, um die nächste leere Zelle zu finden.
Backtracking: Versucht, die Zahlen 1–9 in die leere Zelle einzufügen und überprüft die Gültigkeit mit is_valid.

Rekursive Lösung: Versucht rekursiv, das Brett zu lösen. Wenn eine Platzierung zu einer Lösung führt, wird das gelöste Board zurückgegeben.
Zurückverfolgen: Wenn eine Platzierung nicht zu einer Lösung führt, wird die Zelle zurückgesetzt und es wird mit der nächsten Nummer versucht.

Abschluss

Hilfsfunktionen sind entscheidend für die Funktionalität unseres Sudoku-Lösers. Die Funktion is_valid stellt sicher, dass die Sudoku-Regeln befolgt werden, find_empty hilft beim Auffinden der nächsten auszufüllenden Zelle und Solve verwendet rekursives Backtracking, um die Lösung zu finden. Das Verständnis dieser Hilfsfunktionen bietet Einblick in die Logik hinter dem programmgesteuerten Lösen von Sudoku-Rätseln.

Das obige ist der detaillierte Inhalt vonSudoku-Lösung in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!