Étudiez attentivement ce code et découvrez une manière intelligente d'utiliser la récursivité pour résoudre ces énigmes difficiles du sudoku.
Sudoku est un jeu de nombres populaire composé d'une grille 9x9 avec des chiffres de 1 à 9. Le puzzle comprend une combinaison de chiffres et des espaces vides, que vous devez remplir.
Lorsque vous remplissez les espaces vides, chaque ligne, colonne et sous-grille 3x3 doit contenir tous les chiffres de 1 à 9.
Un simple script Python peut vous aider à résoudre un puzzle Sudoku. Il peut analyser tous les espaces vides du tableau Sudoku et trouver un nombre possible à remplir dans chaque espace vide.
Comment créer et afficher le plateau de Sudoku
Dans un script Python, vous devrez utiliser une liste de tableaux pour stocker les valeurs du puzzle Sudoku non résolu.
Le code utilisé dans ce projet est disponible dans ce Dépôt GitHub sous licence MIT.
- Dans un nouveau script Python appelé sudoku.py, stockez toutes les valeurs de la grille 9x9. Chaque rangée et colonne représente les neuf nombres à travers et en bas du puzzle Sudoku. Ajoutez des 0 pour représenter les espaces à résoudre :
planche = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - Dans une nouvelle fonction appelée print_board, utiliser une boucle for pour traiter chaque ligne de la grille :
définitivementprint_board(conseil):
pour ligne dans gamme(9): - Pour séparer chaque ligne en tiers, vérifiez si la ligne est divisible par trois et ajoutez une ligne :
si ligne % 3 == 0et ligne != 0:
imprimer("- - - - - - - - - - - - - - ") - Dans chaque ligne, faites une boucle dans chaque colonne. Vous pouvez également diviser les colonnes en tiers en vérifiant si la colonne est divisible par trois :
pour col dans gamme(9):
si col % 3 == 0et col != 0:
imprimer(" | ", fin="") - Imprimer la valeur numérique stockée dans la grille. Si la colonne est la dernière colonne de cette ligne particulière, ajoutez une ligne de rupture, de sorte que la ligne suivante apparaisse sur une nouvelle ligne :
si col == 8:
imprimer (planche[ligne][col])
autre:
print (chaîne (planche[ligne][col]) + " ", fin="") - Appelez la fonction pour imprimer le tableau :
print_board (tableau) - Dans une ligne de commande, accédez au dossier dans lequel vous avez stocké votre script Python, par exemple :
cd de bureau - Utilisez la commande python pour exécuter votre script Sudoku. Voir le puzzle imprimé sur l'écran :
python sudoku.py
Comment identifier les espaces vides à résoudre
Vous pouvez parcourir les listes pour trouver les espaces composés de 0. Ceux-ci déterminent quels espaces doivent être résolus.
- Dans une nouvelle fonction appelée find_empty(), parcourez chaque ligne et colonne du tableau :
définitivementfind_empty(conseil):
pour ligne dans gamme(9):
pour col dans gamme(9): - Si la valeur de la cellule courante est 0, retourne la position courante de la cellule vide :
si tableau[ligne][col] == 0:
retour (ligne, colonne) - Si le script atteint la fin de la fonction, cela signifie que le script n'a trouvé aucune cellule avec la valeur 0. Dans ce cas, ne retournez rien :
retourAucun - Dans une nouvelle fonction appelée solve(), utilisez la fonction find pour trouver le premier espace vide sur le tableau :
définitivementrésoudre(conseil):
trouver = trouver_vide (tableau) - La fonction find_empty() renvoie la position de la cellule au format tuple, par exemple (0, 2). Enregistrez ces valeurs séparément dans le ligne et col variables. Sinon, retourne true pour signifier qu'il n'y a plus d'espaces vides à résoudre :
sipas trouver:
retourVrai
autre:
rangée, col = trouver
Comment résoudre le puzzle pour chaque ligne, colonne et grille 3x3
Maintenant que vous pouvez identifier le premier espace vide à résoudre, vous devrez essayer de trouver un nombre approprié pour remplir cet espace et résoudre le puzzle.
Utilisation de la récursivité, appelez la fonction solve() en elle-même pour essayer toutes les combinaisons possibles de valeurs pour tous les autres espaces également.
- Dans la fonction solve (), après avoir trouvé le premier espace vide, parcourez chaque nombre de 1 à 9. Ces nombres représentent les nombres possibles qui pourraient remplir l'espace non résolu :
pour nombre dans gamme(1, 10): - Entrez le tableau, le nombre possible et la position de la cellule vide dans une nouvelle fonction. La nouvelle fonction renverra vrai si ce nombre est un nombre valide qui peut résoudre cet espace vide. S'il est valide, attribuez ce numéro à la cellule du tableau :
si is_valid (board, num, (row, col)):
tableau[ligne][col] = num - Créez la fonction is_valid(), avec les paramètres correspondants :
définitivementest valable(planche, num, pos): - Utilisez la fonction pour vérifier si placer le numéro dans cette position enfreint les règles du jeu Sudoku. Vérifiez d'abord si ce nombre existe déjà dans la ligne ou la colonne de la cellule :
pour col dans gamme(9):
si planche[pos[0]][col] == nombre et pos[1] != colonne :
retourFAUXpour ligne dans gamme(9):
si planche[ligne][pos[1]] == nombre et pos[0] != ligne :
retourFAUX - Obtenez la grille 3x3 à laquelle appartient la cellule. Vous pouvez le faire en divisant la position de la cellule par trois :
box_row = pos[0] // 3
box_col = pos[1] // 3 - Pour chaque ligne et colonne de cette grille 3x3, vérifiez si le nombre existe déjà. Si c'est le cas, retournez false :
pour ligne dans plage (box_row*3, box_row*3 + 3):
pour col dans plage (box_col*3, box_col*3 + 3):
si tableau[ligne][col] == num et (ligne, colonne) != pos :
retourFAUX - Si le script atteint la fin de la fonction, cela signifie qu'aucune des règles de Sudoku n'a échoué. Renvoie vrai :
retourVrai - La fonction is_valid() vérifie uniquement si le placement du nombre est valide, mais cela ne signifie pas qu'il s'agit de la bonne réponse à la solution globale. Dans la fonction solve(), appelez à nouveau la fonction solve() avec la carte mise à jour. La fonction solve() peut atteindre un état où elle ne peut plus utiliser de nombres pour remplir les espaces. Dans ce cas, la fonction entière renvoie false, réinitialise cette cellule particulière à 0 et revient en arrière. La fonction solve() ne renvoie vrai que lorsque le script peut remplir tous les espaces :
pour nombre dans gamme(1, 10):
si is_valid (board, num, (row, col)):
tableau[ligne][col] = num
si résoudre (tableau):
retourVrai
tableau[ligne][col] = 0retourFAUX - Pour commencer à résoudre le puzzle, appelez la fonction solve() avec le tableau d'origine, en bas du script, après avoir déclaré la fonction solve() :
résoudre (tableau) - Imprimez le résultat final :
imprimer("Résolu :")
print_board (tableau) - Sur la ligne de commande, utilisez la commande python pour réexécuter le script. Visualisez le puzzle résolu imprimé sur l'écran :
python sudoku.py
Créer des jeux avec Python
Sudoku n'est qu'un des nombreux jeux que vous pouvez créer et résoudre avec Python. Vous pouvez utiliser Python pour créer divers autres jeux, tels qu'un fouillis de mots, un jeu d'aventure textuel ou un jeu de couleurs, pour n'en nommer que quelques-uns.
