Algorithmes et sudoku

Je pense qu'on a tous déjà fait un sudoku. Là, j'en ai refait un pour la première fois depuis longtemps, et mon cerveau s'est mis à poser des questions à la chaîne.

Le truc que je trouve intéressant, c'est que dès qu'on tombe sur une grille de sudoku, c'est écrit dans les consignes que la grille est garantie d'être résoluble, et de plus, de manière unique. Et je n'ai pas l'impression que c'est facile de démontrer l'unicité de la solution d'une grille "finissable" de sudoku.

Pour justifier qu'elle est garantie d'être résoluble d'au moins une manière, je pense que c'est évident : on part d'une grille complète qui respecte les règles, puis on retire des chiffres. La grille complète dont on est parti est une solution, et je pense que c'est évident qu'on peut effectivement trouver cette solution. Peut-être qu'il faudra tester pendant des heures, mais c'est possible de la retrouver.

Par contre, ce qui m'intéresse beaucoup plus, c'est l'unicité de la solution. Je suppose que les créateurs de grilles de sudoku partent d'une grille complète, et ont une manière de vérifier, à chaque fois qu'ils enlèvent un chiffre, que la grille n'admet toujours qu'une seule solution. Mais comment fait-on pour tester l'unicité, informatiquement ? Il faut bien faire ça avant de proposer la grille à quelqu'un (conscience professionnelle oblige :-D).

Donc, le premier algorithme dont aurait besoin un mathématicien créateur de sudokus, c'est un algorithme qui complète une grille. Ou plutôt, qui cherche toutes les manières de compléter une grille donnée. C'est mieux de faire ça comme algorithme, parce que si l'algorithme trouve plusieurs solutions, c'est que la grille de départ ne contenait plus assez de chiffres.

[Je propose un algorithme qui est garanti d'être fonctionnel, mais qui est totalement idiot et non-optimisé (par flemme de décrire un algorithme qui connait toutes les techniques) : on part de la première case libre, on y place un chiffre $x$ autorisé, puis on refait ça en boucle une tonne de fois jusqu'à avoir soit une grille complète, soit un problème. Si on a un problème, il faut recommencer du début avec la prochaine valeur possible pour $x$, et si on a trouvée une grille acceptable, on la garde en mémoire et on recommence avec $x$ jusqu'à avoir épuisé toutes les possibilités où c'est $x$ dans la permière case libre.]

Mais là, on va avoir des soucis : quel(s) chiffre(s) rajouter pour rendre la grille résoluble ? C'est quasiment certain qu'il y a plusieurs manières de faire ça, donc le mieux ça serait de toutes les trouver (mais comment ?)

Pour ne pas avoir ce genre de problème, on pourrait partir d'une grille complète, retirer un chiffre (plus ou moins au hasard), tester si la grille est encore finissable d'une seule manière, puis en retirer un autre, etc, jusqu'à tomber sur une grille qui n'a plus assez de chiffres pour avoir une solution unique. Mais là, étape par étape, il faudrait retester la résolubilité de la grille, avec le premier algorithme. Ça va devenir très long.

En question subsidiaire... partant d'une grille complétée, quel est le nombre minimal de chiffres qu'il faut laisser dedans pour qu'elle soit résoluble ? On pourrait utiliser ça pour proposer des grilles de difficulté maximale, puis rajouter des chiffres à ces grilles "minimales" pour proposer des grilles plus simples.

Tant qu'on est là... si l'idée est effectivement de partir de grilles complétées, je pense qu'on peut calculer le nombre total de grilles complétées qui existent (tiens, un problème d'algèbre et combinatoire :-D). Et après, pour une grille donnée, détermier toutes les grilles "minimales" qu'on peut en tirer, puisque toutes les autres grilles sont construites sur celles-là. Pour faire ça, il faudrait trouver un algorithme... performant, de préférence, vu le nombre de tests qu'il faut faire.

Quelqu'un ici a déjà réfléchi à ces questions et saurait comment chercher ce que je propose ? Ce qui m'intéresse, dans l'absolu, c'est le raisonnement mathématique, les algorithmes mathématiques, mais s'il y a besoin de partager des programmes, je digère le Python à petites doses :-D.