schwerstes Sudoku
Dem geneigten Leser meines Blogs dürfte ja meine Schwäche für Sudokus bekannt sein. 
Nun las ich von einem Mathematiker, der das schwerste Sudoku kreiert hat. Es hat den Namen “AI Escargot” (andere Quellen meinen es heißt “AI Etana”) bekommen. Dieser Name leitet sich von den Initialen des Erschaffers (Arto Inkala) sowie von Schlange ab. Denn zum einen sieht das Puzzle wie eine Schlange aus und andererseits schlängeln sich auch die Zahlen durch die Kästchen. Viel Spass beim Lösen:
Trackbacks
No Trackbacks
Comments
Display comments as Linear | Threaded
Lukas on :
Jens Kubieziel on :
Joachim on :
534129678
789643521
475312986
913586742
628794135
356478219
241935867
897261354
das war einfach
flopthewop on :
Jens Kubieziel on :
prog-man on :
das heißt also hier muss es noch andere Loesungswege geben! mb
Anonymous on :
Manuel on :
Jens Kubieziel on :
Anonymous on :
Anonymous on :
Frank on :
Eric Neufeld on :
ich bin übirgens wie folgt auf die Lösung gekommen. Es gibt zwei oder mehr felder wo nur 2 zahlen möglich sind. Aus diesen lassen sich zwei zu einander kombinieren. Also da zwei von diesen felder sich unmittelbar gegenüberstehn. ergibt sich hier eine beziehung. Es belibt dann nichts anderes übrieg als einzusetzten und aufn wiederspruch, bestimmte zahlen auszuschließen. Dies Sudoku ist nur mit extremen nachdenken und ausprobieren lösbar.
h2oundco on :
Sven on :
LooksAeterna on :
- keine automatischen Hilfsmittel (außer das Geschmiere gespart und in eine Excel-Tabelle getippt [ohne Formeln, reine Schreibhilfe])
- oft bis zu 4 verschachtelte Hypothesen bei der Lösungssuche
Habe es zweimal gelöst:
Das erste mal Ende 2007 (390 Minuten = 6 + 1/2 h !)
Heute das zweite mal mit nur 230 Minuten = 3 Stunden 50 *Minuten*.
Zwischendurch hatte ich “das schwerste Sudoku” vergessen und kein einziges mal angeschaut und zum Training http://www.sudoku-knacker.de 200 Stück der Stufe sehr schwierig gelöst. Das dürfte die Beschleunigung erklären, aber die Frage aufwerfen, warum ich mir das antue. Ich denke es dient dem Ziel
Nie wieder Sudoku !
spielen zu müssen.
Interessanterweise ist meine zweite Lösung identisch mit meiner ersten, obwohl ich völlig verschiedenen Wegen gefolgt bin. Wenn h2oundco über Dir mit seinen 30 möglichen Lösungen Recht hat, ist das eine ziemliche Überraschung.
samdabadei on :
XD jeah bester sudoulöserprogrammierer auf der seite
Leon on :
Felix on :
Jens Kubieziel on :
Tobias on :
Es gibt eine Lösung:
1 6 2 8 5 7 4 9 3
5 3 4 1 2 9 6 7 8
7 8 9 6 4 3 5 2 1
4 7 5 3 1 2 9 8 6
9 1 3 5 8 6 7 4 2
6 2 8 7 9 4 1 3 5
3 5 6 4 7 8 2 1 9
2 4 1 9 3 5 8 6 7
8 9 7 2 6 1 3 5 4
Aufwand:
Dazu musste er die rekursive (sich selbst aufrufende) Methode zum Lösen 201.143 mal aufrufen.
Zum Vergleich, ein sehr schweres Beispielsudoku hat 35.024 Aufrufe benötigt.
201.143 / 35.024 = 5,74300... = fast 6x
35.024 / 201.143 = 17,41...% < ein Fünftel
Funktionsweise:
Das Programm probiert der Reihe nach die Zahlen 1 bis 9 für ein unbelegtes Feld aus. Ist die Stellung danach noch legal (also keine doppelten in einer Reihe etc.) geht es zum nächsten freien Feld. Wenn es nicht legal ist wird die nächste Zahl ausprobiert, wenn gar nichts funktioniert geht es zum vorherigen Feld zurück und ändert dort die Zahl und probiert dann wieder usw.. Ist die Methode am letzten Feld rechts unten angekommen und das Sudoku noch “legal”, dann ist das eine Lösung
Noch zum Aufwand:
Zur Zahl der Aufrufe muss man noch sagen, dass das Programm alle “legalen” Kombinationen ausprobiert, also auch nach Finden der Lösung nach potenziellen weiteren Lösungen sucht. Hab es mal umgeschrieben, sodass es nach jeder Lösung verrät wie oft es aufgerufen wurde: “sehr schwierig” benötigt dann 23.923 Aufrufe, “Al Escargot” 86.632 Aufrufe.
86.632 / 23.923 = 3,62... = ca. 3,5 mal
23.923 / 86.632 = 27,61%... > ein Viertel
Das Programm hab ich nur für dieses Sudoku geschrieben, hat Spaß gemacht
Tobias (tobias.voelk@t-online.de)
Tobias on :
Tobias on :
Mit reinem Backtracking ohne andere Strategien?
Ich hab es in C++ (das ja bekanntlich schneller als Java ist) mit Backtracking geschrieben, es braucht eine drittel Sekunde.
Hast du mehrere Kerne verwendet oder es rekursiv geschrieben?
Verwendest du beim Lösen mehrere Methoden (z.B. noch welche um das nächste Feld zu finden) oder schreibst du das alles ausführlich in eine Methode?
Martin Boekhoff on :
#define _ 0
#define S(x) x,
#define D(x) x x x
#define L(x) D(S(x))
#define R(x) D(D(S(x)))
#define E(f,x) f(x)f(x+1)f(x+2)
char sudoku[] = {
1, _, _, _, _, 7, _, 9, _,
_, 3, _, _, 2, _, _, _, 8,
_, _, 9, 6, _, _, 5, _, _,
_, _, 5, 3, _, _, 9, _, _,
_, 1, _, _, 8, _, _, _, 2,
6, _, _, _, _, 4, _, _, _,
3, _, _, _, _, _, _, 1, _,
_, 4, _, _, _, _, _, _, 7,
_, _, 7, _, _, _, 3, _, _,
};
char c[] ={E(R,0)E(R,3)E(R,6)}, q[] ={D(D(E(S,0)E(S,3)E(S,6)))}, w[] ={D(E(L,0))
D(E(L,3))D(E(L,6))}; v(char *b, char *r){int l[]={R(0)0},i=82,f,s; for(;--i;l[s]
|=1