Répondre à la discussion
Affichage des résultats 1 à 20 sur 20

sudoku & dénombrement



  1. #1
    fderwelt

    sudoku & dénombrement

    Un petit problème que je me suis posé, mais que je n'ai pas encore résolu. C'est juste pour s'exercer les boyaux de la tête...

    Combien y a-t-il de grilles valides de Sudoku?

    Autrement dit, combien de grilles 9x9, avec chaque chiffre (de 1 à 9) une fois et une seule sur chaque ligne, chaque colonne, et dans chaque bloc de 3x3 cases?

    Je serais curieux de voir comment d'autres que moi abordent la question. Parce que pour l'instrant, je n'ai que la méthode bestiale: on colle un 1 en haut et à gauche, ce qui interdit ce 1 dans la 1ère ligne, la première colonne, et le 1er bloc 3x3. Puis on cherche à coller le 1 dans le 2ème bloc, et ainsi de suite... puis pareil avec les 2, etc... C'est boeuf, hein?

    P.S. - évidemment, si on a une grille valable, toutes les 9! grilles obtenues en permutant les chiffres sont encore valables. C'est pour ça qu'on peut essayer de caser les 1, puis les 2, etc.

    Bon amusement!

    -- françois

    -----


  2. Publicité
  3. #2
    Jean-Luc P

    Re : sudoku & dénombrement

    Une grille de sudoku n'est pas complètement remplie : pour uen grille remplie, il y a plusieurs moyens a priori de disposer les trous pour avoir une unique solution : c'est un facteur multiplicatif non négligeable.

    Sinon dans le pour la Science de décembre Delahaye traite de cela dans sa chronique mathématique.
    Jean-Luc
    La violence est le dernier refuge de l'incompétence.
    Salvor Hardin

  4. #3
    fderwelt

    Re : sudoku & dénombrement

    Oh, pardon. Je voulais dire, combien e grilles _complètement_ remplies... après, choisir quels chiffres on révèle dans l'énoncé, c'est un autre problème!
    Je ne m'intéresse qu'au pur dénombrement, ça fait un exo marrant.
    Je vais regarder dans Pour la Science si j'arrive à le trouver.

    A++

    -- françois

  5. #4
    yat

    Re : sudoku & dénombrement

    Pour simplifier le problème des permutations, j'aurais plutôt songé à remplir la première ligne avec les neuf chiffres dans l'ordre croissant et de ne dénombrer que pour la suite. Il restera à multiplier par 9! et à éliminer les symétries.

    Pour s'engager dans une piste, je pars donc d'une grille ou la première ligne est donnée. Je cherche à remplir la deuxième ligne. Pour le premier carré, j'ai 6*5*4 possibilités. Pour le deuxième, ce n'est pas si simple : Par exemple, si les trois chiffres que j'ai mis dans le premier carré sont ceux de la première ligne, deuxième carré, alors je suis obligé de remplir la deuxième ligne deuxième carré avec les trois chiffres de la première ligne troisième carré, sinon je ne pourrai pas les mettre ailleurs. Si au contraire j'ai mis ceux du troisième carré de la première ligne, Il ne me reste plus pour le deuxième carré que les trois chiffres du premier carré de la première ligne. Sauf erreur de ma part, quand la situation est un mélange de ces deux extrèmes les limitations sont les mêmes. En remplissant la deuxième ligne j'ai donc 6*5*4 possibilités pour le premier carré, 3*2 pour le deuxième et 3*2 pour le troisième. Aux permutations près, on a donc pour l'instant 4320 manières de remplir les deux premières lignes.
    Pour la troisième ligne, il ne reste plus que l'ordre des chiffres au sein de chaque carré, ce qui multiplie par 3*2 pour chaque carré et nous amène à 399120 possibilités. Pour la suite, je pense que les facteurs vont très vite se ramener à 1, mais ça va devenir compliqué parce que les conditions vont devenir de plus en plus difficiles à cerner.

    D'autres questions me tracassent à propos de ce jeu :

    Si on permute deux lignes du même groupe, ou deux groupes de trois lignes, on obtient une grille différente mais toujours valable, et qui se résoud exactement avec le même raisonnement. En ajoutant à ça les symétries et les permutations, je me demande si toutes les grilles peuvent se ramener à un modèle unique par combinaisons de ces transformations. Et sinon, combien de "classes" de grilles existe-t-il ?

    Est-ce qu'on peut transformer dans une grille les lignes en carrés et réciproquement de manière à ce que les contraintes entres les différentes cases (agencées différemment) restent les mêmes ? Je n'y arrive pas pour l'instant, mais si c'était possible ça ferait encore une transformation qui permet de passer d'une grille à une grille équivalente.

    Quel est le nombre minimal de chiffres qu'il faut avoir au départ pour que la grille soit soluble ?

  6. #5
    matthias

    Re : sudoku & dénombrement

    Citation Envoyé par yat
    Est-ce qu'on peut transformer dans une grille les lignes en carrés et réciproquement de manière à ce que les contraintes entres les différentes cases (agencées différemment) restent les mêmes ? Je n'y arrive pas pour l'instant, mais si c'était possible ça ferait encore une transformation qui permet de passer d'une grille à une grille équivalente.
    Question intéressante. Ca m'a pas l'air évident quand même ...

    Citation Envoyé par yat
    Quel est le nombre minimal de chiffres qu'il faut avoir au départ pour que la grille soit soluble ?
    0
    Mais j'imagine que quand tu parles de grille soluble, tu veux dire qu'elle admet une unique solution ?

  7. A voir en vidéo sur Futura
  8. #6
    yat

    Re : sudoku & dénombrement

    Citation Envoyé par matthias
    0
    Mais j'imagine que quand tu parles de grille soluble, tu veux dire qu'elle admet une unique solution ?
    En effet, pour moi c'est implicite : je ne remplis une case d'une grille que quand je suis sur que cette case ne peut contenir que cette valeur. S'il y a plusieurs solutions je ne peux pas la résoudre.

  9. Publicité
  10. #7
    frisco

    Re : sudoku & dénombrement

    en partant d'une grille donne on a :

    9! (permutation possible ( permutation de chiffre ).

    On peut inverser les lignes ou colonnes selon certaines regles.

    on peut permuter les lignes 1 , 2 ,3 par un combinaison entre elle ( 6) possible
    de meme avec les lignes 4, 5, 6 et 7 ,8 ,9
    et pareil pour les colonnes.

    pareil pour les block ( 1,2,3 ) (4, 5 ,6 ) ( 7, 8 ,9)
    soit n= 9! * 6^8 permuation possible.
    (Ps je ne sais pas s'il y a des combianisons non couverte (j'en sais rien ) ou , couverte + d'une fois ( je pense pas ))
    Dernière modification par frisco ; 06/02/2006 à 15h00.

  11. #8
    frisco

    Re : sudoku & dénombrement

    en partant d'une grille (Complete )donne on a :

    9! (permutation possible ( permutation de chiffre ).

    On peut inverser les lignes ou colonnes selon certaines regles.

    on peut permuter les lignes 1 , 2 ,3 par un combinaison entre elle ( 6) possible
    de meme avec les lignes 4, 5, 6 et 7 ,8 ,9
    et pareil pour les colonnes.

    pareil pour les block ( 1,2,3 ) (4, 5 ,6 ) ( 7, 8 ,9)
    9! * 6^8

  12. #9
    yat

    Re : sudoku & dénombrement

    Citation Envoyé par frisco
    9! * 6^8
    On pourra ajouter les rotations.
    Sinon, le problème c'est qu'en permutant des numéros et en changeant l'ordre des lignes ou des colonnes, on doit pouvoir retomber sur la grille de départ.

  13. #10
    supernico999

    Re : sudoku & dénombrement

    Pour information, le nombre que vous cherchez est 9!.722.27.27704267971 (ce dernier facteur étant premier).
    Ca a été démontré par Bertram Felgenhauer et Frazer Jarvis en 2005.

  14. #11
    frisco

    Re : sudoku & dénombrement

    Citation Envoyé par yat
    On pourra ajouter les rotations.
    Sinon, le problème c'est qu'en permutant des numéros et en changeant l'ordre des lignes ou des colonnes, on doit pouvoir retomber sur la grille de départ.
    Je ne pense pas que les rotations puissent marche

    concernant le fais de retombe sur la meme combinasion

    cela n'est pas possible en permutant seulement les chiffres.

    en permutant les lignes (ou les colonnes) seulement cela ne devraient pas être possible.

    dans les autres cas , je n'ai pas reflechis .

  15. #12
    matthias

    Re : sudoku & dénombrement

    Il faut lire : . Un copier-collé un peu hâtif peut-être ?
    Pas mal d'infos et des liens sur Wikipedia

  16. Publicité
  17. #13
    yat

    Re : sudoku & dénombrement

    Citation Envoyé par frisco
    Je ne pense pas que les rotations puissent marche
    Qu'est-ce que tu veux dire ? Tu as une grille valide, tu la tournes de 90 degrés dans le sens des aiguilles d'une montre, c'est une grille valide, non ?
    Citation Envoyé par frisco
    concernant le fais de retombe sur la meme combinasion
    cela n'est pas possible en permutant seulement les chiffres.
    Ca tombe sous le sens... si tu remplaces un chiffre par un autre, tu as changé ta grille
    Citation Envoyé par frisco
    en permutant les lignes (ou les colonnes) seulement cela ne devraient pas être possible.
    Ca tombe également sous le sens : si tu changes l'ordre des colonnes, ta grille ne peut pas être identique
    Citation Envoyé par frisco
    dans les autres cas , je n'ai pas reflechis .
    Moi non plus, je me suis contenté de faire le test : Je construis une grille valide, de manière très méthodique :

    1 2 3 4 5 6 7 8 9
    4 5 6 7 8 9 1 2 3
    7 8 9 1 2 3 4 5 6
    2 3 1 5 6 4 8 9 7
    5 6 4 8 9 7 2 3 1
    8 9 7 2 3 1 5 6 4
    3 1 2 6 4 5 9 7 8
    6 4 5 9 7 8 3 1 2
    9 7 8 3 1 2 6 4 5

    Ensuite j'insère les trois blocs de droite à gauche :

    7 8 9 1 2 3 4 5 6
    1 2 3 4 5 6 7 8 9
    4 5 6 7 8 9 1 2 3
    8 9 7 2 3 1 5 6 4
    2 3 1 5 6 4 8 9 7
    5 6 4 8 9 7 2 3 1
    9 7 8 3 1 2 6 4 5
    3 1 2 6 4 5 9 7 8
    6 4 5 9 7 8 3 1 2

    Et enfin, j'ajoute 3 à chaque case, et avec un modulo 9 ça me donne :

    1 2 3 4 5 6 7 8 9
    4 5 6 7 8 9 1 2 3
    7 8 9 1 2 3 4 5 6
    2 3 1 5 6 4 8 9 7
    5 6 4 8 9 7 2 3 1
    8 9 7 2 3 1 5 6 4
    3 1 2 6 4 5 9 7 8
    6 4 5 9 7 8 3 1 2
    9 7 8 3 1 2 6 4 5

    C'est à dire la grille de départ. Donc, avec une permutation de blocs et une permutation de chiffres, je retombe sur la grille de départ. Donc le multiplicateur 9!*68 n'est pas bon.

  18. #14
    martini_bird

    Re : sudoku & dénombrement

    Salut,

    j'étais tombé sur cet article où ils expliquent comment ils utilisent l'informatique pour terminer l'énumération.

    Cordialement.

    PS: pour ceux que ça intéresse, j'ai programmé avec mes petites mains un solveur de sudoku en java.
    Il est pas encore tout à fait au point mais mis à part les grilles diaboliques où il faut l'aider un peu, il résoud toutes les grilles.
    Dernière modification par martini_bird ; 06/02/2006 à 15h54.

  19. #15
    frisco

    Re : sudoku & dénombrement

    je ne voyer pas les rotation ( je ne pense pas ).

    concernant l'exemple que tu donne ,
    il faudrait voir pour plusieurs grilles de depart , si on retombe sur la grille source.
    la grille que tu as pris pour exemple a bcp de redondance

    si tu prend l'intersection d'une colonne et d'un bloc tu n'as que 3 "couple" de valeurs possible ( 2, 5, 8 ) , ( 3, 6,9) , (1,4,7).
    de meme avec tes lignes (1, 2 ,3) ,(4, 5, 6) ,(7 ,8 ,9).

    si on prends une grille classique sans redondance , est ce cas est possible ?.

    faire un tour de 180 degre ( 2 rotation )
    , c'est equivalent a premuter les lignes et colonnes ( 1, 3 ) , (7, 9 ) puis ((1,2,3),(,7, 8,9))).

    donc la rotation double le nombre de combinaison possible (s'il n'y pas de de doublons ))

  20. #16
    yat

    Re : sudoku & dénombrement

    Citation Envoyé par frisco
    concernant l'exemple que tu donne ,
    il faudrait voir pour plusieurs grilles de depart , si on retombe sur la grille source.
    la grille que tu as pris pour exemple a bcp de redondance
    Certes, mais c'est une grille valide. Et pour cette grille en particulier, une permutation de blocs et une permutation de chiffres donnent le même résultat. Il existe donc des grilles pour lesquelles des permutations de blocs et des permutations de chiffres donnent une grille identique. Ca suffit pour affirmer que le facteur 9!*68 est faux.
    Citation Envoyé par frisco
    si on prends une grille classique sans redondance , est ce cas est possible ?.
    Il y a un bon moyen de le savoir : maintenant que j'ai déblayé le terrain avec une grille facile, à toi d'essayer sur une grille quelconque
    Citation Envoyé par frisco
    faire un tour de 180 degre ( 2 rotation )
    , c'est equivalent a premuter les lignes et colonnes ( 1, 3 ) , (7, 9 ) puis ((1,2,3),(,7, 8,9))).

    donc la rotation double le nombre de combinaison possible (s'il n'y pas de de doublons ))
    Tout à fait. En gros la seule rotation à prendre en compte est par exemple la rotation de 90 degrés dans le sens horaire, les autres reviennent à une symétrie.

    Mais là encore, il existe un ensemble de grilles pour lesquelles une rotation de 90 degrés et une permutation de chiffres aboutit au même résultat. C'est le cas pour ma grille de tout à l'heure, puisque j'ai commencé par vérifier avec la transposée. Or la transposée, ce n'est jamais qu'une rotation de 90 suivie d'une symétrie.

    Il n'est pas compliqué d'énumérer les transformations que l'on peut appliquer à une grille valide pour obtenir une autre grille valide. On pourra ainsi classer chaque grille dans un ensemble de grilles, basé sur le fait qu'on peut passer d'une grille quelconque d'un ensemble à une autre grille quelconque du même ensemble par une chaine de ces transformations. Le raccourci que tu as pris et que je conteste, c'est de tenter d'énumérer le nombre de grilles différentes dans un ensemble, sans autre méthode que de multiplier les transformations possibles entre elles. Pour commencer, les doublons sont à mon avis très complexes à comptabiliser, et ensuite il est probable que ce cardinal varie d'un ensemble à l'autre. Tu le soulignes toi-même en parlat des redondances plus ou moins présentes dans une grille.

  21. #17
    yat

    Re : sudoku & dénombrement

    Pour le sudoku de 4 par 4, il y a 288 grilles !

    Instantané pour X=2, toujours pas touché à la deuxième ligne au bout d'une heure pour X=3, ça serait du NP-complet que ça m'étonnerait pas

  22. #18
    matthias

    Re : sudoku & dénombrement

    Citation Envoyé par yat
    Pour le sudoku de 4 par 4, il y a 288 grilles !
    En regardant vite fait à la main, j'en trouve 384, en aurais-je compté certaines plusieurs fois ?

    [EDIT, ah ben non, j'ai compté des grilles invalides ]
    Dernière modification par matthias ; 06/02/2006 à 18h27.

  23. Publicité
  24. #19
    frisco

    Re : sudoku & dénombrement

    j'ai reflechis a un point par rapport au denombrement

    quelque que soit la permutation que l'on fait , lle nombre de redondance est le meme
    le nombre de redondance va de 0 a 2 *9 *3 soit 54 ( exemple donné plus aux)
    on n' a donc un nombre de combianison possible qui est tres different en fonction du nombre de redondance

  25. #20
    yangzb

    Re : sudoku & dénombrement

    Bjr,
    si une grille peut être obtenue par une permutation simple (permutation des 9 symboles 9!;
    permutation des lignes parmi les 3 lignes du Haut, du Milieu ou du Bas 3!*3!*3!;
    permutations des colonnes parmi les 3 colonnes de la Gauche, du Milieu, de la Droite 3!*3!*3!;
    et enfin permutations globales Gauche/Milieu/Droite et Haut/Milieu/Bas : 3!*3!) d'une grille valide.
    Mais si on fixe les grilles de façon que la première ligne soit 123456789 (on peut tjr permuter les symboles pour avoir la première ligne ainsi) du coup le nombre de permutation est diminuer, en suite on peut fixer la deuxieme ligne de sorte que le premier chiffre est tjr inférieur à celui de la 3eme lignes
    ainsi que celui de 4eme lignes < celui de 5e <celui 6e
    et celui de 7eme < celui 8eme < celui de 9eme
    en fin celui de 4eme < celui de 7eme
    on peut peut-être commencer à compter
    Bon courage !

Sur le même thème :

Discussions similaires

  1. Sudoku
    Par rapporteur dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 06/02/2009, 02h45
  2. Les challenges du Sudoku
    Par Argyre dans le forum Science ludique : la science en s'amusant
    Réponses: 5
    Dernier message: 16/11/2006, 08h43
  3. Sudoku
    Par pruno_d_agen dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 27/06/2006, 11h56
  4. Dénombrement & proba
    Par n0unours dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 16/04/2006, 16h19
  5. Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!
    Par jubano dans le forum Mathématiques du supérieur
    Réponses: 17
    Dernier message: 02/01/2006, 08h57