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°)