sudoku & dénombrement

[invite6de5f0ac]

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

[Jean-Luc P]

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.

[invite6de5f0ac]

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

[yat]

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 ?

[A voir en vidéo sur Futura]

[matthias]

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 ...

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 ?

[yat]

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.

[invite8fe74e77]

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

[invite8fe74e77]

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

[yat]

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.

[invitef45cc474]

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.

[invite8fe74e77]

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 .

[matthias]

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

[yat]

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 ?

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

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

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!*6⁸ n'est pas bon.

[martini_bird]

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.

[invite8fe74e77]

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

[yat]

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!*6⁸ est faux.

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

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.

[yat]

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

[matthias]

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 ]

[invite8fe74e77]

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

[invite23e18616]

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 !