Combien existe-t-il de possibilités de placement des chiffres dans un sudoku de 9 cases sur9 ?

Bonjour, 

Le sudoku est un jeu qui consiste à placer des chiffres sur une grille. Celle-ci comprend généralement 9 régions de 3x3 cases, soit 81 cases pour toute la grille. Le principe du jeu est simple, aucun chiffre de 1 à 9 ne doit se répéter au sein d'une même ligne, d'une même colonne ou d'une région de 3x3 cases. Si tel est le cas, le puzzle est jugé complet et réussi. 

Contrairement à une croyance largement répandue, le sudoku ne vient pas du Japon mais des États-Unis. Le jeu a été inventé en 1979 par l'architecte américain Howard Garns (1905-1989) sous le nom de "Number Place". Mais le succès du jeu se fit attendre. Ce n'est qu'en 2004, soit 15 ans après la mort de son inventeur, grâce à la publication d'une grille dans les colonnes du quotidien britannique The Times sous le nom de Sudoku, que le jeu va peu à peu se faire connaître du grand public occidental. 

Mais pourquoi ce nom ? 

Il y a quand même un endroit où le jeu a été populaire et ce dès les années 1980 : le Japon. Grâce à Maki Kaji et sa maison d'édition Nikoli le jeu, alors intitulé "Suji wa dokushin ni kagiru", qui signifie "le chiffre doit rester seul" (expression ensuite réduite au premier kanji de la phrase, "doku") connait un engouement certain grâce à la publication régulière d'un magazine consacré au puzzle. Les Français quant à eux ne découvriront le jeu qu'à partir de 2005 avec la parution de premières grilles dans le magazine Sport Cérébral, rapidement suivie de beaucoup d'autres. 

Pour plus d'informations sur le jeu, dont les règles sont inspirées d'une multitude de jeux à chiffres qui l'ont précédé, comme le casse tête du "carré latin", vous pouvez parcourir ces articles : Non, le sudoku ne vient pas du Japon (Le Point, 2023), D’où vient le Sudoku ? (Le JDD, 2021) et Comment le sudoku est devenu le casse-tête le plus populaire du monde (Europe 1, 2020). 

Vous nous interrogez à présent sur le nombre de possibilités, en terme de placements de chiffres et en respectant les règles du jeu sur une grille de Sudoku, sans que celles-ci ne se répètent. 

Nous aurions beaucoup de difficultés à effectuer le calcul par nous-même. Heureusement, deux chercheurs en mathématiques de l'université de Sheffield en Angleterre, Bertram Felgenhauer et Frazer Jarvis sont reconnus pour avoir résolu ce problème. Si vous lisez l'anglais et avez quelques notions en mathématique et en logique, un résumé de leur démonstration en 7 pages puis 4 pages est disponible en ligne. 

La page Wikipédia Mathématiques du Sudoku est un bon support pour comprendre le raisonnement et le calcul des deux mathématiciens. Le résultat final est une formule factorisée : 9!×722×27×27 704 267 9719!×722×27×27704267971, qui donne environ 6,67 × 10²¹ grilles possibles. Soit 6 670 903 752 021 072 936 960 de possibilités de remplir une grille de sudoku 9×9 en respectant les règles. Mais si l’on tient seulement compte des grilles équivalentes par symétrie (permutations de chiffres, lignes, colonnes, etc.) on compte alors 5 472 730 538 grilles non équivalentes. 

Taking the average over all of the 3359232 group elements, we find that the number of essentially different Sudoku grids is 5 472 730 538.

En calculant la moyenne sur l'ensemble des 3 359 232 éléments du groupe, nous obtenons un nombre de grilles de Sudoku fondamentalement différentes égal à 547 273 0538.

traduction avec Deepl.

Source : Mathematics of Sudoku II, Ed Russell, Frazer Jarvis (2006)

On enlève alors par exemple les grilles symétriques (symétrie horizontale, verticale ou diagonale), la permutation des bandes ou des piles entières de blocs 3×3 etc. 

Pour de plus amples explications, nous vous invitons à consulter cet article de blog qui résume bien le calcul en utilisant un tableau. Il suffit d'utiliser la traduction Google pour le lire en français : Il existe 5472730538 grilles de Sudoku essentiellement différentes... et le groupe de symétrie du Sudoku. 

Bonne journée.