Amorce de Sudoku [était Re: Sugurus]

Le 27/08/2021 à 19:04, robby a écrit :

je ne sais pas si vous connaissez les Sugurus, plus intéressants que les Sudokus: https://krazydad.com/suguru/

A propos des Sudokus, je me suis posé une question que je n'arrive pas à résoudre et ca me frustre.
Dans le cadre d'un amusement retro-informatique je me suis mis en tête de faire un générateur de sudoku "aléatoire". Ce genre d'algo commence par un sudoku résolu puis vide une case au pif, vérifie que la solution est toujours unique (on a un algo pour ca). Si oui on vide une autre case au pif etc. Si non, on y remets la valeur antérieure et on retire une nouvelle case à éliminer. Quand on ne peut plus retirer de cases on a un Sudoku vrai (c'est à dire à solution unique) avec un certain nombre de cases vides.
C'est simple, à condition d'avoir un sudoku résolu au départ.
Pour faire cela on commence par placer quelques chiffres au hasard dans un sudoku vide et on lance une résolution. On se dit que oui naïvement ca va produire un Sudoku tout résolu sans les particularité des constructions de sudoku "automatisées" qui sont elles aussi prévu pour être soluble (https://tinyurl.com/5amuzh4k).
Oui sauf qu'à un moment on tombe sur ce genre de configurations:
..1 ... .1.
C'est à dire une ligne avec deux fois le même chiffre, donc insoluble.
Ok, il faut donc que les chiffres qu'on place en amorce soient tous différents. Là on se dit qu'en plaçant les chiffres 1 à 9 au hasard dans un sudoku vide, il sera forcément soluble, oui ?
Non! Car on peut tomber sur cette configuration:
123 456 78.
... ... ..9
... ... ...
dans laquelle la case en haut à droite ne peut plus rien contenir.
Ah oui, dans ce cas là oui, forcément. Bon ben c'est parce que 9 chiffres distinct contraint trop le problème. Essayons alors avec 8 ou 7 chiffres distincts alors. Ca devrait marcher, là.. non ?
Et bien non ca ne marche pas toujours car on a cette configuration qui est possible avec 7 chiffres distincts:
093 000(000)
000 000 250
000 000 761
Dans laquelle on doit remplir les 3 cases entres parenthèse avec seulement les chiffres 4 et 8, ce qui est aussi impossible.
Donc une amorce avec 9, 8 ou 7 chiffres distinct n'est pas toujours possible. Qu'en est il avec 6 ? Et bien je sais pas, d'où ma question posée à vos éminents cerveaux:
Quel est le plus petit nombre Z de chiffres différents que l'on peut mettre dans une grille de Sudoku vide et qui soit impossible à résoudre.
Nota: ici contrairement aux sudoku où l'on exige l'unicité, ici je cherche juste s'il existe pas de grille pleine respectant les contraintes du Sudoku qui s'appuie sur ces chiffres d'amorce.
Je ne sais pour l'instant que Z>=7, mais peut-on le baisser ? Si oui un contre-exemple serait sympa. Si non comment le prouver ?
sam (je sens que ca n'est pas simple)