LösungsverfahrenDiese Lösungsverfahren werden in der Reihenfolge ihrer Komplexität ausgeführt. Sobald eine Änderung an dem Lösungsraster vorgenommen wurde, kehrt der Löser zu Lösungsverfahren A zurück. Jedes Mal wenn ein bestimmtes Lösungsverfahren angewendet wird, sammelt der Löser 'Schwierigkeitspunkte' auf, um eine Gesamtbewertung des Schwierigkeitsgrades des Sudokus vornehmen zu können.
Lösungsverfahren D ÜBERARBEITET!Überarbeitete Implementierung von Alan Chambers - Danke Al! Gehe durch alle Zeilen des Lösungsrasters und prüfe, ob es eine Gruppe von N Zellen gibt, die insgesamt nur N verschiedene Zahlen beinhalten. Wenn eine solche 'Kette' exisiert, dann müssen diese Zahlen in diesen Zellen liegen. Folglich können diese Zahlen aus den restlichen Zellen der Zeile gestrichen werden. Auch diese Regel wird analog für alle Spalten und Blöcke ausgeführt. Ein Beispiel: In der Zeile 1 2 3 4 5 6 7 8 9 --------------------------------------------------------------------------------- 378 38 6789 37 458 2 34568 489 1 enthalten die Spalten 1, 2 and 4 die Zahlen 3, 7, and 8. Also können wir [78] aus Spalte 3, [8] aus Spalte 5 und [38] aus Spalte 7 und [8] aus Spalte 8 streichen. Anschließend sieht die Zeile so aus: 1 2 3 4 5 6 7 8 9 --------------------------------------------------------------------------------- 378 38 69 37 45 2 456 49 1 Ein praktisches Beispiel finden Sie hier. Schwierigkeitsgrad=32, 48 bzw. 64 entsprechend den Werte N=2, 3 bzw. 4. Lösungsverfahren E - noch nicht implementiertUns wurde ein neues Verfahren zur Lösung eines unserer 'logik-resistenten' Sudokus vorgeschlagen, welches wir bisher nicht implementiert haben. Wenn Sie sich dieses Verfahren genauer ansehen möchten oder nach einer anspruchsvollen Programmieraufgabe suchen, klicken Sie hier. Lösungsverfahren F ÜBERARBEITET!Dieses Lösungsverfahren wird immer komplizierter, wie wir gleich sehen werden. Zunächst die einfachste Form: Gehe durch alle Zeilen des Lösungsrasters und prüfe, ob es Zahlen gibt, die in einer Zeile genau zweimal vorkommen. Prüfe, ob es eine zweite Zeile gibt, in der dieselbe Zahl ebenfalls zweimal vorkommt und zwar in denselben Spalten wie in der zuerst untersuchten Zeile. Ist dies der Fall, muss die gesuchte Zahl in genau zwei der vier gefundenen Zellen liegen (und zwar in diagonal gegenüber liegend Zellen). Folglich kann diese Zahl aus allen restlichen Feldern der beiden Zeilen und Spalten gestrichen werden. Diese Regel wird analog für alle Spalten durchgeführt. Dieses Verfahren ist unter Gurus als X-wing ('Kreuzflügel') bekannt. Es gibt auch das folgende Äquivalent für Blöcke: Wenn die beiden gefundenen Spalten einer Zeile innerhalb desselben Blocks liegen, kann die Zahl aus allen restlichen Feldern des Blocks gestrichen werden. Wiederhole für Spalten gegenüber Zeilen und Spalten gegenüber Blöcken. Anschließend wird dasselbe für Blöcke durchgeführt: Wenn zwei Blöcke mit gemeinsamen Zeilen oder Spalten dieselbe Zahl in genau zwei Zellen in übereinstimmenden Zeilen oder Spalten enthalten, kann diese Zahl aus allen restlichen Feldern in diesen Spalten bzw. Zeilen gestrichen werden. (Ziemlich kompliziert, nicht wahr? Ich bin mir nicht ganz sicher, ob ich es selbst verstanden habe.) Es wird sogar noch komplizierter, wenn man mit drei mal drei Zellen arbeitet. Diese Variante als als Swordfish ('Schwertfisch') bekannt. Schließlich gibt es noch höhere Ordnungen dieses Problems mit vier oder mehr Zellen. Al Chambers war auch hier der Vorreiter und hat eine generische Version von Lösungsvariante F implementiert, die mit beliebiger Ordnung N umgehen kann. Der helle Wahnsinn. Er hat seine Version für N=4 Jellyfish ('Qualle') genannt. Ich nehme an, weil man davon weiche Knie bekommt. Da kann ich nichts mehr zu sagen, Al. Schwierigkeitsgrad=48 (für X-wing) bzw. 64 (Swordfish und darüber) Andere LösungsverfahrenWeitere Lösungsregeln finden sich auf John Perry's Website. Diese sind reichlich kompliziert. Aber vielleicht können wir Sie ja überreden, für uns etwas Javascript-Code zu schreiben! Was ist "Raten-und-prüfen erlauben"?Raten-und-prüfen ist eine Implementierung des Ariadne-Fadens. Wenn alle Lösungsverfahren ausgeschöpft sind, probiert der Löser eine beliebige Zahl in einer der noch offenen Zellen. Anschließend versucht er, die vollständige Lösung durch Anwenden der oben beschriebenen Lösungsverfahren zu ermitteln. Wenn dabei ein ungültiges Sudoku entsteht, versucht es der Löser mit einer anderen Zahl. Dieses Vorgehen wird so lange wiederholt, bis eine vollständige (zulässige) Lösung gefunden wurde oder alle Rateversuche erfolglos durchprobiert wurden. Man kann sich streiten, ob dieses Vorgehen im Sinne der Logik ist, weshalb wir es erlauben, dieses Verfahren über ein Kontrollkästchen ein- oder auszuschalten. Erste Lösung zurückgebenWenn Sie die Vorgehensweise "Raten-und-prüfen" verwenden, ist es immer möglich, dass mehr als eine Lösung für das Sudoku gefunden wird. Wird das Kontrollkästchen "Erste Lösung zurückliefern" ausgeschaltet, so werden alle denkbaren Lösungen durchgespielt, um zu ermitteln, ob die gefundene Lösung eindeutig ist DanksagungVielen Dank an 'rubylips' von http://www.act365.com/sudoku/ für Rat und Tat bezüglich des "Ariadne-Fadens" und weitere hilfreiche Hinweise. Dank auch an r.e.s für den Link auf den Beweis, dass Sudokus NP-schwer sind, und für das Testen des Lösers. Dank an Pete Forman für die Überarbeitung von Lösungsverfahren B bezüglich der Suche in Blöcken. Dank an Colin Hughes für das Finden des Bugs in der Setz-Methode. Dank an Keven Cook für das Finden des Bugs in dem Report-Bereich. Dank an Tim Lindsay für die "logik-resistenten" Beispiele - die Inspiration für die Herausforderungsseite. Dank an Bill Giles für die Idee der Schritt-für-Schritt-Lösung. Dank an Mark Summerville für die Logikregeln zu den Lösungsverfahren E und F. Dank an Kevin Lawson für den Vorschlag des alternativen Herausforderungs-Rätsels. Dank an John MacLeod für die überarbeitete Version von Lösungsverfahren D. Dank an David Budgett und John MacLeod (nochmal!) für die Beschreibung der Block-Version von Lösungsverfahren F. Dank an Tim Nobel und Michael Lawrence für ihre Vorschläge neuer Regeln. Dank an Al Chambers für seine Implementierung des überarbeiteten Lösungsverfahrens D - gute Arbeit! Dank an Craig Oakley für "Swordfish". Dank an Al (nochmal!) für seine generische Implementierung von Lösungsverfahren F (ich werde es nie verstehen!) Dank an Nicolas Leoutre für die Übersetzung der Website auf Französisch. Dank an Sernin Van de Krol für die Übersetzung der Website auf Niederländisch. Dank an Riccardo Riva für die Übersetzung der Website auf Italienisch. Dank an Carsten von Schwichow für die Übersetzung der Website auf Deutsch. Dank an Gordon Royle für seine Liste von 17-Ziffern-Sudokus. Dank an Pat Breniser für seinen Tipp, wie sich die Schritt-für-Schritt-Lösung abbrechen lässt. |