Résolution et créations de sudokus
Description
Voilà une p'tite classe qui peut résoudre et générer une grille de Sudoku avec plusieurs niveaux de difficulté.
Pour ceux qui ne connaissent pas ce jeu:
Le Sudoku se compose d'une grille 9x9 divisée en 9 carrés 3x3.
Le but du jeu est de remplir toute la grille de façon à ce que chacun des chiffre de 1 à 9 se retrouve une et une seule fois dans chaque ligne, dans chaque colonne et dans chacun des 9 carrés 3x3.
Selon le niveau de difficulté, un certain nombres de chiffres sont déjà donnés, et c'est au joueur de compléter le reste.
Ici le programme nécessite que l'on remplisse un fichier avec une suite de 81 chiffres, en mettant des 0 à la place des case vides à compléter.
L'idée générale est la suivante:
J'utilise deux procédures de résolutions: "elimination" et "recherche de position unique".
L'"élimination" va parcourir toutes les cases non encore déterminées et pour chacune de ces cases, supprimer les valeurs qui ne peuvent plus y etre (tout simplement en supprimant les valeurs qui sont déjà présentes dans la ligne la colonne et le carré de la case considérée.)
La "recherche de position unique" va regarder s'il y a des chiffre qui n'ont plus qu'une seule possibilité de placement dans une ligne, une colonne ou un carré; et dans l'affirmative, elle y place cette valeur.
Le programme lance ces deux procédure tant qu'elle modifie le Sudoku et donc tant qu'elle avancent vers la solution.
Lorsque plus rien n'est modifié par ces procédure et que le Sudoku n'est pas encore résolu, on cherche la première case qui n'est pas encore déterminée, et on fait un test d'hypothèse sur celle-ci. et on tente de résoudre récursivement le nouveau problème (éventuellement impossible).
Pour ceux qui ne connaissent pas ce jeu:
Le Sudoku se compose d'une grille 9x9 divisée en 9 carrés 3x3.
Le but du jeu est de remplir toute la grille de façon à ce que chacun des chiffre de 1 à 9 se retrouve une et une seule fois dans chaque ligne, dans chaque colonne et dans chacun des 9 carrés 3x3.
Selon le niveau de difficulté, un certain nombres de chiffres sont déjà donnés, et c'est au joueur de compléter le reste.
Ici le programme nécessite que l'on remplisse un fichier avec une suite de 81 chiffres, en mettant des 0 à la place des case vides à compléter.
Conclusion :
L'idée générale est la suivante:
J'utilise deux procédures de résolutions: "elimination" et "recherche de position unique".
L'"élimination" va parcourir toutes les cases non encore déterminées et pour chacune de ces cases, supprimer les valeurs qui ne peuvent plus y etre (tout simplement en supprimant les valeurs qui sont déjà présentes dans la ligne la colonne et le carré de la case considérée.)
La "recherche de position unique" va regarder s'il y a des chiffre qui n'ont plus qu'une seule possibilité de placement dans une ligne, une colonne ou un carré; et dans l'affirmative, elle y place cette valeur.
Le programme lance ces deux procédure tant qu'elle modifie le Sudoku et donc tant qu'elle avancent vers la solution.
Lorsque plus rien n'est modifié par ces procédure et que le Sudoku n'est pas encore résolu, on cherche la première case qui n'est pas encore déterminée, et on fait un test d'hypothèse sur celle-ci. et on tente de résoudre récursivement le nouveau problème (éventuellement impossible).
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.