Une grille de sudoku se fabrique de façon que, avec pour seuls indices les chiffres présents au départ, la solution soit unique. S’il y a trop peu d’indices, il y a deux solutions ou plus. Alors, combien d’indices faut-il au minimum ?

17 en 9×9

Dans une grille 9×9, il existe des grilles dont la solution est unique avec 17 indices. Et l’on pense qu’avec 16 indices ou moins, il n’existe aucune grille à solution unique.

Que 16 ne suffise pas a été montré vers 2012, par une méthode qui examine par ordinateur un nombre énorme de cas. Comme il y a environ 6,67 × 10²¹ grilles complètes (Combien de solutions ?), on n’a pas tout simplement tout essayé : on a, dit-on, vérifié en accumulant des astuces pour réduire le domaine à explorer.

Vérifions en 4×4

Dans la petite grille 4×4 (blocs de 2×2, chiffres de 1 à 4), on peut tout examiner. Pour chacune des 288 grilles complètes, on a essayé toutes les façons de choisir les indices, avec ce résultat.

IndicesChoix qui donnent une solution unique
30
425 728

Avec 3 indices, quel que soit le choix, la solution n’est jamais unique. Avec 4, il existe des grilles à solution unique, comme celle-ci.

112233441243

Il n’y a que 4 indices, mais la solution est unique.

112233441234341221434321

Autrement dit, en 4×4, le minimum d’indices est de 4.

Pourquoi il faut 8 chiffres différents parmi les indices

Dans une grille 9×9 à solution unique, les indices contiennent au moins 8 chiffres différents. La raison est simple.

Supposons que les indices ne contiennent ni 7 ni 8. Si l’on échange tous les 7 et tous les 8 dans la grille solution, les indices ne changent pas et la règle reste respectée. On obtient alors deux solutions. Donc, au plus un seul chiffre peut manquer parmi les indices.

Plus d’indices n’est pas forcément mieux

Même avec 17 indices ou plus, selon la façon de les placer, il peut y avoir deux solutions ou plus. Que la solution soit unique ne dépend pas du nombre d’indices, mais de leur disposition.

Et moins il y a d’indices, plus la grille est difficile : ce n’est pas toujours vrai non plus. La difficulté dépend des techniques nécessaires pour résoudre (Le sudoku le plus difficile du monde).

Les grilles 9×9 de l’app NumberPlace ont de 22 à 40 chiffres de départ. Chacune n’a qu’une solution, et l’app ne la propose qu’après avoir vérifié qu’elle se résout jusqu’au bout avec des techniques seulement.