Solveur de Sudoku

L'approche algorithmique de résolution diffère de l'approche humaine, en ce sens qu'elle essaye de dégager un nombre minimum de règles, relativement simples à calculer, mais pas forcément simples à exploiter visuellement par un être humain.
En l'occurrence l'approche algorithmique que nous avons choisie utilise systématiquement les possibilités restantes dans une case. Cette approche est difficile pour un être humain car elle surcharge la grille et nous verrons qu'il cherche le plus possible à l'éviter.

Nous avons retenu la méthode générale suivante :

• Utilisation de règles qui diminuent les possibilités restantes dans les cases, jusqu'à arriver à une seule possibilité.
• Itération de ces règles jusqu'à ce que la dernière itération ne puisse plus faire de diminutions de possibilités.

Trois règles couvrent le champ des règles que nous considèront comme des règles de base, et sont exécutées par le bouton "Règles de base" :

• L'élimination consiste, à partir d'une case déjà trouvée, à supprimer la valeur de cette dite case dans toutes les autres cases appartenant aux mêmes ligne, colonne et carré que cette dite case.
• La règle des candidats multiples (naked subset) consiste à trouver dans une région, n cases non encore trouvées (mais ne constituant pas la totalité des cases non encore trouvées de cette région), ces cases contenant à elles toutes exactement n chiffres possibles. On peut alors supprimer ces chiffres des autres cases non encore trouvées de cette région.
• La règle d'interactions entre régions (locked candidates) consiste à trouver une intersection entre 2 régions (ligne et carré ou colonne et carré) qui, en ce qui concerne une de ces 2 régions contienne un chiffre que les cases de cette région n'appartenant pas à cette intersection ne contiennent pas. On peut alors supprimer ce chiffre dans les cases de la 2ème région n'appartenant pas à l'intersection.

La règle d'interactions entre région n'est utilisée que quand les 2 précédentes ne donnent plus de résultats.

Il existe une règle duale de la règle des candidats multiples, qui est la règle des candidats multiples cachés (hidden subset). Elle consiste à trouver dans une région, n cases non encore trouvées (mais ne constituant pas la totalité des cases non encore trouvées de cette région), ces cases pouvant contenir plus de n chiffres possibles, mais en contenant exactement n qui ne sont pas dans les autres cases non encore trouvées de cette région. On peut alors supprimer dans les n cases en question les chiffres différents des n chiffres en question. Ces 2 règles donnant les mêmes résultats, nous avons utilisé la plus facile à programmer.

On peut maintenant faire le lien avec l'approche de l'être humain :

• Tant qu'il est dans les règles de base, il essaye d'éviter de marquer les possibilités de chaque case. Ces possibilités sont implicites ou peuvent être indiquées par des annotations dans la marge. La méthode d'élimination n'est donc pas une méthode en elle même. Par contre le choix des annotations à mettre dans la marge et leur découverte est important.
• La règle des candidats multiples correspond à l'examen d'une case d'une région donnée, pour trouver qu'elle ne peut contenir qu'un seul chiffre, ou que 2 cases (cases couplées) ne peuvent contenir que 2 chiffres. Elle devient difficile à mettre en oeuvre pour 3 cases ou plus.
• La règle des candidats multiples cachés correspond à une approche par chiffre, pour trouver qu'un chiffre donné ne peut se trouver que dans une seule case d'une région donnée ou que seulement 2 chiffres possibles (chiffres couplés) ne peuvent se trouver que dans seulement 2 cases. Elle devient difficile à mettre en oeuvre pour 3 cases ou plus.
• Etant donné la difficulté à appliquer les 2 méthodes précédentes pour un grand nombre de cases, l'être humain, contrairement à l'algorithme, utilise les 2, mais seulement pour des petits nombres.
• La règle d'interactions entre régions peut se faire sans avoir à marquer les possibilités. Mais elle peut passer inaperçue et c'est l'habileté du joueur qui permettra de la détecter.
• Les règles avancée imposent de marquer les possibilittés.

Dans l'approche humaine, les règles avancées imposent de marquer les possibilittés.

• XYZ-Wing : Elle est intéressante car elle peut être repérée facilement et rapidement.
• XY-Chain : La longueur de chaine est limitée à 6. Une chaine de longueur 3 est un XY-Wing
• X-Cycle(ou Fisshy Cycle) : La longueur de chaine est limitée à 6. C'est un cycle pair de cases liées alternativement par des liens forts et des liens faibles. Il comporte entre autres, comme cas particuliers :
  • X-Wing : Elle peut être trouvée par une recherche systématique mais longue. Avec un peu d'habitude on peut arriver à la repérer plus rapidement.
  • Swordfish simple (à 2 candidats) : Elle peut être trouvée dans la même recherche que celle du X-Wing.
  Sont donnés en priorité les cas où les cases sont alignées en ligne et en colonne, c'est à dire le X-Wing, et le Swordfish de 3 lignes et 3 colonnes.
• X-Chain : La longueur de chaine est limitée à 6. C'est un X-Cycle non fermé dont les 2 extrémités appartiennent à un lien fort, et sont vues en même temps (même ligne, même colonne ou même carré) par une ou plusieurs cases. Il comporte entre autres, comme cas particuliers :
  • Turbot Fish : c'est le cas d'une chaine de longueur 4. Le Skyscraper et le 2-String_Kite en sont 2 cas particuliers.
• Swordfish : C'est le Swordfish étendu : pour un chiffre donné, les candidats dans 3 lignes ne sont situés que dans 3 colonnes ; il doiy y avoir au moins 2 candidats par ligne, et chaque colonne doit avoir au moins 2 candidats. Le swordfish simple est un cas particulier du swordfish étendu, mais il se peut qu'il permette d'éliminer plus de possibilités que ce dernier.
• Jellyfish : C'est le même principe que le Swordfish, avec 4 lignes et 4 colonnes.
• Squirmbag : C'est le même principe que le Swordfish, avec 5 lignes et 5 colonnes.