Résolution de Sudoku en Python

Créer des solveurs de sudoku peut être un excellent moyen de vous familiariser avec le retour en arrière récursif et la résolution d'algorithmes. Dans cet article de blog, nous explorerons certaines fonctions d'assistance d'un projet de jeu Sudoku en ligne de commande que j'ai créé pour démontrer ces méthodes. Ce fichier contient des fonctions d'aide essentielles qui facilitent la résolution des puzzles Sudoku. Nous allons décomposer les fonctions clés : is_valid, find_empty et solve.

Vérification de la validité d'un numéro
La fonction is_valid vérifie si le placement d'un nombre spécifique dans une cellule donnée est valide selon les règles du Sudoku.

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

Vérification des lignes et des colonnes : garantit que le numéro n'est pas déjà présent dans la même ligne ou colonne.
Vérification de la sous-grille : garantit que le numéro n'est pas présent dans la sous-grille 3x3.

Trouver une cellule vide

La fonction find_empty localise la prochaine cellule vide (représentée par 0) sur le tableau.

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

Itération : parcourt le tableau pour trouver une cellule vide.
Retour : Renvoie les coordonnées de la première cellule vide trouvée ou Aucune si le tableau est plein.

Résoudre le casse-tête du Sudoku

La fonction de résolution utilise le retour en arrière pour résoudre le puzzle Sudoku.

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

Rechercher une cellule vide : utilise find_empty pour localiser la prochaine cellule vide.
Retour en arrière : essaie de placer les nombres 1 à 9 dans la cellule vide, en vérifiant la validité avec is_valid.

Résolution récursive : tente de résoudre le tableau de manière récursive. Si un placement mène à une solution, il renvoie le tableau résolu.
Retour en arrière : si un placement ne mène pas à une solution, il réinitialise la cellule et essaie le numéro suivant.

Conclusion

Les fonctions d'assistance sont cruciales pour le fonctionnement de notre solveur Sudoku. La fonction is_valid garantit que les règles du Sudoku sont suivies, find_empty aide à localiser la prochaine cellule à remplir et solve utilise un retour en arrière récursif pour trouver la solution. Comprendre ces fonctions d'assistance donne un aperçu de la logique derrière la résolution des puzzles Sudoku par programmation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!