Créer un solveur de Sudoku en Python

Le Sudoku est un casse-tête populaire qui consiste en une grille de 9×9 avec des chiffres de 1 à 9. Le puzzle comprend une combinaison de chiffres et quelques espaces vides, que vous devez remplir.

Lorsque vous remplissez les espaces vides, chaque ligne, chaque colonne et chaque sous-grille 3×3 doit contenir tous les chiffres de 1 à 9.

Un simple script Python peut vous aider à résoudre une énigme de Sudoku. Il peut analyser tous les espaces vides sur la planche de Sudoku et trouver un nombre possible pour remplir chaque espace vide.

Comment créer et afficher le tableau 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 repo GitHub sous licence MIT.

1. Dans un nouveau script Python appelé sudoku.py, stockez toutes les valeurs de la grille 9×9. Chaque ligne et chaque colonne représentent les neuf nombres qui traversent et descendent le puzzle Sudoku. Ajoutez des 0 pour représenter les espaces à résoudre :
2. Dans une nouvelle fonction appelée print_board, utilisez une boucle for pour traiter chaque ligne de la grille :
3. Pour séparer chaque ligne en tiers, vérifiez si la ligne est divisible par trois et ajoutez une ligne :
4. À l’intérieur de chaque ligne, parcourez chaque colonne en boucle. Vous pouvez également diviser les colonnes en tiers en vérifiant si la colonne est divisible par trois :
5. Imprimez la valeur numérique stockée dans la grille. Si la colonne est la dernière pour cette ligne particulière, ajoutez une ligne de rupture, de sorte que la ligne suivante apparaisse sur une nouvelle ligne :
6. Appelez la fonction pour imprimer le tableau :
7. Dans une ligne de commande, naviguez jusqu’au dossier où vous avez stocké votre script python, par exemple :
8. Utilisez la commande python pour exécuter votre script Sudoku. Visualisez le puzzle imprimé à l’écran :

Comment identifier les espaces vides à résoudre

Vous pouvez parcourir les listes pour trouver les espaces constitués de 0. Ceux-ci déterminent les espaces à résoudre.

1. Dans une nouvelle fonction appelée find_empty(), parcourez en boucle chaque ligne et chaque colonne du tableau :
2. Si la valeur de la cellule actuelle est 0, renvoyez la position actuelle de la cellule vide :
3. Si le script atteint la fin de la fonction, cela signifie qu’il n’a pu trouver aucune cellule avec la valeur 0. Dans ce cas, ne renvoyez rien :
4. Dans une nouvelle fonction appelée solve(), utilisez la fonction find pour trouver le premier espace vide sur le tableau :
5. La fonction find_empty() renvoie la position de la cellule sous forme de tuple, par exemple (0, 2). Enregistrez ces valeurs séparément dans le fichier rangée et col Sinon, il renvoie true pour signifier qu’il n’y a plus d’espaces vides à résoudre :

Comment résoudre l’énigme pour chaque ligne, chaque colonne et chaque grille 3×3 ?

Maintenant que vous pouvez identifier le premier espace vide à résoudre, vous devez essayer de trouver un nombre approprié pour remplir cet espace et résoudre l’énigme.

En utilisant la récursivité, appelez la fonction solve() à l’intérieur d’elle-même pour essayer toutes les combinaisons possibles de valeurs pour tous les autres espaces également.

1. À l’intérieur de la fonction solve(), après avoir trouvé le premier espace vide, passez en boucle sur chaque nombre de 1 à 9. Ces nombres représentent les nombres possibles qui pourraient remplir l’espace non résolu :
2. Saisissez 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 l’espace vide. Si c’est le cas, assignez ce nombre à la cellule sur le tableau :
3. Créez la fonction is_valid(), avec les paramètres correspondants :
4. Utilisez la fonction pour vérifier si le fait de placer le numéro à cette position enfreint les règles du jeu de Sudoku. Tout d’abord, vérifiez si ce nombre existe déjà dans la ligne ou la colonne de la cellule :
5. Obtenez la grille 3×3 à laquelle la cellule appartient. Pour ce faire, divisez la position de la cellule par trois :
6. Pour chaque ligne et chaque colonne de cette grille 3×3, vérifiez si le numéro existe déjà. Si c’est le cas, il renvoie false :
7. Si le script atteint la fin de la fonction, cela signifie qu’aucune des règles du Sudoku n’a échoué. Retournez alors true :
8. La fonction is_valid() vérifie uniquement si le placement des nombres 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 le tableau mis à jour. La fonction solve() peut arriver à un stade où elle ne peut plus utiliser de nombres pour remplir les espaces. Dans ce cas, la fonction entière renvoie un faux, remet cette cellule particulière à 0 et revient en arrière. La fonction solve() ne renvoie un message vrai que lorsque le script peut remplir tous les espaces :
9. Pour commencer à résoudre le puzzle, appelez la fonction solve() avec le tableau original, à la fin du script, après avoir déclaré la fonction solve() :
10. Imprimez le résultat final :
11. Sur la ligne de commande, utilisez la commande python pour réexécuter le script. Affichez le puzzle résolu à l’écran :

Création de jeux à l’aide de Python

Le sudoku n’est qu’un des nombreux jeux que vous pouvez créer et résoudre à l’aide de Python. Vous pouvez utiliser Python pour créer de nombreux autres jeux, tels qu’un jeu de mots mêlés, un jeu d’aventure textuel ou un jeu de couleurs, pour n’en citer que quelques-uns.

S’abonner à notre lettre d’information