Counting, Symmetries and Equivalence Classes of Sudoku Grids

La Grande Chasse au Puzzle de Sudoku

Imaginez que vous êtes un détective essayant de compter toutes les façons possibles dont un immense manoir de 81 pièces pourrait être meublé avec neuf types de mobilier différents. Mais il y a un piège : les règles sont incroyablement strictes. Dans chaque rangée, chaque colonne et chaque pièce de 3x3, vous devez avoir exactement un exemplaire de chaque type de meuble. C'est le monde du Sudoku, un puzzle qui a captivé des millions de personnes. Mais pour les mathématiciens, le Sudoku n'est pas seulement un jeu ; c'est un gigantesque labyrinthe combinatoire. Ils veulent savoir : combien de grilles (ou « mansions ») uniques et complètes existent réellement ? Et plus important encore, combien d'entre elles sont véritablement différentes si l'on ignore des choses comme la rotation de toute la maison ou le changement de nom des meubles ?

Pour résoudre cela, les mathématiciens utilisent un outil puissant appelé la « théorie des groupes », qui est essentiellement l'étude de la symétrie. Considérez la symétrie comme un miroir magique : si vous faites pivoter un flocon de neige ou si vous retournez une carte à jouer, l'objet peut paraître différent pendant un court instant, mais il reste fondamentalement le même. Dans le monde du Sudoku, si vous pouvez transformer une grille en une autre en changeant les chiffres (comme transformer tous les 1 en 2 et tous les 2 en 1) ou en mélangeant les lignes et les colonnes, ces deux grilles sont considérées comme des « jumelles ». La grande question était de savoir : si nous ne comptons que les grilles uniques, non jumelles, combien y en a-t-il ? Pendant des décennies, la réponse a été trouvée par la puissance de calcul brute des ordinateurs, mais les étapes pour y parvenir ressemblaient davantage à un amas désordonné de ruses qu'à un chemin clair et logique.

La Découverte de l'Article : Trouver le Motif Caché

Dans cet article, Fernanda Pereira porte un regard neuf sur une partie spécifique et délicate du problème de comptage du Sudoku. Elle se concentre sur le « premier bandeau » de la grille — les trois premières rangées. Des chercheurs précédents, Felgenhauer et Jarvis, avaient déjà effectué le gros du travail pour trouver qu'il existe exactement 44 types distincts de ces bandeaux de rangées supérieures. Cependant, ils étaient arrivés à ce nombre de 44 en appliquant une chaîne longue et compliquée de cinq réductions différentes. C'était comme éplucher un oignon couche par couche, où chaque couche nécessitait une astuce différente et spécifique. Le résultat était correct, mais le nombre 44 semblait accidentel, comme s'il s'agissait d'un arrêt aléatoire sur une longue route sinueuse sans signification profonde.

L'article de Pereira soutient que 44 n'est pas un accident aléatoire ; c'est une vérité structurelle fondamentale. Elle propose une nouvelle façon plus propre de voir le problème. Au lieu d'éplucher des couches, elle suggère de regarder la grille de Sudoku à travers une nouvelle lentille : les partitions de colonnes.

Imaginez les trois premières rangées de la grille comme trois boîtes séparées. Dans chaque boîte, les nombres des trois colonnes forment une « équipe » spécifique de trois nombres. Par exemple, dans la première boîte, la première colonne pourrait contenir les nombres {1, 4, 7}, la deuxième {2, 5, 8}, et la troisième {3, 6, 9}. Ce regroupement est appelé une « partition ». L'idée majeure de Pereira est que toute la complexité du bandeau supérieur du Sudoku peut être résumée à une simple liste de ces trois « équipes » de nombres.

Elle traite ces trois équipes non pas comme un ordre strict (Boîte 1, Boîte 2, Boîte 3), mais comme un multiensemble — un sac où l'ordre n'importe pas, mais où les doublons comptent. Si vous avez trois sacs identiques de nombres, c'est une chose ; si vous avez deux sacs identiques et un différent, c'en est une autre. L'article prouve que deux bandeaux de Sudoku sont des « jumeaux » (équivalents) si et seulement si leurs sacs d'équipes de nombres sont les mêmes, même si l'on mélange les nombres (re-étiquetage) ou si l'on échange les sacs.

La Percée du « Calcul Manuel »

La partie la plus excitante de l'article est la façon dont elle compte ces sacs. Au lieu de s'appuyer sur un superordinateur pour vérifier des millions de possibilités pour le résultat final, Pereira utilise un théorème mathématique appelé le Lemme de Burnside. Ce théorème est un raccourci de comptage ingénieux qui permet de déterminer combien de groupes uniques existent en observant combien de choses restent inchangées lorsqu'on applique différentes symétries.

En appliquant ce théorème à son idée de « sac de partitions », elle est capable de dériver le nombre 44 via une formule analytique fermée. Elle décompose le problème en 30 types différents de motifs de mélange de nombres (appelés types de cycles). Pour chaque motif, elle calcule combien de « sacs » restent inchangés. Elle additionne ensuite les résultats de 19 calculs spécifiques non nuls. La somme finale, divisée par un nombre spécifique, arrive exactement à 44.

Cependant, le chemin vers cette formule élégante a nécessité une assistance computationnelle. Bien que la dérivation finale des 44 classes soit un calcul en forme close qui ne nécessite pas d'énumération informatique, l'article note que l'auteure a utilisé des outils d'IA pour aider au développement des arguments mathématiques et a écrit des scripts Python pour effectuer des vérifications computationnelles. Ces scripts ont vérifié de manière indépendante la décomposition des comptes et la somme finale par rapport à des évaluations directes sur toutes les permutations possibles. Cela garantit que la logique « calculée à la main » tient bon face à la réalité de la force brute, confirmant que les 44 classes sont bien le résultat structurel correct.

Il s'agit d'un changement majeur de perspective. L'article argumente explicitement contre l'idée que 44 n'est qu'un sous-produit désordonné d'un long processus de réduction ad hoc. Au lieu de cela, il montre que 44 est le résultat naturel du comptage des manières uniques d'organiser ces partitions de nombres sous les règles de la symétrie.

Une Vision Globale

Bien que l'accent principal soit mis sur les 44 classes du bandeau supérieur, l'article aborde également le compte total de toutes les grilles de Sudoku uniques. Il confirme le nombre précédemment connu de 5 472 730 538 grilles essentiellement différentes (un nombre trouvé par Russell et Jarvis à l'aide d'ordinateurs). La méthode de Pereira ne se contente pas de revérifier ce chiffre ; elle fournit une explication structurelle pour les 44 classes qui constituent le fondement de ce compte plus large.

En résumé, l'article prend un nombre qui ressemblait à un arrêt aléatoire sur un long voyage et révèle qu'il est une destination dotée d'une carte claire et magnifique. Il remplace une chaîne de cinq ruses compliquées par un seul invariant élégant (le multiensemble de partitions) et un seul calcul puissant. Le résultat est la preuve que les 44 classes ne sont pas un accident de calcul, mais une caractéristique fondamentale de l'univers du Sudoku, avec des étapes analytiques finales réalisables à la main et une logique sous-jacente rigoureusement vérifiée par ordinateur.