Méthodes de résolutionCes méthodes de résolution sont utilisées dans l'ordre de complexité - si l'une d'elles change la grille de résolution alors le solveur repart en arrière pour utiliser la méthode de résolution A et recommence. Méthode de Résolution ARegardez si dans une ligne de la grille de résolution certains chiffres n'apparaissent qu'une seule fois dans cette ligne. Si tel est le cas, la case contenant ce chiffre doit être la solution. Cette règle est répétée pour les colonnes et les blocs. Méthode de Résolution BRegardez si dans une ligne de la grille de résolution certains chiffres n'apparaissent que dans un bloc spécifique. Ce chiffre doit être dans cette ligne, vous pouvez donc éliminer ce chiffre des autres cases de ce bloc. Répétez cette règle pour les colonnes. La même règle s'applique pour les blocs - regardez si dans un bloc de la grille de résolution certains chiffres n'apparaissent que dans une ligne ou colonne spécifique. Ce chiffre doit être dans ce bloc, vous pouvez donc éliminer ce chiffre dans les cases de la ligne ou de la colonne en-dehors de ce bloc. Méthode de Résolution CRegardez si dans une ligne de la grille de résolution un chiffre n'apparaît que deux fois dans la ligne. Si les cases qui contiennent ce chiffre correspondent avec un autre chiffre qui satisfait ce critère, alors ces cases doivent contenir cette paire de chiffres - vous pouvez donc éliminer les autres options de ces cases. A nouveau, cette règle est répétée pour les colonnes et les blocs. Cette méthode est également répétée pour les triplets et plus. Méthode de Résolution D MISE A JOUR!La méthode révisée a été codée par Alan Chambers - merci Al! Regardez si dans une ligne de la grille de résolution il existe un groupe de N cases qui contiennent seulement N chiffres possibles. Si une telle 'chaîne' existe, alors ces cases doivent contenir ces chiffres, vous pouvez donc éliminer les chiffres des autres cases de cette ligne. Cette règle est répétée pour les colonnes et les blocs. Par exemple, dans la ligne 1 2 3 4 5 6 7 8 9 --------------------------------------------------------------------------------- 378 38 6789 37 458 2 34568 489 1 Les colonnes 1,2 et 4 contiennent les chiffres 3,7, et 8. Nous pouvons donc éliminer [78] dans la colonne 3, [8] dans la colonne 5 et [38] dans la colonne 7 et [8] dans la colonne 8. Après ça, la ligne ressemble à ceci: 1 2 3 4 5 6 7 8 9 --------------------------------------------------------------------------------- 378 38 69 37 45 2 456 49 1 Si vous souhaitez un exemple pratique, essayez cette page. Méthode de Résolution E - pas encore implémentéeOn nous a suggéré une nouvelle Méthode de Résolution pour résoudre un de nos Challenge Sudokus.. mais nous ne l'avons pas encore codée. Si vous souhaitez découvrir cette règle, ou si vous avez envie de la coder, cliquez ici. Méthode de Résolution F - implémentée partiellementRegardez si dans sune ligne il existe des instances où un chiffre apparaît dans seulement deux cases. S'il existe d'autres lignes qui satisfont à la même règle avec le même chiffre, et que les colonnes de ces cases sont les mêmes dans les deux cas, alors ce chiffre doit apparaître dans deux de ces quatre cases. Vous pouvez donc éliminer toutes les occurrences de ce chiffre dans les colonnes en question. La même règle est répétée pour les colonnes. Il existe aussi un équivalent pour les blocs (mais ce n'est pas encore implémenté) qui est: Si, pour chaque ligne, les deux cases sont dans les deux mêmes blocs alors vous pouvez éliminer les autres occurrences dans les blocs en question. Répétez cette règle pour les colonnes relatives aux lignes et aux colonnes relatives aux blocs. Répétez alors cette règle pour les blocs - si deux blocs partagent ou bien les lignes, ou bien les colonnes et qu'un seul chiffre apparaît dans uniquement deux cases dans chaque bloc, dans les lignes ou les colonnes en question, alors les autres occurrences de ce chiffre peuvent être supprimées de ces lignes ou de ces colonnes. (plutôt compliqué, hein? je ne suis pas sûr de comprendre ceici moi-même). Qu'est-ce que le 'autoriser le Deviner-Vérifier'?Ceci est l'implémentation de ce qui est connu comme un 'Fil d'Ariane'. Si on a épuisé toutes les méthodes de résolution, le solveur fait une hypothèse sur la réponse d'une case, et il cherche alors à trouver une réponse en ré-appliquant les méthodes de résolution. Si cela conduit à un Sudoku invalide, il tente une autre hypothèse. S'il reste encore des options, il continue sur les autres hypothèses jusqu'à ce qu'il trouve une réponse (ou obtienne un Sudoku invalide). Certaines personnes prétendent que cette méthode ne serait pas 'logique', nous avons alors donné le choix d'utiliser cette méthode, en cochant une case. Retourner la Première Solution PossibleSi vous utlisez la technique du deviner-vérifier, il est toujours possible qu'il y ait plus d'une solution à un Sudoku donné. Le fait de décocher la case 'Retourner la Première Solution Possible' obligera le solveur à vérifier toutes les hypothèses afin de confirmer que votre solution est unique. RemerciementsMerci à Nicolas Leoutre pour la translation Français! Merci beaucoup à 'rubylips' de http://www.act365.com/sudoku/ pour ses conseils et son aide sur le fil d'Ariane et ses autres suggestions utiles. Merci aussi à r.e.s pour nous avoir fourni un lien sur la preuve que les Sudukos sont des problèmes NP, et pour avoir testé le solveur. Merci à Pete Forman pour la mise à jour de la méthode de résolution B, en ce qui concerne les blocs. Merci à Colin Hughes pour avoir signalé le bug dans la méthode d'initialisation. Merci à Keven Cook pour avoir signalé le bug dans le panneau de reporting. Merci à Tim Lindsay pour les exemples irrésolubles par la logique - et son inspiration pour la page de challenge. Merci à Bill Giles pour son idée de solveur par étapes. Merci à Mark Summerville pour avoir founir les règles logiques des méthodes de résolution E et F. Merci à Kevin Lawson pour avoir suggéré le puzzle de challenge alternatif. Merci à John MacLeod pour la version révisée de la méthode de résolution D. Merci à David Budgett et John MacLeod (encore une fois!) pour l'explication de la version 'blocs' de la méthode de résolution F. Merci à Tim Nobel et Michael Lawrence pour leurs suggestions concernant de nouvelles règles. Merci à Al Chambers pour avoir codé la révision de la méthode D - beau travail! |