[News] La résolution des Sudoku, une affaire de couleurs…

Message par **Michel** » 09/06/2007 - 0:00:38

Si vous vous êtes déjà trouvé bloqué devant un problème de Sudoku, vous avez peut-être imaginé que l’énigme n’avait pas de solution, ou, lorsque finalement vous en résolviez un, que votre solution n’était pas forcément la seule. Ces questions et d'autres sont explorées dans l'article Sudoku Squares and Chromatic Polynomials d’Agnes M. Herzberg et M. Ram Murty, paru dans l’édition de juin-juillet des Notes de l’AMS (American Mathematical Society) dans lequel les auteu...

Message par **fffred** » 09/06/2007 - 0:38:09

marrant je me suis déjà posé ces questions, mais je savais pas que c'était aussi compliqué à résoudre :fada:

xeter · Message par **xeter** » 09/06/2007 - 9:15:35

Et on peut diagonaliser un Sudoku, ou sinon le trigonaliser...
^^ Un Spé maths qui vient de finir les cours

Ze Venerable · Message par **Ze Venerable** » 09/06/2007 - 17:56:36

sympa...
par contre ce passage :

Aussi le nombre minimum (d'entrées) (tel qu'il n'y ait qu'une seule solution ?) est au plus 17.

n'est pas en contradiction avec l'exemple du Sodoku à 29 entrées et 2 solutions?

euh · Message par **euh** » 09/06/2007 - 18:14:16

Ca signifie que les sudokus n'ayant qu'une solution ont un nombre d'entrées supérieur à 17 mais pas que les sudokus ayant un nombre d'entrées supérieur à 17 n'ont qu'une solution.

Pour plus de détails: http://www.ams.org/notices/200706/tx070600708p.pdf

Ze Venerable · Message par **Ze Venerable** » 09/06/2007 - 19:02:19

ok, merci!

PourNotreMonde · Message par **PourNotreMonde** » 09/06/2007 - 20:31:32

Ca signifie que les sudokus n'ayant qu'une solution ont un nombre d'entrées supérieur à 17 mais pas que les sudokus ayant un nombre d'entrées supérieur à 17 n'ont qu'une solution.

Ca veut pas dire grand chose ça... c'est contradictoire euh

Message par **Michel** » 09/06/2007 - 21:02:51

PourNotreMonde a écrit :
Ca signifie que les sudokus n'ayant qu'une solution ont un nombre d'entrées supérieur à 17 mais pas que les sudokus ayant un nombre d'entrées supérieur à 17 n'ont qu'une solution.

Ca veut pas dire grand chose ça... c'est contradictoire euh

La phrase d'euh n'est pas contradictoire.

17 est bien actuellement le nombre minimum d'entrées nécessaires pour qu'une grille n'ait qu'une solution. De 17 à 80 entrées il existe des grilles à solution unique.
On n'a actuellement pas trouvé de grille à solution unique pour 16 entrées, 15 ... etc.

Et de facon indépendante et donc non contradictoire, des grilles à plus de 17 entrées peuvent avoir plusieurs solutions.

byblo · Message par **byblo** » 10/06/2007 - 4:02:46

En bref, le message subliminal de la news est : "jouez à OXO, ça prends moins la tête"

J-B · Message par **J-B** » 11/06/2007 - 12:39:14

<<
Par exemple, ils démontrent que le nombre de façons différentes d'étendre une coloration partielle est donné par un polynôme. Si la valeur de ce polynôme est zéro pour un Sudoku donné, alors le puzzle n'a aucune solution ; si la valeur est 1, le puzzle n’a qu’une solution ; et ainsi de suite.
>>

Ce passage n'a pas de sens. En fait les auteurs montrent (sauf erreur, j'ai lu rapidement) la chose suivante :

On considère un problème plus général. On ne se limite plus à 9 symboles (les chiffres de 1 à 9). Je note S le nombre de symboles autorisés. Les règles sont : un même symbole ne doit pas apparaître deux fois (ou plus) sur la même ligne, sur la même colonne ou dans le même carré. Le cas usuel est le cas S=9.

On se donne une grille partiellement remplie. On note U le nombre de symboles différents apparaissant dans la grille (attention, il ne s'agit pas du nombre d'entrées). On a U inférieur ou égal à S.

Alors le nombre de solutions est P(S) où P est un polynome ne dépendant que de la grille partiellement remplie. Pour le cas usuel, on ne s'intéresse qu'à P(9) qui n'est guère qu'un entier !

Pour les personnes intéressées, on trouve facilement l'article sur internet en tapant dans google le nom des auteurs.

--

Par rapport à la phrase qui semble poser des soucis.

1) Il existe (on a pleins d'exemples) une grille à 17 entrées qui admet une unique solution.
2) On ne sait pas s'il existe des grilles à 16 entrées (ou moins) qui admettent une unique solution.

(Si j'ai bien compris...).

Ze Venerable · Message par **Ze Venerable** » 11/06/2007 - 19:55:27

Salut!
j'avoue que j'arrive pas à voir la différence entre ton explication et celle de celle de t-s... ça me déprime

PourNotreMonde · Message par **PourNotreMonde** » 11/06/2007 - 20:05:06

Enfin moi je trouve qu'un jeu tel le sudoku aurait dû faire son apparition bien avant... ca m'étonne que ce soit si "nouveau", mais en tout cas des millions de petits et grands se sont laissés prendre au jeu

J-B · Message par **J-B** » 11/06/2007 - 20:19:15

Ze Venerable a écrit :Salut!
j'avoue que j'arrive pas à voir la différence entre ton explication et celle de celle de t-s... ça me déprime

De quelle explication parles-tu ?

Ze Venerable · Message par **Ze Venerable** » 11/06/2007 - 21:30:27

ta 1é j-b, qui est correctement résumée je trouve par l'extrait que tu cites

J-B · Message par **J-B** » 11/06/2007 - 21:57:31

Le passage en question n'a pourtant pas de sens. Je le recite ici.

<<
Par exemple, ils démontrent que le nombre de façons différentes d'étendre une coloration partielle est donné par un polynôme. Si la valeur de ce polynôme est zéro pour un Sudoku donné, alors le puzzle n'a aucune solution ; si la valeur est 1, le puzzle n’a qu’une solution
>>

Le nombre de façons différentes d'étendre une coloration partielle est un nombre entier. Ca ne peut donc pas être un polynome. Il y a donc quelque chose à corriger et la correction ne me semble pas si évidente. Il est raisonnable d'imaginer qu'il s'agit de la valeur d'un certain polynome en un certain réel. Mais sans plus de précision l'énoncé serait est alors complètement creux. Voilà quel pourrait être un tel l'énoncé :

Pour toute coloration partielle, il existe un polynome P telle que le nombre d'extention possible est la valeur de P en 0.

C'est une trivialité, étant donné que le polynome peut dépendre de la coloration partielle. Voilà une preuve. Je considère une coloration partielle. Je note P le polynome constant égal au nombre d'exentions possible. Alors le nombre d'extension possible est égal à la valeur de P en 0. Fin de la preuve.

Remarque : on pourrait remplacer 0 par n'importe quoi. On pourrait aussi utiliser des polynomes plus sophistiqués (si N est le nombre de solutions, on pourrait prendre le polynome P=2X+N ou P=X(X+1)+N ou ...).

On voit ainsi que cet énoncé est complètement idiot. C'est une conséquence du fait que pour tout entier, je peux trouver un polynome qui évalué en 0 (ou en 9 ou en ...) vaut l'entier de départ. Ce n'est pas très folichon.

--

L'énoncé est en fait beaucoup plus fort (enfin c'est pas l'énoncé du siècle non plus !). Il dit que, pour une coloration partielle donnée, il existe un certain polynome P, tel que pour tout S supérieur ou égal à U (je reprend les notations de mon précédent message), le nombre de solution est P(S).

Le point non trivial est que le polynome de dépend pas de S.

Si par exemple pour une grille donnée le polynome est X(X+1) et que U=9, alors le nombre de solutions pour le sudoku classique (c'est-à-dire le cas S=9) sera 9(9+1) mais, de plus si S valait 10, le nombre de solutions serait 10(10+1), si S valait 11 ce serait 11(11+1) etc.

Est-ce plus clair ?

Ze Venerable · Message par **Ze Venerable** » 11/06/2007 - 22:52:46

donc tu reproches surtout à l'extrait d'être trop vague et ainsi de passer sous silence une propriété intéressante du sodoku ? Mais il est tout à fait juste non (car il ne me semble pas vraiment qu'y soient confondus le polynôme et les valeurs prises par ce polynôme) ? Mais peut-être n'y ai-je pas réfléchi suffisamment longtemps...

en tout cas merci...

J-B · Message par **J-B** » 12/06/2007 - 7:53:47

Je reproche deux choses :

1) Que ça soit faux (l'article confond bel et bien polynome et valeur d'un polynome en un point : << le nombre de façons différentes [...] est donné par un polynôme >>

2) Que même en corrigeant et en remplaçant "polynome" par "valeur d'un polynome en 9" pour respecter le papier original, alors la propriété est énoncée dans un cas tellement particulier qu'elle devient complètement vide de contenue. Il est complètement inutile de l'énoncer dans un cadre si particulier, ça n'apporte absolument aucune information (c'est ce point qui n'est sans doute pas clair). On peut peut-être méditer l'exemple suivant : la dérivée en 0 de la fonction cosinus est donnée par la valeur en 0 d'un polynome polynome. Chouette...

Je ne sais si c'est plus clair.

wpjo · Message par **wpjo** » 24/12/2009 - 19:40:05

Certes, un sudoku avec 29 chiffres données eut avoir deux solutions.Êt sûrement certains sudokus avec 63 chiffres données (par exemple, toutes les chiffres sont déjà donnéees, sauf les cases pour les chiffres "8" et "9" sont encore blanches) peyuvent avoir deux solutions ! Et très, très probablement, même, certains sudokus avec 73 chiffres données en peuvent avoir deux.

Par contre, le 17 chiffres données et une seule soulution, cela est effectivement très fort.

wpjo

Lysa · Message par **Lysa** » 24/01/2010 - 22:42:21

Certains Sudokus sont plus difficiles à résoudre que d'autres, les plus ardus ne contenant que très peu de chiffres au départ.

Pas forcément, certains sudokus avec plusieurs chiffres peuvent être complexes à résoudre