12 juillet 2012

(Erratum) Défi pour cet été : Résoudre le sudoku le plus difficile au monde !

Erratum (12/07/12) : Erreur de grille dans le post initial (par excès de zèle j'ai voulu trouver un modèle avec des références à son auteur, mais ça ne semblait pas être la bonne grille). Merci aux deux personnes qui me l'ont signalé.

Saurez-vous résoudre le Sudoku le plus difficile au monde ? 
Un mathématicien finlandais a mis au point en trois mois une grille de Sudoku avec une unique solution. 

Arto Inkala pourrait bien hanter vos jours et vos nuits. Ce mathématicien finlandais a passé pas moins de trois mois à mettre au point la grille de Sudoku ultime. Une grille si difficile qu'elle n'a qu'une et une seule solution. C'est pourquoi Arto Inkala revendique le titre de Sudoku le plus difficile au monde. Saurez-vous la résoudre ? 

Je précise aux lecteurs d'AlgoRythmes qu'en moins de 10 secondes j'ai trouvé la solution (...enfin, j'ai trouvé le sudoku résolu sur internet) ; donc le but n'est pas de me poster la répose, mais bien d'essayer de résoudre cette grille diabolique !

Source : Metrofrance.com et aisudoku.com via Nicole que je remercie

He declared jubilantly after slaving away with specialised computer software that ran through billions of calculations: “This one is MUCH more difficult. It will take a long time to solve. No one’s managed it yet.”
Like all sudokus, the aim is to fill in the grid so every column, row and group of nine squares contain the digits one to nine.
Players are given just enough numbers to get them started.
Dr Inkala, 41, grinned: “Normal sudoku puzzle logic eliminates the possibilities for each box in two or three steps.
“But this one requires puzzlers to think ahead eight or nine steps at a time — making very long deductions to eliminate the possible candidates for each box.”
The Helsinki University maths wizard unleashed his previous “ultimate” sudoku in 2006.
Experts solved it within 24 hours.
Health firm Efalex — suppliers of brainboosting omega supplements — sponsored his latest creation.
Dr Inkala reckons it would take weeks to solve without any help.
And he warned: “I’m already working on my next one."

5 commentaires:

Dr. Goulu a dit…

Désolé, je ne gaspille plus de temps cervical à des tâches ou les ordinateurs sont définitivement meilleurs. Donc :

def r(a):
i=a.find('0')
if i<0:
print a
[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j] for j in range(81)] or r(a[:i]+m+a[i+1:]) for m in`14**7*9`]

r('005300000800000020070010500400005300010070006003200080060500009004000030000009700')

résultat après quelques secondes, ce qui révèle une complexité élevée, en effet :

145327698839654127672918543496185372218473956753296481367542819984761235521839764

explications : http://drgoulu.com/2008/10/12/python/

Cyrille a dit…

Pourquoi celui de Métro semble beaucoup plus dur que le tien ? En faisant une hypothèse dès que c'est nécessaire, il m'en a fallu 12 pour résoudre celui-ci et 102 pour l'autre, en allant jusqu'à 8 hypothèses imbriquées les unes dans les autres.

J'avoue m'être aussi aidé d'un programme de calcul, mais l'écriture d'un algorithme (intelligent) de résolution de sudoku est au moins aussi intéressante que la résolution elle-même.

RuBisCO a dit…

"Une grille si difficile qu'elle n'a qu'une et une seule solution." Une grille de sudoku doit avoir une unique solution, sinon ce n'est pas une grille. :D
Mais j'avoue avoir eu la flemme, un programme à la calculatrice l'a résolu en moins de 3 minutes.

Farid Mita a dit…

Tiens! ça me fait revenir aux années 2005-2006-2007, où je me suis intéressé au Sudoku, en rédigeant de grands passages sur l'article "sudoku"
de Wikipedia:
http://fr.wikipedia.org/wiki/Sudoku
(je suis classé deuxième sur la liste des auteurs de cet article:
http://toolserver.org/~daniel/WikiSense/Contributors.php?wikilang=fr&wikifam=.wikipedia.org&page=Sudoku&grouped=on&order=-edit_count&max=100&format=html)

Ce n'est pas de l'autoglorification!

L'objet de ce post est de rappeler qu'une grille de sudoku doit aboutir à une unique solution! Sans cela, ce n'est pas du sudoku!
Et ce n'est pas suffisant si l'on cherche des grilles de qualité! Il est souhaitable que la grille soit irréductible (se reporter sur wikipedia pour cette condition)

Pour terminer, les puristes du sudoku interdisent la formulation des hypthèses sur les chiffres à mettre dans une case donnée! Préférence aux diverses techniques de résolution "manuelle" existantes sinon à élaborer...

hanane safir boulay a dit…

Bonsoir,
j ai résolu cette grille après 4 jours de probabilités :)

Enregistrer un commentaire

Des réactions, des propositions ? Exprimez-vous :-)
(A cause de quelques commentaires inopportuns, ceux-ci sont modérés et ne paraissent qu'après approbation)