Ich habe mich jetzt erstmal mit meinen Backtracking-Programmen befasst:
Erster Versuch: das n-dimensionale Damenproblem - läuft.
Zweiter Versuch: Sudoku - läuft.
Dritter Versuch: Str8ts - läuft.
Aber - nicht alle Extremes werden in akzeptabler Zeit gelöst. Ich habe das Ganze halt auch sehr puristisch gemacht, d.h. jedes freie Feld durchläuft die Kandidatenliste 1 bis 9.
Irgendwo oberhalb von ca. 52 ungelösten Feldern wird's bitter. Habe den Rechner mal bis über 200 Millionen Kandidatenchecks laufen lassen, ohne Lösung. Alle normalen werden aber problemlos innerhalb kürzester Zeit gelöst.
Meine Einschätzung im Moment ist, dass es keinen Sinn macht, schon an den Killer-Solver zu gehen. Erst muss der Str8ts-Solver gut laufen. ich werde deshalb ein bisschen Logiklösung integrieren. Das heißt, aus dem Originalrätsel werden erste logisch ausschließbare Kandidaten ermittelt. Wenn es für die freien Felder dann nicht mehr überall 1-9, sondern eine reduzierte Kandidatenliste gibt, sinkt der Rechenaufwand. Die zweite Verbesserung wird sein, die Reihenfolge der Felder, die der Solver durchläuft, so anzupassen, dass Felder mit den wenigsten Kandidaten am Anfang stehen. Ob das den Durchbruch bringt, weiß ich noch nicht.
Die angehägte Datei enthält die Killer 1-6 von SlowThinker und meinen ersten Versuch, das Killer #7.
Alle können wahlweise modifiziert ausgedruckt werden, also gedreht, gespiegelt und in den Farben variiert.
Das macht das mehrfach Lösen etwas variabler. Viel Spaß.