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!
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)
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.
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…
Tu fais la liste des combinaisons pour deux dés à 6 face puis tu enlèves les permutations circulaires...
Vas y, prouve moi que 36 est un multiple de 21...
Pourquoi, parcequ'il existe des transformations identitaires, à savoir pour cet exemple que la permutation circulaire d'un double ne génère pas une nouvelle combinaison.
(sans compter que si tu considère plusieurs type de transformation dans un problème plus complexe, tu peux aussi obtenir via une transformation une combinaison déjà obtenue via une autre transformation)
Alors peux-tu affirmer qu'il que toutes les transformations appliquées à toutes tes combinaisons générent systématiquement une nouvelle combinaisons inédite ?
J'ai pas envie d'aller vérifier, mais à mon avis, rien qu'avec la rotation, on doit avoir des identités où au moins quelques doublons...
@YoshiRyu : j'ai comme l'intuition que la structure du Sudoku t'assure que les transformations considérées ne peuvent pas être des identités.
Par exemple la transposée, il faudrait que le coin de la matrice soit de la forme
A X Y ... X B Z ... Y Z C ... ..
Et ce bloc 3x3 ne peut pas être une permutation, et ne peut donc pas apparaitre dans une grille de Sudoku.
Idem avec les echanges de lignes (et de colonne) dans un même bloc 3x3, avec les echanges de lignes (et de colonnes) de blocs, et donc les symétries horizontales et verticales (par composition), et donc les rotations (par composition entre la transposée et la symetrie).
Pour reprendre ton exemple de d6, ce serait plutot : on veut connaitre le nombre de combinaisons sans doublon.
Plutot que de les lister exhaustivement, on réduit le problème en considerant seulement les cas où le premier dé est strictement inférieur au second, et en considérant la transformation qui consiste à echanger les deux dés (on sait que c'est une transformation sans point fixe sur l'ensemble des combinaisons qu'on cherche, puisqu'il faudrait que D1=D2).
On trouve 15 cas où D1<D2. Et donc, on peut calculer qu'il y a 2x15=30 cas en tout.
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…
Tu fais la liste des combinaisons pour deux dés à 6 face puis tu enlèves les permutations circulaires... Vas y, prouve moi que 36 est un multiple de 21...
Il ne s'agit pas que des permutations circulaires (au nombre de 9 pour les 9 chiffres du Sudoku), mais bien de toutes les 9! permutations… Contrairement aux dés, comme le Sudoku travaille sur des chiffres tous distincts, il n'y a pas de risque de retomber sur des grilles identiques par permutation.
(sans compter que si tu considère plusieurs type de transformation dans un problème plus complexe, tu peux aussi obtenir via une transformation une combinaison déjà obtenue via une autre transformation) Alors peux-tu affirmer qu'il que toutes les transformations appliquées à toutes tes combinaisons générent systématiquement une nouvelle combinaisons inédite ? J'ai pas envie d'aller vérifier, mais à mon avis, rien qu'avec la rotation, on doit avoir des identités où au moins quelques doublons...
Une symétrie horizontale puis verticale équivaut à une rotation à 180°. Je crois que c'est la seule combinaison qui entraine des doublons. Sinon, je t'invite à aller regarder de plus près les méthodes qui ont été utilisées, par exemple, par Felgenhauer, c'est décrit dans son article… Effectivement il n'utilise pas les symétries et rotations, mais plutôt un travail bloc par bloc.
Pour les non-professionnels complets (comme moi) de l'algorithmique, le dernier numéro de Quadrature (n°81) propose un algorithme "naïf" de résolution, et plusieurs améliorations élémentaires fondées sur des raisonnements très simples, ainsi que pas mal d'autres choses très intéressantes.
scand1sk dit:Une symétrie horizontale puis verticale équivaut à une rotation à 180°. Je crois que c'est la seule combinaison qui entraine des doublons.
C'est la seule combinaison qui entraine des doublons pour une matrice quelconque, mais là on parle d'un grille de sudoku, où les même élément se répètent tous 9 fois, donc je trouve présomptueux d'affirmer qu'il n'existe aucune serie de transformations qui ne donne ne doublon en considérant toutes les combinaison de départ et toutes les transformations possibles... (même en virant la rotation à 180° et aussi celle à 270 en fait, parceque'une rotation à 270° se retrouve également en faisant une symetrie en X et en Y et une rotation de 90°)