Bonjour les amis !

Pendant mes vacances, j'ai comme bon nombre de gens joué au célèbre Sudoku. Puis, un peu moins comme bon nombre de gens, j'ai décidé d'essayer d'en créer. Ce n'est pas si compliqué si l'on s'organise, mais là n'est pas la question. Mes aventures m'ont mené à me poser une question qui m'apparaît relativement complexe : combien il y a-t-il de grilles différentes possibles au Sudoku ?

À première vue, je m'étais dit que ça devait pas être si complexe. Mais j'ai vite déchanté.
En effet, il y a une ribambelle de contraintes qui dépassent mes maigres connaissances en statistiques.

J'ai essayé de procéder de bien des manières : par "petits carrés de 9", puis par ligne. Mais dans les deux cas je ne vois pas comment répercuter la diminution des possibilités au fur et à mesure que l'on écrit les chiffres.

Procéder par ligne m'apparaît tout de même être le choix le plus judicieux. Par exemple :

On écrit le 1 dans la case de coordonnées (1, 1) (haut-gauche). Cette action engendre plusieurs choses : le 1 ne peut plus avoir l'ordonnée 1, ni l'abscisse 1, ni apparaître dans le "petit carré de 9" supérieur gauche. Comment dénombrer le nombre de combinaisons restantes dès lors ?

Autre essai : on a <math>\(9^9\)</math> manières de placer les 9 chiffres sur la première colonne. Sur la deuxième, ça se complique directement : on ne peut logiquement plus placer chaque chiffre <math>\(i\)</math> que sur 6 emplacements (puisqu'on perd les 3 situés dans le petit carré où <math>\(i\)</math> apparaît déjà dans la première colonne). Dans la troisième colonne, plus que 3 emplacements possibles, selon le même principe.

Si je me trompe pas, ça nous donne donc : <math>\(9^9 * 9^6 * 9^3\)</math> possibilités rien que pour les trois premières colonnes.

À partir de là, on recommence au niveau des carrés. Mais chaque <math>\(i\)</math> étant déjà placé 3 fois (sur 3 lignes différentes), on perd d'avance 3 cases. On commence donc la quatrième colonne avec <math>\(9^6\)</math> possibilités, et la suivante perd directement 3 possibilités, de nouveau à cause des petits carrés : <math>\(9^3\)</math> combinaisons. Selon ce principe, la sixième colonne aurait <math>\(9^0\)</math> combinaisons. La septième <math>\(9^3\)</math>, la huitième <math>\(9^0\)</math> et la neuvième <math>\(9^{-3}\)</math>, ce qui me semble légèrement... bizarre.

Il m'aurait semblé logique que seule la dernière ligne ait <math>\(9^0\)</math> combinaison possible.

Je doute déjà que mon raisonnement soit bon car dire qu'on a 6 emplacements pour 9 chiffres (traduit par <math>\(9^6\)</math>) n'est pas correct ; on a 6 emplacements différents pour chaque chiffre mais chacun peut bien, à chaque fois, être placé. Comment tenir compte de cette nuance au niveau des combinaisons ?

D'avance merci.

Ceci t'intéressera peut-être.
Sinon, il me semble qu'il y a quelques problèmes dans ton approche dès le début : pourquoi <math>\(9^9\)</math> manières de placer les chiffres sur la première colonne ? Il ne devrait y en avoir que <math>\(9!\)</math>, car l'on compte en fait les permutations de <math>\([|1, 9|]\)</math> (autrement dit, on ne place un même chiffre qu'une fois).

<math>\(6.671*10^{21}\)</math> combinaisons ! C'est de l'ordre de grandeur du diamètre de la galaxie (en mètres).
Ça laisse à ceux qui fabriquent des sudokus de la marge avant de retomber sur les mêmes

Citation : cbasile06

Ceci t'intéressera peut-être.
Sinon, il me semble qu'il y a quelques problèmes dans ton approche dès le début : pourquoi <math>\(9^9\)</math> manières de placer les chiffres sur la première colonne ? Il ne devrait y en avoir que <math>\(9!\)</math>, car l'on compte en fait les permutations de <math>\([|1, 9|]\)</math> (autrement dit, on ne place un même chiffre qu'une fois).

Cet article est super intéressant ! J'ignorais cette histoire de "permutation" mais ça me semble tout à fait logique.

Finalement, l'article explique le reste et même la méthode. Merci !