{"partition": "head_middle", "source_domain": "www.maxisciences.com", "digest": "sha1:W7IIKPYBYMIUKNDDLXLEKPGNQF7Q7OV5", "path": "/lustre/fsn1/projects/rech/qgz/uzq54wg/processed_redpajama/base_processing/output/fr/2014-15/000_00035.parquet"}
Communauté	Article	A voir aussi
Des chercheurs trouvent une formule pour r�soudre tous les sudokus
Publié par �meline Ferard, le 16 octobre 2012
Deux chercheurs américains sont parvenus à mettre au point un algorithme mathématique qui permet de résoudre tous les sudokus, très rapidement et sans avoir à réfléchir ou observer la grille de chiffres.
5, non... 6 ou 3 ? ou 2 ? Depuis plusieurs années, le sudoku a fait une entrée en force dans les journaux. Alors que ceux-ci publiaient autrefois des mots croisés pour divertir leur lectorat, aujourd'hui, bon nombre d'entre eux ne jurent plus que par ces jeux en forme de grille. Le principe est simple : dans la forme classique, il faut remplir toute la grille en plaçant les chiffres de 1 à 9 de telle manière que deux identiques ne se retrouvent pas sur la même ligne, sur la même colonne ou dans le même carré. Pour cela, il faut partir des symboles déjà inscrits et s'adonner à une série de réflexions et de déductions, permettant de placer au fur et à mesure chaque chiffre. De facile, à moyen puis difficile voire diabolique, il en existe désormais de tous les niveaux. Certains se résolvent ainsi en quelques minutes quand d'autres peuvent prendre plus d'une heure voire plusieurs. Quand on ne parvient pas à le finir, une seule possibilité s'ouvre alors... regarder la solution. Mais des chercheurs de l'université de Notre-Dame aux Etats-Unis ont décidé eux, d'aller chercher plus loin pour résoudre ses casse-têtes chiffrés. En effet, Zoltan Toroczkai et Maria Ercsey-Ravasz ont mis au point un algorithme mathématique capable de résoudre n'importe quel sudoku, très rapidement et sans même avoir à le considérer. C'est dans le cadre de leurs recherches sur l'optimisation et la complexité informatique que les deux scientifiques se sont intéressés à ce jeu défini en 1979 par l’Américain Howard Garns. Selon eux, les fans de Sudoku utilisent un système de "force brutale" pour résoudre les problèmes, combiné avec un fort processus de déduction. Ils essaient alors tous les combinaisons de chiffres possibles jusqu'à ce que la réponse correcte soit trouvée. Mais si cette méthode est efficace, elle représente une grande perte de temps, estiment les chercheurs plutôt fiers de leur trouvaille publiée dans la revue Nature Physics. Un nouveau classement des grilles de 1 à 4 A la place, ceux-ci proposent donc d'utiliser leur algorithme universel qui est entièrement déterminant et arrive toujours à la réponse correcte, ceci en bien moins de temps. Au cours de leurs travaux, les chercheurs ont d'ailleurs constaté que le délai nécessaire pour résoudre le problème avec leur algorithme dépendait de la difficulté de la grille attribuée par ses concepteurs. Ils sont ainsi parvenus à développer une échelle de difficulté des problèmes ou des puzzles. Elle s'étend de 1 à 4 et correspond à peu près à la classification du "facile" à "très difficile" appliquée d'ordinaire. Plus en détail, l'échelle indique notamment qu'une grille de "force" 2 met 10 fois plus de temps à être résolue qu'une de force 1. Ajouté à cela, elle précise également que le puzzle le plus difficile connu aujourd'hui atteint le niveau de 3,6. Mais on ignore aujourd'hui si d'autres grilles encore plus complexes existent. Savoir jusqu'où l'homme peut aller "Je ne m'étais pas intéressés au Sudoku jusqu'à ce que l'on commence à travailler plus généralement sur la classe des problèmes SAT" (boolean SATisfiability problem), qui visent à savoir s'il existe une solution à une série d'équations logiques données, explique Toroczkai. "Dans la mesure où le Sudoku fait partie de cette classe, cela semblait être un bon banc d'essai pour notre résolveur, donc je me suis familiarisé avec. Pour moi, et d'autres scientifiques étudiant de tels problèmes, c'est une question fascinante de savoir jusqu'où les hommes peuvent aller en résolvant des Sudokus et sans faire marche arrière, autrement dit sans faire de choix au hasard, en voyant où cela mène et si cela ne fonctionne pas, en recommençant", ajoute t-il. Reste que pour utiliser l'algorithme des chercheurs, il faut tout de même s'y connaitre un tantinet en mathématiques et qu'au final, les sudokus servent justement à occuper son temps. Quoi de plus satisfaisant que d'achever le remplissage de la grille, après trente minutes d'asticotage mental ? Outre l'intérêt scientifique, pas sûr donc que la résolution instantanée des grilles convainque tant que cela ! Mais les chercheurs estiment que leur algorithme pourrait servir pour résoudre une grande variété de problèmes rencontrés dans l'industrie, l'informatique et même la biologie.
Retrouver la source de toutes les informations gr�ce � un algorithme
Réduire les commentaires
Bouguerra55
-------------------- "il restera toujours un "DEFI"---------------------------
Fredygaga3
salut les guas! est ce que quelqu un pourais me dire pourquoi il n y a pas de maree en mediterannee alors qu elle communique avec l oc�en? '(principe des vases communiquants)
Ottogis
Algorithme ne signifie pas formule. Il faut arr�ter de parler de formule math�matique d�s qu'il est question de math�matiques, c'est vraiment p�nible...
Moich
@Fredygaga3 : Si je ne dis pas de b�tises (l'�tude des mar�es, ce n'est pas ma sp�cialit�, juste de la culture g�n�rale), il y a bien des mar�es en m�diterran�e, mais faibles. Si la communication se fait bien au niveau du d�troit de Gibraltar avec un oc�an qui a un fort marnage, lui, les masses d'eau � transf�rer dans le temps de la mar�e (moins de 6h en incluant l'�tale) sont marginales compte tenu de ce passage relativement �troit (Gibraltar, o� les courants sont sortant en profondeur, mais entrants en surface) et de la masse d'eau de la m�diterran�e. De plus, cette mer qui est assez petite ne profite pas assez des effets de l'attraction lunaire et de l'inertie des masses d'eau, comme peut le subir un oc�an.
Zxvczxc
bull shit
Lune : une �clipse lunaire totale � ne pas manquer le 15 avril
Photos	Ces incroyables colonnes ont �t� r�alis�es � l'aide d'un algorithme
Math�matique