Je prends une grille de sudoku complétée, et j'efface des chiffres dans certaines cases, les unes après les autres. Combien de chiffres dois-je effacer au minimum pour que la grille devienne ambiguë, c'est-à-dire que l'on puisse la compléter de deux façons correctes différentes (au moins) ? Vous avez le choix de la grille de départ.

Par exemple, sur n'importe quelle grille complète si j'efface une seule case il n'y a toujours qu'une façon de la compléter. Par ailleurs sur n'importe quelle grille je peux effacer complètement toutes les occurences de deux chiffres, disons le 1 et le 2, pour que la grille devienne ambiguë. Donc sur n'importe quelle grille, en effaçant seulement 18 cases j'obtiens au moins deux possibilités. Donc on sait que sur une grille arbitraire, une case ne suffit jamais et 18 suffisent toujours.

Ne lisez pas la phrase suivante si vous voulez chercher un peu.

Je prétends que 3 cases ne suffisent jamais, et que 4 cases suffisent parfois. Reste à voir si 4 suffisent toujours. Bonus : 4 peuvent suffire peu importe la taille de la grille. Exemple de grille ambiguë à 4 :

+-------+-------+-------+
| 2 8 4 | 7 1 3 | 6 5 9 |
| 1 5 3 | 8 9 6 | 7 2 4 |
| 6 7 9 | 2 4 5 | 3 1 8 |
+-------+-------+-------+
| 9 3 8 | 6 2 1 | 4 7 5 |
| 5 . 6 | 4 8 7 | . 9 3 |
| 4 . 7 | 3 5 9 | . 8 6 |
+-------+-------+-------+
| 3 6 2 | 9 7 8 | 5 4 1 |
| 8 4 5 | 1 3 2 | 9 6 7 |
| 7 9 1 | 5 6 4 | 8 3 2 |
+-------+-------+-------+