[Sudoku]
Mon père, amateur de casse-têtes et fan de maths se pose de gave questions existentielles autour du sudoku, et manifestement n’a pas trouvé de réponse sur le net. Du coup, si parmi vous quelqu’un a des réponses aux questions suivantes, ça m’intéresse - attention, une simple réponse sans preuve ou démonstration à l’appui ne vaut pas, on en trouve pas mal, et contradictoires, sur le net…
- Comment est conçu une grille de sudoku ? (à part le bourrinage informatique)
- Comment prouver l’unicité d’une grille ? (à part le bourrinage informatique)
- Combien existe t’il de grilles différentes possibles ?
- Quel est le nombre minimum de chiffre qui doit être donné au départ ?
- Quel est le nombre maximum de chiffres au départ (avec la condition “tous sont utiles”, autrement dit, retirer n’importe quel chiffre supprime l’unicité de la solution).
Voilà, merci d’avance pour vos réponses éclairées.
http://www.mots-croises.ch/Manuels/Sudo … ilites.htm
Le nombre de possibilités, pour une grille de 9 x 9 calculé par Bertram Felgenhauer en 2005, est de 6’670’903’752’021’072’936’960.
Ce nombre est égal à 9! x 722 x 27 x 27’704’267’971. Le dernier nombre (qui par hasard est aussi premier!) est dérivé de calculs de solutions effectués par force brute.
Il semblerait cependant que si l’on tient compte des diverses symétries et déplacements de lignes ou de groupes, de même que des rotations de numéros, qu’il est possible de faire sur une solution, sans en changer la nature, la complexité et la méthode de résolution, il n’existe plus que 5’472’730’538 solutions… ce qui risque de vous prendre encore un peu de temps, avant de devoir recommencer à faire d’anciennes grilles.
La preuve de l’unicité de la solution d’une grille, en revanche, je ne l’ai jamais croisée.
A ma connaissance, il n’y a pas de réponse à ces questions … car les grilles sont conçues par bourrinage informatique 
Jusqu’à preuve du contraire !
La page de wikipédia à ce sujet est très bien documentée :
http://fr.wikipedia.org/wiki/Sudoku
De plus en fin de page il y a des liens vers des livres, des références, des articles et d’autres site web. Un bon point de départ pour répondre à ces questions.
lynkowsky dit:
- Comment est conçu une grille de sudoku ? (à part le bourrinage informatique)
- Comment prouver l'unicité d'une grille ? (à part le bourrinage informatique)
On prouve l'unicité en la resolvant, ça ne prend que quelques centièmes de secondes (avec le programme de M. Kennett disponible en open source, par exemple).
Pour les générer, on crée des grilles aléatoires jusqu'à en trouver une dont la solution est unique (souvent en partant d'une solution et en retirant les chiffres un par un).
C'est l'affaire de quelques dizièmes de secondes. En tout cas, c'est ainsi que sont fabriquées l'immense majorité des grilles publiées.
D'ailleurs la longueur des chaines de déduction nécessaires à sa résolution est un bon indicateur de difficulté.
Pour les plus complexes, comme l'AI Escargot, elles sont censées être construites plus ou moins à la main.
- Combien existe t'il de grilles différentes possibles ?
Cf réponses précédantes. Si ton paternel lit l'anglais, l'article de 2005 de B Felgenhauer est trouvable sur google scholar.
- Quel est le nombre minimum de chiffre qui doit être donné au départ ?
- Quel est le nombre maximum de chiffres au départ (avec la condition "tous sont utiles", autrement dit, retirer n'importe quel chiffre supprime l'unicité de la solution).
Si il y a 7 symboles différents ou moins, c'est sûr qu'il n'y a pas de solution unique (puisque les 2 symboles manquants sont permutables. Donc on a au mieux 2 grilles solutions).
Sinon, on pense que c'est aux alentours de 16 indices minimum. Mais à ma connaissance, c'est une conjecture.
C’est quand même fort que la démo du nombre de solution soit “on a tout essayé et on a compté”. Mon père recherche plutôt une solution “propre” venant de riches calculs combinatoires, ou un truc du genre quoi !
Roswell dit:
Pour les plus complexes, comme l'AI Escargot, elles sont censées être construites plus ou moins à la main.
Ce qui tend à prouver qu'il y a d'autres solutions que la force brute. D'autant que le jeu a l'air relativement ancien selon divers articles (antérieur à l'informatique capable de générer de telles grilles.)
Je réponds au post que tu as supprimé en croyant avoir fait un doublons :
Tu disais que le nombre de combinaison est multiple d’un nombre premier, mais que le fait qu’une fois les solutions similaires (par tranformation) retirées on obtient un nombre inférieur est étranges.
Et bien non, la preuve avec une démonstration très simple :
Je te demande de d’assigner à 3 emplacements 3 éléments parmi la liste suivante (chaque élément étant unique) : A, B et C
Tu as donc 6 combinaison possible (ABC, ACB, BAC, BCA, CAB, CBA) soit 2*3 combinaisons. pourtant, lorsque tu retire les solutions similaire par rotation et par symétrie, tu n’as plus qu’une seul combinaison.
Retirer les transformées ne fait que soustraire des solutions, elle ne divisent pas l’ensemble des combinaison, il n’y a donc pas de raison particulière pour le nombre de combinaisons totales soit un multiple du nombre de combinaisons distinctes par toute transformation de type rotation ou symétrie.
lynkowsky dit:C'est quand même fort que la démo du nombre de solution soit "on a tout essayé et on a compté". Mon père recherche plutôt une solution "propre" venant de riches calculs combinatoires, ou un truc du genre quoi !
Un ordinateur a tout essayé et a compté, c'est parfaitement propre comme solution.
Parfois, ça va plus vite de programmer un algorythme qui calcule bêtement tous les cas et de le faire tourner que de chercher la démonstration mathématique.
Après tout, c'est exactement pour ça qu'on a inventé les ordinateurs à la base ^^
Le Sudoku est une des applications de mes programmes de recherche (j’ai travaillé avec Narendra Jussien, l’auteur d’un livre assez complet sur le Sudoku).
Le Sudoku est une variante du Carré Latin, un problème qui a été pas mal étudié dans les années 1970… C’est un problème NP-complet, ce qui signifie que le temps de résolution de ceux-ci est exponentiel, et que même le « bourrinage informatique » atteint vite ses limites pour les résoudre (du moins pour un carré latin/sudoku de taille arbitraire). Un humain est évidemment encore plus vite largué. Les ordinateurs commencent à avoir énormément de mal à partir des grilles un peu plus grandes que le classique 9×9 (un de mes programmes commençait sérieusement à galérer au delà de 15×15).
Même pour des Sudoku de taille 9, il n’est absolument pas trivial de compter le nombre de grilles possibles (et il faut même commencer par énumérer toutes les symétries et permutations possibles pour que l’ordinateur puisse compter les grilles en temps raisonnable), et le nombre d’indices minimal reste un problème ouvert. Par exemple, pour prouver que 16 indices est un minimum, il faut trouver un Sudoku à 16 indices et tester toutes les grilles possibles à 15 indices en montrant qu’il existe plusieurs solutions à chacun de celles-ci.
lynkowsky dit:C'est quand même fort que la démo du nombre de solution soit "on a tout essayé et on a compté". Mon père recherche plutôt une solution "propre" venant de riches calculs combinatoires, ou un truc du genre quoi !
En fait, l'article de Bertram Felgenhauer de 2005 (:arrow:) montre que la méthode est un peu plus maline qu'une énumération bête et méchante.
Après, faire un complément de démonstration en utilisant un programme, ce n'est pas moins propre qu'avec un papier et un crayon. Ce n'est qu'un outil.
YoshiRyu dit:Retirer les transformées ne fait que soustraire des solutions, elle ne divisent pas l'ensemble des combinaison, il n'y a donc pas de raison particulière pour le nombre de combinaisons totales soit un multiple du nombre de combinaisons distinctes par toute transformation de type rotation ou symétrie.
Euh, ben, si, quand même, ça marche un peu comme ça… Une fois que tu as une solution, tu peux en générer d'autres en permutant les chiffres… Tu peux donc « demander » à l'ordinateur de ne générer qu'une seule de ces permutations, et tu en déduis le nombre total de solutions en multipliant par le nombre de permutations possible à partir de 9 chiffres (ça c'est une formule classique de dénombrement, en l'occurrence 9! (362 880). Ça divise par autant le temps de calcul par ordinateur, de quoi passer de 4 jours à 1 seconde de calcul…
Idem, on peut éliminer les solutions qu'il est possible d'obtenir par symétrie sur les deux axes, par rotation de 90, 180, 270 degrés (hop, on divise encore par 2⁵ = 32 le temps de calcul).
Disons que compter toues les solutions, même de manière maline, ça reste quand même bourrin, et effectivement, comme dit plus haut, on ne peut pas extrapoler. Parce que on pourrait oser espérer une formule, même complexe - surtout que le fait de tomber sur un nombre premier est quand même assez intrigant je trouve… Est-ce le cas avec des grilles plus importantes (par exemple du 16x16 ou du 25x25 ?)
Enfin il ne faut pas s’étonner que des problèmes dont l’exposé est simple soient extrêmement difficiles à démontrer, au point que la force brute soit une solution alternative acceptable.
Pour mémoire, la conjecture de Fermat, dont l’énoncé est on ne peut plus simple et compréhensible à partir du niveau 4e, a nécessité la mise en œuvre de méthodes bien postérieures à celles disponibles à l’époque de Fermat lui-même pour devenir un théorème. Pourtant, jusque là, tous les calculateurs n’avaient jamais réussi à mettre la conjecture en défaut. L’inconvénient étant que les calculs étaient infinis, contrairement au nombre de grilles de sudokus.
Je ne m’étonne pas, je m’y connais suffisamment en maths pour savoir cela. Mais bon, ça coûte rien de chercher à savoir si le problème a été résolu autrement que par la force brute - celle-ci posant quand même toujours le problème de la difficulté d’extrapoler.
Pour avoir aussi un peu cherché des façon propres de trouver les solutions et vérifier leur unicité, je n’ai pas trouvé.
D’un point de vue théorique, ça ressemble beaucoup aux codes correcteurs d’erreur (http://fr.wikipedia.org/wiki/Code_correcteur), c’est à dire qu’on a un message, qui respecte certaines contraintes (ici qu’on doit avoir tous les chiffres de 1 à 9 dans plusieurs espaces, ce qui fait que l’information est en fait très redondante). Enfin, on a un certain nombre d’informations manquantes (ici les trous). Avec en plus l’avantage ici que l’on sait où sont les informations manquantes.
Dans ce domaine, on parle de code 5-correcteur par exemple, s’il est capable de résoudre 5 erreur (c’est à dire ici retrouver la et la seule bonne grille de Sudoku avec 5 trous). La question serait donc de savoir si le sudoku est un code correcteur et si oui, combien de trous on peut faire au max.
Mais hélas, les contrainte du sudoku (tous les chiffres présents) n’est pas vraiment facile à retranscrire en équations (en tout cas je ne l’ai jamais vu) et donc il est pas simple d’utiliser toute cette théorie…
Donc on n’avance pas, mais si tu trouves des math élégantes sur ce sujet, je suis preneur!
Je ne voulais pas être insultant, lynko, hein.
Je suis moi-même tout à fait conscient de mes limites dans ce domaine.
Humilité powaaa !
et à propos du fameux théorème de Fermat, le fantastique livre de Simon Singh “Le dernier théorème de fermat” (tout public) raconte cette épopée mathématique! (http://www.amazon.fr/Dernier-Th%C3%A9or%C3%A8me-Fermat-Simon-Singh/dp/2012789218/ref=sr_1_2?ie=UTF8&qid=1309381568&sr=8-2)
nicotupe dit:D'un point de vue théorique, ça ressemble beaucoup aux codes correcteurs d'erreur
C'est pas faux. Encore qu'ici, il s'agisse plus de correction d'effacements que de correction d'erreurs.
D'ailleurs, ce serait marrant des grilles de sudoku fausses, qu'il faut corriger en changeant le moins de cases possibles (y aurait-il des problèmes avec une solution unique? hum..).
nicotupe dit:
Mais hélas, les contrainte du sudoku (tous les chiffres présents) n'est pas vraiment facile à retranscrire en équations (en tout cas je ne l'ai jamais vu) et donc il est pas simple d'utiliser toute cette théorie...
De mémoire, il me semble avoir vu ça dans : P. Babu, K.Pelckmans, P.Stoica, J. Li, Linear systems, sparse solutions, and sudoku, IEEE Signal Processing Letters, volume 17, 2010.
(mais je n'ai pas accès à ma biblio complète de chez moi, donc je peux pas vérifier là tout de suite)
Roswell dit:nicotupe dit:D'un point de vue théorique, ça ressemble beaucoup aux codes correcteurs d'erreur
C'est pas faux. Encore qu'ici, il s'agisse plus de correction d'effacements que de correction d'erreurs.
Oui mais dans mes souvenirs, pour corriger des effacement, on les remplit au hasard et on résout de la même manière.
Roswell dit:
De mémoire, il me semble avoir vu ça dans : P. Babu, K.Pelckmans, P.Stoica, J. Li, Linear systems, sparse solutions, and sudoku, IEEE Signal Processing Letters, volume 17, 2010.
(mais je n'ai pas accès à ma biblio complète de chez moi, donc je peux pas vérifier là tout de suite)
si ta mémoire ne te fait pas défaut, je suis preneur, si tu as le moyen de me l'envoyer.