Mathématiques du Sudoku - Définition
La liste des auteurs de cet article est disponible ici.
Méthode de Felgenhauer/Jarvis pour l'énumération de la grille de 9×9
L'approche décrite ici est historiquement la première stratégie employée pour énumérer les solutions d'une grille de Sudoku classique (régions de 3x3 dans une grille de 9x9). Elle a été proposée par Felgenhauer et Jarvis.
Aperçu
L'analyse débute par l'étude des permutations de la première bande utilisée dans des solutions valides. Une fois que la classe d'équivalence et les symétries de cette bande, pour des solutions partielles, sont identifiées, on s'intéresse aux deux autres bandes qui sont construites et comptées pour chaque classe d'équivalence. En effectuant la somme de l'ensemble des combinaisons, on obtient le nombre total de solutions, soit 6 670 903 752 021 072 936 960 (environ 6.67×1021).
Afin de réduire l'espace de recherche, on part du principe que le renommage (par exemple changer le '1' en '2' et vice-versa) des cases produit une solution équivalente. Une grille autorise 9! = 362880 renommages de ce type : un chiffre choisi parmi les 9 chiffres possibles est attribué au premier type de case, un chiffre parmi les 8 restants est attribué au deuxième type de case, un chiffre parmi les 7 restants est attribué au troisième type de case, etc.
