{"partition": "head_middle", "source_domain": "eljjdx.canalblog.com", "digest": "sha1:GS6CXCA7GHHZ6B3DXXQ4IOIW7JPAOKFQ", "path": "/lustre/fsn1/projects/rech/qgz/uzq54wg/processed_redpajama/base_processing/output/fr/2014-15/000_00004.parquet"}
Choux romanesco, Vache qui rit et intégrales curvilignes
Pendant ce temps, chez les Sudokus
Il est 13h, bonjour à tous, bon week-end. Voici les titres de l'actualité de ce dimanche :- Un week-end de grand froid sur la France. C'est la neige qui a paralysé plusieurs heures des automobilistes sur l'autoroute A26.- Froid, encore : les températures ressenties sont plus faibles que les températures sous abri. Explications, mais sans équations.- Froid toujours : nos envoyés spéciaux en province nous montreront comment est la neige dans les différents coins de la France.- Point sur la fashion week : que nous réservent les créateurs de mode en matière de gants et de bonnets ?- Science : malgré le froid, trois chercheurs ont réussi à déterminer qu'en dessous de 17 chiffres, un sudoku n'a jamais de solution unique.- Enfin, nous terminerons par la météo, en rappelant qu'il neige en hiver.
Ouvrons donc ce sujet science, avec l'exploit du mois dernier : Gary McGuire, mathématicien irlandais, a résolu une énigme datant de plus de dix ans, en découvrant le plus petit sudoku qui existe. Pour cela, il a fallu plus de 7 millions d'heures de calculs sur un superordinateur. Explications.
Il n'existe que trois types de sudokus : ceux qui n'ont qu'une unique solution, ceux qui ont plusieurs solutions et ceux qui n'ont aucune solution. Les premiers sont intéressants, et les autres sont terriblement décevants et ne méritent pas le nom de sudoku (étymologiquement, "chiffre unique").
Marcel Bompré, amateur de sudoku, témoigne : "c'est vrai que c'est décevant quand on ne s'aperçoit qu'au dernier moment que la grille que l'on est en train de remplir possède plusieurs solutions différentes. Surtout qu'il fait froid."
En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile. De tous les sudokus connus, les plus dépouillés ne comportent que 17 chiffres révélés.
Marcel Bompré, amateur de sudoku, témoigne : "un jour, j'ai résolu un sudoku avec seulement 17 chiffres révélés. C'était pas facile. Surtout qu'il fait vraiment froid."
Exemple de sudoku à 17 indices.
Peut-on trouver un sudoku à 16 chiffres ? La question a longtemps été ouverte, jusqu'au 1er janvier 2012. Gary McGuire, aidé de deux collaborateurs, ont regardé attentivement les 6.7 milliers de milliards de milliards de grilles complètes existantes afin de voir s'il était possible de leur retirer plus de 64 chiffres sans les dénaturer. Leur conclusion : il n'existe pas de sudoku à 16 chiffres.
Même pour un ordinateur, vérifier une par une les 6.7×1021 grilles existantes reste quelque chose de très long. Heureusement, il est possible de réduire considérablement le nombre de sudokus à inspecter grâce à un théorème appelé "lemme de Burnside" : deux grilles sont équivalentes si l'on peut passer de l'une à l'autre en permutant les chiffres, les colonnes ou les lignes (on ne peut pas vraiment dire que deux sudokus sont différents si on intervertit les 7 et les 5, par exemple)
Équivalence des sudokus :* permutation des chiffres* permutation des bandes verticales* permutation de colonnes au sein d'une même bande * permutation des bandes horizontales * permutation de lignes au sein d'une même bande* inversion des lignes/colonnes
Ces opérations permettent de réduire à 5500 millions le nombre de grilles à inspecter. C'est mieux, mais ça reste long à faire. Il faut donc y aller finement.
La méthode la moins habile pour résoudre le problème est de prendre une par une les grilles complètes et de tester toutes les sous-grilles à 16 indices pour voir s'il en existe des valides. Problème : y a 33 millions de milliards de façons de garder 16 cases parmi 81. En comptant une minute par grille, il faudrait au moins 10000 ans pour arriver à bout du problème.
Les trois compères y sont donc allé un peu différemment, en cherchant les "ensembles inévitables" dans les grilles complètes. On peut illustrer le concept avec le sudoku suivant :
L'un des quatre indices en jaune est inévitable
En retirant les cases jaunes de cette grille, le sudoku aurait deux solutions différentes : il faut en garder au minimum une parmi ces quatre pour une solution unique. En raisonnant de cette façon, on peut en déduire le nombre minimal d'indices amenant à la grille complète en cherchant ces configurations "inévitables". Le reste est une affaire d'informatique : il faut programmer ce principe de manière satisfaisante pour l'appliquer aux 5.4×109 sudokus pleins. C'est ce que les trois chercheurs ont fait, en inventant un nouvel algorithme, qui pourrait d'ailleurs servir dans bien d'autres domaines de l'informatique. Dans les faits, les calculs ont duré presque un an sur le superordinateur Stokes (mais aurait duré 800 ans sur un ordinateur plus classique).
Marcel Bompré, amateur de sudoku, témoigne : "Pfffiou ! C'est long ! Surtout qu'il neige."
La quête d'un sudoku à 16 chiffres est définitivement terminé, mais le travail mathématique ne l'est pas. Tout comme pour la découverte du nombre de Dieu en juillet 2010, l'approche informatique est trop balourde pour être honnête. Il existe sans doute une approche bien plus fine qui pourrait montrer qu'il n'existe pas de sudoku à 16 indices, ni de Rubik's cube que l'on ne peut résoudre en moins de 21 coups.
Rappelons tout de même l'information principale de la journée : il fait froid en hiver.
Sources :* There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, l'article de McGuire en prépublication sur arXiv.* Mathematics of Sudoku I, où Felgenhauer et Jarvis montrent qu'il existe 6.7×1021 grilles de sudoku.* Mathematics of Sudoku II, où Russel et Jarvis montrent qu'il n'existe que 5.4×109 grilles vraiment différentes.
Posté par El Jj à 13:00 - Commentaires [3] - Permalien [#]
Tags : Actu mathématiques, Informatique, Jeux, Sudoku
Vous aimerez peut-être : Lemme de burnside : exemples et applications Le dieu du cube Il existe 10 types de mathématiciens... 2 699 999 990 000 décimales... Mokshû patamû Made in sinaï Cravate club Just another huffman tree Cliquez plus pour gagner plus (de cookies) Faut-il appliquer la théorie des jeux combinatoire pour le jeu du chou-fleur ?
Commentaires sur Pendant ce temps, chez les Sudokus
C'est beau
C'est beau l'informatique, c'est encore plus magnifique quand la forme de l'article permet une critique sur la stupidité des média Posté par plop, 05 février 2012 à 17:51 | | Répondre
Super article, d'autant plus par ce froid !
Petit oubli cependant : "Il n'existe que trois types de sudokus : ceux [qui] n'ont qu'une unique solution".
Posté par Mr Alabar, 06 février 2012 à 16:28 | | Répondre
Le sudoku ca peut etre dur!
Bonjour, sujet intéressant, merci
"En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile."
C'est une tendance mais vu d'assez loin.
A mon grand étonnement de "mathématicien" j'ai découvert que le sudoku ca peut être dur, il y a de véritables monstres mathématiques d'une espèce sans commune mesure avec les sudokus soit disant diaboliques des journaux.
C'est le cas par exemple de "Easter Monster":
http://sudoku.com.au/blog/jpgfiles/Easter%20Monster%20jpgs/start_blank.jpg
On notera que la grille initiale avec 21 indices est éloignée du 17 limite.
Voici quelques étapes de la solution:
http://sudoku.com.au/sudokutips.aspx?Go=I29-12-1991&category=sudoku
(avec les "Previous blog pages")
Pour d'autres sudokus extrêmes comme celui ci:
http://en.wikipedia.org/wiki/Sudoku_algorithms
Voir en bas "Exceptionally difficult Sudokus"
On remarquera toujours que ceux-ci sont loins des 17 indices minimaux avec autour de 21 indices.
J'encourage fortement les amateurs à tenter le "Easter Monster" pour bien voir qu'un sudoku ce n'est pas ce qu'on vous fait croire dans la presse Posté par Thomas Cabaret, 13 mars 2012 à 11:41 | | Répondre
« février 2012 »dimlunmarmerjeuvensam 1 2 3 4 56 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2627 28 29 L'intégrale de eljjdx
La dualité. Mesdames et messieurs.
Mokshû Patamû
Made in Sinaï
Cravate club
Just another Huffman tree
24 jours après le Big Bang
Ordre et désordre
2013+1 (Cette nouvelle année est-elle intéressante ? Episode 05)
Calendrier de l'avent
Bézout futé
Indivisibles
De l'humour mathématique
Cliquez plus pour gagner plus (de cookies)
Faut-il appliquer la théorie des jeux combinatoire pour le jeu du chou-fleur ?
Les mathématiques de Futurama [rediffusion]
C@fé des sciences
Tweets de @ElJj
Actu mathématiques
Amusette
Conjectures
Courbes et surfaces
Découpages
Grands nombres
Nombres premiers
Paradoxe
Proba
Question des lecteurs
Théorie des jeux
Topologie
Ces jeux me rappellent tant de souvenirs :p sur Mokshû Patamû
Exactement, cela correspond à la ligne d'horizon sur La dualité. Mesdames et messieurs.
A ce propos, lire l'article BibNum de D. Nordon sur La dualité. Mesdames et messieurs.
Bonjour Article tres interessant et bien sur La dualité. Mesdames et messieurs.
Joli billet. A paraître bientôt sur BibNum un sur La dualité. Mesdames et messieurs.
Les belles sciences que sont les mathématiques ! sur Top 10 des mathématiques religieuses
C'est un article très bien réalisé, avec beaucoup sur La dualité. Mesdames et messieurs.
Il y a un article mathématique intéressant et en sur Mokshû Patamû
Comme toujours, sympathique billet, merci. Ne sur Mokshû Patamû
@Djoe l'indien > Effectivement, 1% des nombres sur Szemerédi, go !
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.
libstat : mesure d'audience pour site web
Annuaire, sciences, sites classés
Blog hébergé par CanalBlog | Plan du site | Blog Science créé le 15/11/2006 | Contacter l'auteur | Signaler un abus