Cette histoire de sudoku 4x4 m'a semblé d'une pauvreté absolument navrante. Je me demandais dans l'article précédent s'il y avait vraiment tant de choix que ça, s'il n'y avait pas de redondance. En clair, faut-il nécessairement donner 4 chiffres pour que la grille soit déterminée, ou bien 3 suffiraient-ils dans certains cas?

Je me suis alors livré à un petit calcul assez simple, à savoir: combien existe-t-il de grilles différentes? Ma réponse est la suivante: une fois fixé le contenu du quart nord-ouest, il y a deux façons de compléter la ligne du haut. Idem pour la deuxième ligne, la première colonne, et pour la deuxième colonne. Et une fois qu'on a fixé tout ça, le quart sud-est est parfaitement déterminé. Il n'existe par ailleurs aucune contrainte liant les quatre permutations que je viens de citer. On arriva alors à un total de 4!x2⁴ = 384 grilles possibles, qu'on peut réduire par le jeu de symétries mais ce n'est pas ce qui nous intéresse. A titre de comparaison il y aurait paraît-il un peu plus de 5 milliards de grilles 9x9.

La question de départ était: si je prends 4 cases, et si je donne leur valeur, est-ce que je couvre tout? Puis-je m'en sortir en 3 cases? Après quelques réserves d'usage (on ne peut pas mettre n'importe quoi dans n'importe quelle case, tout simplement par respect des règles de base), une première réponse vient assez vite: 4 valeurs données dans 4 cases peuvent donner 4⁴ = 256 grilles différentes, alors qu'il en existe 384. Ceci s'explique assez bien: si l'on choisit de divulguer 4 cases faisant déjà l'objet de contraintes, il faudra en dire plus. Le cas extrême est celui-ci:

1	2	3	4
3	4	_	_
2	1	4	3
4	3	_	_

Il faut impérativement donner une treizième valeur pour terminer la grille...