Tifsudoku : résolution des grilles de sudoku pas à pas
Description
Ce programme permet de résoudre les grilles de Sudoku de deux manières différentes :
- En une passe.
- En mode pas à pas, avec un commentaire sur la méthode employée.
Le programme ne génère pas de grilles.
Quelques grilles déjà saisies manuellement sont livrées dans le .zip (répertoire Sudoku).
Effectué avec Visual Studio 2005.
METHODES DE RESOLUTION
TifSudoku emploie successivement cinq 'méthodes' de résolution d'un Sudoku.
Si la méthode 1 ne donne rien, on passe à la 2, etc...
A chaque modification dans la grille, on recommence par la méthode 1)
1) SUPPRESSION IMPOSSIBLES.
Pour chaque case, on a un tableau de 9 booléens qui contient la liste des valeurs impossibles de la case.
-> Pour chaque case, on met à jour les valeurs impossibles qui sont déjà affectées à une case de la même ligne, de la même colonne ou du même bloc. Ceci permet d'affecter dans la foulée les cases qui contiennent des valeurs évidentes (cases qui n'ont plus qu'une valeur possible).
2) AFFECTATION VALEURS UNIQUES.
-> On affecte une valeur à une case d'un bloc, d'une colonne ou d'une ligne qui est la seule à possèder cette valeur possible particulière.
3) SUPPRESSION PAIRES EXCLUSIVES.
-> Si dans un bloc (ou colonne ou ligne), n cases ont n mêmes chiffres possibles, on peut supprimer ces chiffres possibles des autres cases du bloc (ou colonne ou ligne).
Exemple :
Deux cases d'un bloc n'ont que 1 et 2 comme valeurs possibles. Si l'une vaut 1, l'autre vaut forcément 2, et vice et versa ;). Aucune autre case du bloc ne pourra donc avoir 1 ou 2 comme valeur.
Cette méthode ne permet pas de déterminer la valeur d'une case, mais permet d'avancer en supprimant des valeurs impossibles pour certaines cases.
4) SUPPRESSION DES CHIFFRES EXCLUSIFS.
Plus dur à expliquer en baratin, on va donner direct un exemple :
Exemple :
Dans un bloc, les cases contenant la valeur possible X sont toutes sur la même ligne. La valeur X de ce bloc sera donc forcément sur cette ligne. Par conséquent, on ne pourra pas avoir la valeur X sur cette ligne et dans les autres blocs. On peut donc supprimer cette valeur X des valeurs possibles des cases de la même ligne et des autres blocs.
Cette suppression est à appliquer en bloc/ligne, bloc/colonne, colonne/bloc et ligne/bloc
Cette méthode ne permet pas de déterminer la valeur d'une case, mais permet d'avancer en supprimant des valeurs impossibles pour certaines cases.
5) IMPASSE
Les quatre premières solutions n'ont rien donné. On va retenir une valeur possible pour une case et tenter de résoudre le Sudoku :
- Si on tombe sur une erreur, on essaie avec une autre solution.
- Si on arrive à finir la grille, on essaie les autres solutions.
--> Si les autres solutions conduisent à une erreur, on retient la seule solution qui fonctionne, le Sudoku est résolu.
--> Si une autre solution fonctionne, le Sudoku a deux (ou plus) solutions, il n'est donc pas correct, on est en erreur.
Le programme s'arrête dès la deuxième solution trouvée (il pourrait y en avoir plus, mais ce n'est pas la peine d'aller plus loin).
L'impasse est effectuée sur une des cases de la grille qui contient le moins de solutions possibles (on regarde déjà s'il y a des cases avec deux solutions possibles, puis trois, ...)
Pour mémoriser les différentes grilles, on les stocke dans une pile (dernier rentré, premier sorti).
Ex : Lorsqu'on effectue une impasse sur une case qui a trois valeurs possibles, on crée trois grilles distinctes, chacune avec une des trois valeurs possibles. On stocke deux grilles dans la pile et on tente de résoudre la troisième. On peut ensuite continuer à empiler des grilles s'il y a à nouveau des impasses. Ensuite, si l'on souhaite revenir en arrière, il suffit de dépiler pour retrouver les grilles dans le bon ordre.
EN UNE PASSE
Le mode 'Résoudre en une passe' applique les mêmes méthodes de résolution que le pas à pas.
FONCTIONNEMENT
La saisie d'une valeur dans une case de la grille se fait directement au clavier, lorsque la souris pointe sur la case.
Il est possible de sauvegarder/charger les grilles sous forme de fichier .txt
LIMITES ET BUGS
Toutes les grilles que j'ai testées ont été résolues avec succès.
Il reste des bugs :
- lorsqu'on modifie manuellement des valeurs d'une grille en cours de résolution pas à pas (les couleurs d'erreur ne s'affichent parfois pas).
- lorsqu'on appuie sur résoudre en une seule passe en plein milieu d'une résolution pas à pas (la résolution ne se lance pas à tous les coups).
En ce qui concerne les limites du code :
- Certaines fonctions ne sont pas optimisées et plusieurs pourraient être regroupées.
- Il n'y a pas une séparation claire entre l'interface graphique et le moteur de résolution. Le code est donc peu lisible et peu portable... (le grand nombre de tableaux n'arrange pas les choses).
-> Initialement, je voulais faire une résolution récursive pour l'impasse mais il fallait casser tout le programme. L'impasse se résoud finalement avec une pile (Stack), ce qui est finalement une bonne solution pour le pas à pas.
Si vous avez des remarques, des questions ou des améliorations à apporter n'hésitez pas à m'en faire part !
TiFred
[email supprimé par la modération]
- En une passe.
- En mode pas à pas, avec un commentaire sur la méthode employée.
Le programme ne génère pas de grilles.
Quelques grilles déjà saisies manuellement sont livrées dans le .zip (répertoire Sudoku).
Effectué avec Visual Studio 2005.
Conclusion :
Quelques précisions :METHODES DE RESOLUTION
TifSudoku emploie successivement cinq 'méthodes' de résolution d'un Sudoku.
Si la méthode 1 ne donne rien, on passe à la 2, etc...
A chaque modification dans la grille, on recommence par la méthode 1)
1) SUPPRESSION IMPOSSIBLES.
Pour chaque case, on a un tableau de 9 booléens qui contient la liste des valeurs impossibles de la case.
-> Pour chaque case, on met à jour les valeurs impossibles qui sont déjà affectées à une case de la même ligne, de la même colonne ou du même bloc. Ceci permet d'affecter dans la foulée les cases qui contiennent des valeurs évidentes (cases qui n'ont plus qu'une valeur possible).
2) AFFECTATION VALEURS UNIQUES.
-> On affecte une valeur à une case d'un bloc, d'une colonne ou d'une ligne qui est la seule à possèder cette valeur possible particulière.
3) SUPPRESSION PAIRES EXCLUSIVES.
-> Si dans un bloc (ou colonne ou ligne), n cases ont n mêmes chiffres possibles, on peut supprimer ces chiffres possibles des autres cases du bloc (ou colonne ou ligne).
Exemple :
Deux cases d'un bloc n'ont que 1 et 2 comme valeurs possibles. Si l'une vaut 1, l'autre vaut forcément 2, et vice et versa ;). Aucune autre case du bloc ne pourra donc avoir 1 ou 2 comme valeur.
Cette méthode ne permet pas de déterminer la valeur d'une case, mais permet d'avancer en supprimant des valeurs impossibles pour certaines cases.
4) SUPPRESSION DES CHIFFRES EXCLUSIFS.
Plus dur à expliquer en baratin, on va donner direct un exemple :
Exemple :
Dans un bloc, les cases contenant la valeur possible X sont toutes sur la même ligne. La valeur X de ce bloc sera donc forcément sur cette ligne. Par conséquent, on ne pourra pas avoir la valeur X sur cette ligne et dans les autres blocs. On peut donc supprimer cette valeur X des valeurs possibles des cases de la même ligne et des autres blocs.
Cette suppression est à appliquer en bloc/ligne, bloc/colonne, colonne/bloc et ligne/bloc
Cette méthode ne permet pas de déterminer la valeur d'une case, mais permet d'avancer en supprimant des valeurs impossibles pour certaines cases.
5) IMPASSE
Les quatre premières solutions n'ont rien donné. On va retenir une valeur possible pour une case et tenter de résoudre le Sudoku :
- Si on tombe sur une erreur, on essaie avec une autre solution.
- Si on arrive à finir la grille, on essaie les autres solutions.
--> Si les autres solutions conduisent à une erreur, on retient la seule solution qui fonctionne, le Sudoku est résolu.
--> Si une autre solution fonctionne, le Sudoku a deux (ou plus) solutions, il n'est donc pas correct, on est en erreur.
Le programme s'arrête dès la deuxième solution trouvée (il pourrait y en avoir plus, mais ce n'est pas la peine d'aller plus loin).
L'impasse est effectuée sur une des cases de la grille qui contient le moins de solutions possibles (on regarde déjà s'il y a des cases avec deux solutions possibles, puis trois, ...)
Pour mémoriser les différentes grilles, on les stocke dans une pile (dernier rentré, premier sorti).
Ex : Lorsqu'on effectue une impasse sur une case qui a trois valeurs possibles, on crée trois grilles distinctes, chacune avec une des trois valeurs possibles. On stocke deux grilles dans la pile et on tente de résoudre la troisième. On peut ensuite continuer à empiler des grilles s'il y a à nouveau des impasses. Ensuite, si l'on souhaite revenir en arrière, il suffit de dépiler pour retrouver les grilles dans le bon ordre.
EN UNE PASSE
Le mode 'Résoudre en une passe' applique les mêmes méthodes de résolution que le pas à pas.
FONCTIONNEMENT
La saisie d'une valeur dans une case de la grille se fait directement au clavier, lorsque la souris pointe sur la case.
Il est possible de sauvegarder/charger les grilles sous forme de fichier .txt
LIMITES ET BUGS
Toutes les grilles que j'ai testées ont été résolues avec succès.
Il reste des bugs :
- lorsqu'on modifie manuellement des valeurs d'une grille en cours de résolution pas à pas (les couleurs d'erreur ne s'affichent parfois pas).
- lorsqu'on appuie sur résoudre en une seule passe en plein milieu d'une résolution pas à pas (la résolution ne se lance pas à tous les coups).
En ce qui concerne les limites du code :
- Certaines fonctions ne sont pas optimisées et plusieurs pourraient être regroupées.
- Il n'y a pas une séparation claire entre l'interface graphique et le moteur de résolution. Le code est donc peu lisible et peu portable... (le grand nombre de tableaux n'arrange pas les choses).
-> Initialement, je voulais faire une résolution récursive pour l'impasse mais il fallait casser tout le programme. L'impasse se résoud finalement avec une pile (Stack), ce qui est finalement une bonne solution pour le pas à pas.
Si vous avez des remarques, des questions ou des améliorations à apporter n'hésitez pas à m'en faire part !
TiFred
[email supprimé par la modération]
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.