Une grille de sudoku se fabrique en effaçant des chiffres d’une « grille complète » qui sert de solution. Mais combien existe-t-il en tout de grilles complètes qui respectent la règle ?

288 grilles en 4×4

Prenons la plus petite grille, le 4×4 (blocs de 2×2, chiffres de 1 à 4). Voici un exemple.

112233441234341221434321

Chaque colonne, chaque ligne et chaque bloc contient une fois chacun des chiffres de 1 à 4. En comptant une à une, par ordinateur, toutes les grilles de ce genre, on en trouve 288.

Fixer la première ligne facilite le comptage

On peut réduire le travail sans tout compter.

Si, dans une grille complète, on renomme les chiffres, par exemple en échangeant 1 et 2, on obtient encore une grille complète. Une grille dont la première ligne est « 2 1 3 4 » devient, en échangeant 1 et 2, une grille dont la première ligne est « 1 2 3 4 ». Il suffit donc de

  • compter seulement les grilles dont la première ligne est « 1 2 3 4 »,
  • puis de multiplier par le nombre de façons d’ordonner la première ligne (4×3×2×1 = 24).

Voilà de quoi trouver le total. En 4×4, il y a 12 grilles dont la première ligne est « 1 2 3 4 », et 12×24 = 288.

28 200 960 grilles en 6×6

C’est la grille du 6×6 Mini de l’app NumberPlace, avec des blocs de 2 lignes sur 3 colonnes. Avec la même méthode, en fixant la première ligne à « 1 2 3 4 5 6 », on en compte 39 168. Il y a 6×5×4×3×2×1 = 720 façons d’ordonner la première ligne, donc

39 168 × 720 = 28 200 960

soit 28 200 960 grilles. C’est environ 100 000 fois plus qu’en 4×4.

Environ 6,67 × 10²¹ grilles en 9×9

Le nombre de grilles complètes en 9×9 est de

6 670 903 752 021 072 936 960

soit environ 6,67 × 10²¹ (à peu près 6,67 trilliards). Il a été obtenu au milieu des années 2000, en répartissant les grilles en bandes et en blocs, puis en comptant les cas par ordinateur. Même en comptant cent millions de grilles par seconde, il faudrait plus de 2 millions d’années.

Ce total contient beaucoup de grilles qui ne diffèrent que par une rotation, un retournement ou un renommage des chiffres. Si l’on considère comme identiques celles qui ne diffèrent que par ces changements d’apparence, il en reste environ 5,5 milliards.

Il y a encore plus de grilles à résoudre

À partir d’une seule grille complète, on peut fabriquer plusieurs grilles à résoudre en effaçant les chiffres de différentes façons. L’app NumberPlace crée à chaque fois une grille complète à la volée, puis efface des chiffres pour en faire une grille à résoudre (Comment on fabrique un sudoku). Vous avez très peu de chances de tomber deux fois sur la même.

Combien de chiffres faut-il laisser pour que la solution soit unique ? La réponse est dans Combien d’indices au minimum ?.