Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
Str8ts [streɪts], auch Straights oder Stradoku, ist eine Art von Logikrätseln, die Gemeinsamkeiten mit Sudoku hat. Auch bei Str8ts wird ein 9 × 9-Gitter so mit den Ziffern 1 bis 9 gefüllt, dass jede Ziffer in jeder Spalte und in jeder Zeile nur einmal vorkommt. Anders als bei Sudoku, gibt es bei Str8ts aber auch schwarze Felder wie in Kreuzworträtseln. Gefüllt werden nur die weißen Felder. Schwarze Felder können leer oder mit einer Ziffer vorausgefüllt sein.
Der Name „Str8ts“ leitet sich von „straight“ ab, also von der „Straße“ beim Pokern. „Str8ts“ wird wie das englische Wort straights ausgesprochen. Zusammenhängende weiße Felder in Zeilen oder Spalten bilden bei Str8ts eine Straße, sie müssen also eine Folge zusammenhängender Ziffern enthalten. Dabei ist die Reihenfolge beliebig.
Ein Str8ts-Rätsel besteht aus dem 9 × 9-Spielfeld mit einem Muster schwarzer und weißer Felder und einigen vorgegebenen Ziffern. Schwierige Str8ts können mit sehr wenigen vorgegebenen Ziffern auskommen. Im September 2010 gab es ein Str8ts mit nur zwei vorgegebenen Ziffern.
Das Rätsel wurde 2008 von dem Kanadier Jeff Widderich erfunden. Er wollte ein Logikrätsel mit ähnlich einfachen Regeln wie Sudoku und einer ähnlich komplexen Logik entwerfen. Seine Idee war es, die schwarzen Felder einzufügen und die „Block-Regel“ von Sudoku durch die „Straßenregel“ von Str8ts zu ersetzen. Entstanden ist ein Rätsel, das in seiner Komplexität mit Sudoku vergleichbar ist und zusätzlich die Ästhetik von Kreuzworträtseln aufnimmt.
Für die Umsetzung hat Jeff Widderich sich mit Andrew Stuart zusammengetan, einem britischen Programmierer, dessen Sudoku-Website SudokuWiki.org als eine der besten gilt.
Seit August 2009 steht Str8ts als iPhone-Applikation zum Download zur Verfügung, seit Anfang 2013 auch als Android-Applikation. Mittlerweile gibt es auch schon mehrere Bücher mit Str8ts-Rätseln und ein Brettspiel aus Holz.
Das Spiel besteht aus einem Gitter mit 9 × 9 Feldern, insgesamt also 81 Felder in 9 Zeilen und 9 Spalten. Einige dieser Felder sind schwarz, die anderen weiß. Zusammenhängende weiße Felder in einer Zeile oder Spalte bilden Straßen.
Ziel des Spiels ist es, die leeren weißen Felder des Rätsels zu vervollständigen. Schwarze Felder werden nicht ausgefüllt. Solange das Str8ts nicht gelöst ist, können in einem Feld mehrere Möglichkeiten für verschiedene Ziffern bestehen. Werden diese Möglichkeiten notiert, nennt man sie Kandidaten.
Für Str8ts gilt wie für Sudoku, dass zur Lösung keine Rechenkenntnisse erforderlich sind. Allerdings muss man wissen, welche Zahlen benachbart sind (aufeinander folgen).
Beim Ausfüllen gelten die folgenden Regeln:
|
Da es auch schwarze Felder gibt, die leer sind, müssen nicht alle Ziffern von 1 bis 9 in jeder Zeile oder Spalte vorkommen. Ein leeres schwarzes Feld kann in Zeilenrichtung für eine andere fehlende Ziffer stehen als in Spaltenrichtung. Die Ziffern 1 und 9 sind nicht benachbart, die Folge „9812“ ist deshalb keine gültige Straße.
Bei den bisher veröffentlichten Str8ts gibt es die folgenden Schwierigkeitsstufen:
| Sterne | Deutsch | Englisch |
|---|---|---|
| * | Leicht | Gentle |
| ** | Mittel | Moderate |
| *** | Schwer | Tough |
| **** | Teuflisch | Diabolical |
| ***** | Extrem | Extreme |
Für Einsteiger gibt es besonders einfache Str8ts, die „leicht“ oder „easy“ genannt werden. Bei leichten und vielen mittleren Str8ts kann man Lösungsziffern nach und nach unmittelbar erkennen. Komplizierte logische Überlegungen sind nicht erforderlich. Bei den schwereren Str8ts erschließen sich Lösungsziffern aber erst, nachdem man durch die Verknüpfung verschiedener logischer Überlegungen die Anzahl der Kandidaten eines Feldes bis zur Lösung reduziert hat.
Bei Str8ts der Schwierigkeitsstufen „teuflisch“ und „extrem“ müssen oft streng systematisch Kandidaten bestimmt und nach und nach reduziert werden. Dabei müssen auch die komplexeren Lösungsstrategien verwendet werden, um ein Rätsel zu lösen.
Ein Teil der „extremen“ Str8ts lässt sich mit den bisher beschriebenen deduktiven Lösungsstrategien nicht lösen, obwohl sie gültig sind, also eine eindeutige Lösung besitzen.
Die Bestimmung der Schwierigkeit eines Str8ts ist weder eindeutig noch unumstritten. Die gefühlte Schwierigkeit hängt ganz wesentlich davon ab, ob man einen logischen Zusammenhang schnell erkennt oder nicht. Die Zuordnung zu Schwierigkeitsstufen kann von einem Lösungsprogramm dadurch ermittelt werden, dass gezählt wird, welche Lösungsmethoden wie oft angewendet werden müssen, bis die vollständige Lösung ermittelt ist. Den verschiedenen Lösungsmethoden werden Wichtungsfaktoren zugeordnet. Aufsummiert ergibt sich ein Score-Wert, der dann die Schwierigkeitsstufe bestimmt.
Das normale Str8ts ist ein Quadrat von 9 × 9 Feldern, wovon einige schwarz sind. Die schwarzen Felder können beliebig angeordnet sein. In typischen Str8ts sind ca. 20 Felder schwarz, die Spanne reicht von 1 bis 35.
Das gleiche Rätsel lässt sich durch verschiedene Transformationen in unterschiedlicher Weise darstellen. Dabei gibt es drei Transformationen des Musters und eine Zifferntransformation. Die einzelnen Transformationen sind:
Die vier Transformationen können beliebig kombiniert auf ein bestimmtes Str8ts angewendet werden, es ergibt sich immer ein korrektes scheinbar neues Str8ts-Rätsel. Tatsächlich handelt es sich aber weiter um das gleiche Str8ts in neuer Darstellung. Durch Transformationen können 16 Varianten erzeugt werden.
Zur Lösung von Str8ts sind systematisches Vorgehen und logisches Denken gefordert. Nur so kommt man Schritt für Schritt bis zur vollständigen Lösung. Leichte Str8ts lassen sich im Kopf durch logisches Denken lösen. Für anspruchsvollere Rätsel kommt man nicht mehr ohne Notizen aus, um verschiedene Lösungsmöglichkeiten für jedes Feld, die Kandidaten, aufzuschreiben.
Zunächst sucht man das Str8ts nach Straßen ab, die nur ein leeres weißes Feld enthalten. Das kann eine Zweier-Straße mit einer vorgegebenen Ziffer sein oder auch eine längere Straße, in der nur ein Feld leer ist. Nach der 3. Regel, der Straßenregel, kommen bei einer Zweier-Straße nur die beiden Nachbarziffern der Vorgabe infrage. Ist die Vorgabeziffer die 1 oder die 9, dann gibt es sogar nur eine Nachbarziffer, die dann als Lösung des freien Feldes eingetragen wird. Hat man zwei mögliche Ziffern gefunden, kann oft eine davon ausgeschlossen werden, weil sie die 2. Regel, die Zeilen-Spaltenregel, verletzt. Ganz einfache Str8ts können so komplett gelöst werden.
Das Grundprinzip aller Lösungswege wird dabei schon deutlich: Der Ausgangspunkt zur Lösung jedes leeren weißen Feldes ist die Liste der Kandidaten, die zunächst immer alle Ziffern von 1 bis 9 enthält. Unter Anwendung der Lösungsstrategien werden nach und nach die Kandidaten eines Feldes gestrichen. Bleibt nur noch ein Kandidat übrig, hat man die Lösungsziffer des Feldes gefunden. Bleibt kein Kandidat übrig, hat man einen Fehler gemacht oder das Rätsel ist fehlerhaft.
Findet man keine weitere Lösungsziffer, muss man zunächst die Kandidaten der Felder feststellen und dann nach und nach reduzieren. Welche Kandidaten für ein Feld möglich sind, kann man sich mit den von Sudoku her bekannten Methoden notieren. Zweckmäßigerweise beginnt man mit Feldern, für die offenbar nur wenige Kandidaten existieren, und notiert diese. Dabei erkennt man weitere logische Zusammenhänge, so dass Kandidaten gestrichen werden können. Nur wenige Kandidaten hat man beispielsweise bei einer Zweier-Straße mit einer vorgegebenen Ziffer, aber auch bei Dreier-Straßen ist die Zahl der Kandidaten schon durch unmittelbare Anwendung der ersten drei Regeln klein.
Bei sehr schwierigen Str8ts kann es vorkommen, dass man für alle leeren Felder die Kandidaten ermitteln und notieren muss, bevor man nach Anwendung verschiedener Lösungsstrategien und daraus folgender Reduktion der Kandidaten eine Lösungsziffer entdeckt. Wenn eine neue Lösungsziffer gefunden wird, kann man deren Auswirkung auf die Kandidaten der Felder der gleichen Spalte oder Zeile eintragen. Hat sich die Kandidatenliste in einem Feld verringert, folgt aus der 3. Regel, dass sich möglicherweise in den Feldern der zugehörigen Straßen weitere Kandidaten ausschließen lassen.
Zeilen-Spalten-Prüfung ist die unmittelbare Anwendung der 2. Regel. Für ein Feld lassen sich alle Ziffern ausschließen, die in der Zeile oder der Spalte des Feldes bereits vorkommen. Diese Methode ist offensichtlich und wird deshalb auch intuitiv angewendet, ohne dass sie als Methode empfunden wird.
Straßen-Prüfung bedeutet zunächst die unmittelbare Anwendung der 3. Regel. Findet man beispielsweise eine Dreier-Straße mit den Ziffern 3 und 5 sowie einem freien Feld, dann muss dort eine 4 stehen. Die Straßenregel führt darüber hinaus auch zu weiteren wichtigen Schlussfolgerungen, deshalb ist sie das Herzstück des gesamten Spiels.
Wegen der schwarzen Felder kommen in einer Zeile oder Spalte nicht zwingend alle Ziffern von eins bis neun vor, wie das bei Sudoku der Fall ist. Im Verlauf einer Lösung gibt es unter den Kandidatenziffern deshalb sichere oder mögliche Ziffern. Für einige der Lösungsstrategien ist es von entscheidender Bedeutung, ob eine Ziffer sicher oder ob sie nur möglich ist.
Neben der unmittelbaren Anwendung der 3. Regel führt die Straßen-Prüfung (Compartment Check) zum Ausschluss von Kandidaten, sowohl innerhalb als auch außerhalb der jeweiligen Straße.
Aus den bekannten Ziffern oder den Kandidaten der weißen Felder einer Straße wird ermittelt, innerhalb welcher Grenzen die Ziffern der Straße liegen können. Alle Ziffern, die außerhalb dieses Bereiches legen, können aus den Feldern der Straße gestrichen werden.
Ist der Wertebereich der Straße kleiner als ihre doppelte Länge, dann gibt es Ziffern, die sicher in dieser Straße vorkommen müssen. Sichere Ziffern können in der Zeile bzw. Spalte der Straße aus den Feldern außerhalb der Straße gestrichen werden. Steht beispielsweise in einer Dreier-Straße in einem Feld die Ziffer 4, dann können allein aus der Straßenregel in den beiden leeren Feldern nur die Ziffern 2, 3, 5 und 6 vorkommen. Alle anderen Ziffern können in den Feldern dieser Straße gestrichen werden. Die Ziffern 2356 dieses Beispiels werden dann mögliche Ziffern (possible digits) genannt.
Entfällt in dieser Straße die Ziffer 2 in beiden noch ungelösten Feldern, bleiben neben der bereits bekannten 4 als mögliche Ziffern der Straße die 3, 5 und 6 stehen. Das bedeutet, dass die Straße entweder 345 oder 456 enthält. In beiden Kombinationen kommt neben der 4 auch die 5 vor. Die 5 wird dann sichere Ziffer (necessary digit) der Straße genannt. Das Erkennen sicherer Ziffern ist von entscheidender Bedeutung für einige Lösungsmethoden. Eine sichere Ziffer einer Straße kann aus den Kandidaten aller außerhalb liegenden Felder der Zeile bzw. Spalte gestrichen werden, zu der die Straße gehört. Da die Beispielstraße Teil einer Zeile ist, kann also die 5 aus allen Feldern der Zeile außerhalb der Straße gestrichen werden.
Enthält eine Straße noch keine bekannte Lösung, kann die Straßenprüfung in gleicher Weise auf Basis der aktuell möglichen Kandidaten durchgeführt werden. Enthält die Dreier-Straße zum Beispiel die Kandidaten 3456-35-456, dann sind 3456 die möglichen und 45 die sicheren Ziffern der Straße. 45 können außerhalb der Straße in deren Zeile gestrichen werden.
Ein weiteres Beispiel: die Dreier-Straße mit den Kandidaten 23456-56-46 hat die möglichen Ziffern 3456, 45 sind sichere Ziffern. Die 2 ist nicht möglich, weil sie mit den Ziffern 56 im zweiten Feld keine Dreier-Straße bilden kann.
In der abgebildeten Fünfer-Straße kommen die Ziffern 1 bis 7 vor. Damit sind 3, 4 und 5 sichere Ziffern, sie müssen vorkommen. Die 1, 2, 6 und 7 können, müssen aber nicht vorkommen.
Andrew Stuart beschreibt im Abschnitt „Strategy discussion“ seiner Website die Straßenprüfung in zwei Abschnitten. Er nennt den ersten Teil, der Ziffern innerhalb der Straße eingrenzt, „Compartment Check“. Die zweite Strategie, die sichere Ziffern außerhalb der Straße ausschließt, nennt er „High/low“.
Eine versteckte Einzelziffer (hidden single) ist eine sichere Ziffer, die in ihrer Straße nur in einem Feld vorkommt (die 3 im nebenstehenden Beispiel). In diesem Feld können also alle übrigen Kandidaten gestrichen werden, die versteckte Einzelziffer ist die Lösung des Feldes.
Es muss sich um eine sichere Ziffer handeln. Ist die einzeln vorkommende Ziffer möglich, aber nicht sicher, dann ist sie auch keine sichere Lösung.
Kann eine Ziffer mit den möglichen Ziffern der übrigen Feldern einer Straße keine zulässige Straße bilden, dann ist sie gestrandet und kann gelöscht werden (stranded digit).
Beispiel im Bild rechts: Dreier-Straße-Kandidaten sind 2457-456-4567. Die 2 ist gestrandet, weil es keine 3 gibt, die als Verbindung zu den Ziffern der beiden anderen Felder erforderlich wäre.
Enthält ein Feld einer Straße der Länge 2 nur gerade Ziffern, kann man im benachbarten Feld alle geraden Ziffern streichen. Im benachbarten Feld können nur Ziffern stehen, die um 1 verschieden sind. Gleiches gilt für die ungeraden Ziffern.
Straßen mit einer Länge von 5 bis 7 Feldern enthalten zwangsläufig bestimmte Ziffern und schließen diese damit in anderen Straßen derselben Zeile oder Spalte aus:
| Länge | Ausschlüsse |
|---|---|
| 5 | 5 |
| 6 | 4, 5, 6 |
| 7 | 3, 4, 5, 6, 7 |
Befindet sich zusätzlich eine Ziffer in einem schwarzen Feld der Zeile oder Spalte, kann man weitere Ziffern ausschließen.
Mit den oben beschriebenen Basis-Lösungsmethoden lassen sich die meisten einfachen bis mittelschweren Str8ts lösen. Die im Folgenden genannten Lösungsmethoden werden seltener gebraucht, sind aber für schwere, teuflische oder gar extreme Str8ts erforderlich.
Steht in einem Feld einer Straße ein Ziffernpaar, dessen Differenz mindestens so groß ist wie die Länge dieser Straße, dann können diese beiden Ziffern in allen anderen Feldern dieser Straße gestrichen werden. Das liegt daran, dass nicht beide Ziffern gemeinsam in der Straße existieren können, weil diese zu kurz ist. Das Vorkommen der einen Ziffer schließt also die andere in dieser Straße aus.
Beispiel sei ein Feld mit dem Paar 19 in einer Straße kürzer als neun Felder. Steht dort die 1, müsste irgendwo anders in dieser Straße eine 9 stehen. Steht dort die 9, müsste irgendwo anders in der Straße eine 1 stehen, was aber beides nicht möglich ist, da in einer Straße mit acht oder weniger Feldern nicht gleichzeitig 1 und 9 stehen können.
Aus den Str8ts-Regeln folgt, dass jede Ziffer genauso oft in Spalten wie in Zeilen vorkommen muss. Kommt also eine Ziffer in irgendeiner Zeile nicht vor, muss es auch eine Spalte geben, in der sie nicht vorkommt (und umgekehrt). Wenn man z. B. weiß, dass eine Ziffer sicher in genau sieben Zeilen vorkommt, dann weiß man, dass sie auch genau in sieben Spalten vorkommen muss. Ist diese Ziffer in sieben Spalten sicher und in zwei Spalten als möglich ermittelt, kann sie in den beiden möglichen Spalten gestrichen werden. Ist sie in sechs Spalten sicher und in einer weiteren als möglich ermittelt, dann ist sie dort sicher, d. h., dass dort dann andere Kandidatenziffern entfallen.
Für die Anwendung der Setti-Regel ist das gesamte Spielfeld zu untersuchen, was diese Lösungsmethode recht aufwendig macht. Für wirklich extreme Str8ts ist die Setti-Regel aber oft eine sehr wirkungsvolle Lösungsstrategie. Bei der Anwendung muss die Kandidatenziffern-Eigenschaft "sicher in der Zeile" oder "sicher in der Spalte" betrachtet werden.
Paar (englisch naked pair): Kommen in zwei Feldern einer Zeile oder Spalte lediglich zwei gleiche Kandidatenziffern vor, dann können diese beiden Ziffern aus den übrigen Feldern der Zeile bzw. Spalte gestrichen werden.
Die Paar-Methode und auch die unten beschriebenen Tripel- und Quadrupel-Methoden funktionieren in Zeilen und Spalten von Str8ts genauso, wie in Zeilen und Spalten von Sudokus. Paare, Tripel oder Quadrupel können in verschiedenen Straßen vorkommen und aus allen Kandidaten (möglichen oder sicheren) gebildet werden.
Tripel (englisch naked triple): Kommen in drei Feldern einer Zeile oder Spalte lediglich drei gleiche Kandidatenziffern vor, dann können diese drei Ziffern aus den übrigen Feldern der Zeile bzw. Spalte gestrichen werden.
Das Triple kann dabei Felder mit den drei oder auch mit zwei der drei Ziffern enthalten. Beispiel: drei beliebige Felder einer Spalte enthalten 12-23-123. Dann liegt ein Tripel 123 vor.
Quadrupel (englisch naked quadruple): Kommen in vier Feldern einer Zeile oder Spalte lediglich vier gleiche Kandidatenziffern vor, dann können diese vier Ziffern aus den übrigen Feldern der Zeile bzw. Spalte gestrichen werden.
Das Quadrupel kann dabei Felder mit den vier oder auch mit zwei oder drei der vier Ziffern enthalten.
Ein verstecktes Paar (hidden pair) liegt dann vor, wenn zwei sichere Ziffern einer Straße lediglich in den gleichen beiden Feldern der Straße vorkommen. Die weiteren Kandidaten dieser beiden Felder können gelöscht werden.
Beispiel: In einer Fünfer-Straße mit den Kandidaten 124-23567-467-12356-47 sind die Ziffern 345 sichere Ziffern. Da 3 und 5 nur in den Feldern 2 und 4 vorkommen, können die übrigen Kandidaten gelöscht werden. Ergebnis: 124-35-467-35-47.
Ein verstecktes Tripel (hidden triple) liegt dann vor, wenn drei sichere Ziffern einer Straße lediglich in den gleichen drei Feldern der Straße vorkommen. Die weiteren Kandidaten dieser drei Felder können gelöscht werden.
Ein verstecktes Quadrupel (hidden quadruple) liegt dann vor, wenn vier sichere Ziffern einer Straße lediglich in den gleichen vier Feldern der Straße vorkommen. Die weiteren Kandidaten dieser vier Felder können gelöscht werden.
X-Wing:[5] Kommt eine bestimmte Ziffer in zwei Spalten jeweils genau zweimal vor, und zwar in den beiden gleichen Zeilen, und handelt es sich bei der Ziffer um eine für die jeweilige Spalten-Straße sichere Ziffer, dann kann sie in den beiden Zeilen an anderer Stelle ausgeschlossen werden.
Die Regel gilt in gleicher Weise für sichere Ziffern in Zeilen-Straßen. Wichtig dabei ist, dass eine Ziffer in einer Zeile sicher sein kann und gleichzeitig in der Spalte möglich, aber nicht sicher ist.
Die vier Felder, in denen die sichere Ziffer vorkommt, bilden ein Rechteck, in dem die Ziffer in einem der zwei diagonal gegenüberliegenden Eckenpaare als Lösung vorkommen muss. Die beiden Diagonalen bilden das X, das, wie auch beim Sudoku, zum Namen X-Wing als Lösungsmethode geführt hat.
Wenn ein X-Wing aus sicheren Ziffern z der Spalte existiert, werden Ziffern z, die vorher nicht sicher waren, aber der gleichen Zeilenstraße angehören, zu sicheren Ziffern. Der mögliche Wertebereich der Zeilenstraße reduziert sich dabei. Das gilt entsprechend auch für X-Wings in Zeilenrichtung.
Eine Erweiterung der X-Wing-Logik auf drei Zeilen und Spalten wird Swordfish[6] (engl. für "Schwertfisch") genannt: Kommt eine bestimmte Ziffer in drei Spalten jeweils zwei- oder dreimal vor, und zwar in den drei gleichen Zeilen, und handelt es sich bei der Ziffer um eine für die jeweilige Spalten-Straße sichere Ziffer, dann kann sie in den drei Zeilen an anderer Stelle ausgeschlossen werden.
Wenn ein Swordfish aus sicheren Ziffern z der Spalte existiert, werden Ziffern z, die vorher nicht sicher waren, aber der gleichen Zeilenstraße angehören, zu sicheren Ziffern. Der mögliche Wertebereich der Zeilenstraße reduziert sich dabei.
Auch hier gilt, dass die Regel in gleicher Weise für sichere Ziffern in Zeilen-Straßen gilt.
Die Erweiterung der X-Wing- und Swordfish-Logik auf vier Zeilen und Spalten wird Jellyfish[7] (engl. für "Qualle") genannt: Kommt eine bestimmte Ziffer in vier Spalten jeweils zwei-, drei- oder viermal vor, und zwar in den vier gleichen Zeilen, und handelt es sich bei der Ziffer um eine für die jeweilige Spalten-Straße sichere Ziffer, dann kann sie in den vier Zeilen an anderer Stelle ausgeschlossen werden.
Wenn ein Jellyfish aus sicheren Ziffern z der Spalte existiert, werden Ziffern z, die vorher nicht sicher waren, aber der gleichen Zeilenstraße angehören, zu sicheren Ziffern. Der mögliche Wertebereich der Zeilenstraße reduziert sich dabei.
Auch hier gilt, dass die Regel in gleicher Weise für sichere Ziffern in Zeilen-Straßen gilt. Man kann das Prinzip auch auf 5 × 5 („Starfish“, engl. für "Seestern") usw. erweitern, solange man es nur auf sichere Ziffern anwendet.
Wenn es gar nicht weiter geht, hilft eine Hypothese (was-wäre-wenn?, Ausprobieren, Ariadnes Faden, Versuch und Irrtum, Backtracking), die weiterverfolgt wird, bis sie auf die Lösung oder einen Widerspruch führt. Sie sollte erst dann angewendet werden, wenn alle oben dargestellten Methoden nicht mehr weiterhelfen.
Für ein Ausprobieren eignen sich vor allem Felder, die nur zwei Kandidaten aufweisen, weil dann eine falsche Hypothese die Alternative als richtig bestätigt. Man muss sich dabei den Ausgangspunkt der Annahme merken. Wenn die Verfolgung der getroffenen Annahme nicht zum Widerspruch führt, verfolgt man die Annahme der Alternative; wenn die zum Widerspruch führt, war die erste Annahme richtig. Als besondere Situation kann es sich ergeben, dass alle Annahmen in einem anderen Feld dieselbe Zahl als Schlussfolgerung ergeben. Dann hat man an dieser Stelle eine Lösungsziffer gefunden.
Mit Hypothese und Widerspruch lässt sich letztlich jedes noch so schwierige Str8ts lösen und auch seine Eindeutigkeit nachweisen. Der Weg dahin kann allerdings sehr langwierig und unübersichtlich werden, wenn man beim Verfolgen einer Hypothese weitere Unterhypothesen annehmen muss. Von manchen Spielern wird das Testen von Hypothesen auch generell als unlogisch oder unästhetisch abgelehnt.
Die Aussage ein Str8ts sei logisch lösbar, führt immer wieder zu Diskussionen über die Frage, ob Hypothese und Widerspruch als logische Methode angesehen wird.
Die oben beschriebenen Methoden können alle als deduktiv bezeichnet werden. Eine Methode gilt als deduktiv, wenn sich aus einer oder auch mehreren Prämissen eine Folgerung ableiten lässt.
Die Zeilen-Regel beispielsweise ist deduktiv, weil man sie so formulieren kann:
WENN Ziffer n in der Zeile vorkommt, DANN kann Ziffer n kein Kandidat in einem ungelösten Feld der Zeile sein.
Oder allgemeiner:
WENN Muster vorkommt, DANN können bestimmte Ziffern ausgeschlossen werden.
In diesem Sinn folgt die Methode Hypothese-Widerspruch keiner deduktiven Logik. Mit der Aussage „Das Str8ts ist logisch lösbar“ ist also gemeint, dass das Str8ts mit deduktiven Methoden lösbar ist.
Ein Lösungsprogramm kann die beschriebenen deduktiven Methoden verwenden, um ein Str8ts zu lösen. Die Methoden werden dazu nach und nach auf das gesamte Str8ts angewendet. Immer wenn eine Lösung gefunden wird oder Kandidaten ausgeschlossen werden können, beginnt eine neue Programmschleife. Um wirklich alle Str8ts zu lösen, muss als letzte Methode aber auch das Backtracking verwendet werden.
Einen Solver findet man auf den Websites www.str8ts.com und www.str8ts.de. Er enthält allerdings nicht alle oben beschriebenen Methoden, insbesondere auch nicht das abschließende Backtracking. Deshalb kann er nicht alle Str8ts lösen.
Auf dem Computer kann man ein Str8ts auch ausschließlich mit der Backtracking-Methode lösen. Beginnend mit dem ersten freien Feld werden systematisch alle Kandidaten probiert. Beim ersten Widerspruch geht man zurück (engl. backtrack) und wählt den nächsten Kandidaten. Hat ein Feld keine wählbaren Kandidaten mehr, wird um ein Feld zurückgegangen und dort der nächste Kandidat gewählt. Dieser Lösungsweg lässt sich sehr elegant rekursiv formulieren, und man ist sicher, dass alle Kombinationsmöglichkeiten abgesucht werden. Da es sich um tausende Wege handeln kann, ist dieser Algorithmus nur für Computerprogramme geeignet.
Die beim Sudoku bewährten Methoden zum Merken von Kandidaten können beim Str8ts genauso angewandt werden.
Beginnend mit den kurzen Straßen ermittelt man Feld für Feld die Kandidaten und schreibt sie als kleine Ziffern an den oberen oder unteren Rand des Feldes. Wird ein Kandidat ausgeschlossen, streicht man ihn durch.
Wird eine Ziffer der Kandidatenliste zur sicheren Ziffer, kann man sie unterstreichen, wenn sie in der Zeilenstraße sicher ist oder einen senkrechten Strich daneben setzen, wenn sie in der Spaltenstraße sicher ist. Man kann die sicheren Kandidaten der beiden Richtungen auch durch farbige Punkte in zwei Farben markieren.
Diese Methode kann bei kleingedruckten und schwierigen Str8ts unübersichtlich werden. Dann hilft nur Kopieren und Vergrößern des Rätsels.
Für klein gedruckte Str8ts in Zeitungen ist die Uhrzeiger-Strichmethode hilfreich, um die Kandidaten für ein Feld festzuhalten. Man macht im Feld einen kleinen Strich an der Stelle des „Uhrzeigers“ (siehe Bild). Die Fünf stellt eine Ausnahme dar; sie wird als kleiner Punkt in der Mitte dargestellt. So kann man sich mehrere Kandidaten für ein Feld merken. Wenn man keinen Radiergummi zur Hand hat, streicht man einen Kandidatenstrich durch, wenn weitere Überlegungen diesen ausschließen. Diese Methode gilt als leserlicher als das Schreiben von kleinen Ziffern. Die Markierung sicherer Ziffern kann wieder durch zwei Farben erfolgen.
Man kann kleine Punkte entsprechend einer Telefontastatur setzen und damit mögliche Kandidaten für ein Feld notieren, beginnend für die Eins in der linken oberen Ecke. Oben in der Mitte kommt der Punkt für eine Zwei, in der rechten oberen Ecke der Punkt für eine Drei, am linken Rand in der Mitte liegt der Punkt für eine Vier und so weiter bis zum Punkt für eine Neun, der dann in der rechten unteren Ecke steht.
Schwieriger als das Lösen eines Str8ts ist es, eines zu entwerfen. Ohne die Hilfe eines Lösungsprogramms wäre es extrem aufwendig, wollte man es tatsächlich versuchen.
Verfügt man über ein Lösungsprogramm, kann man ein neues Str8ts in folgender Weise erzeugen:
Muster erzeugen
Im ersten Schritt wird ein Muster der schwarzen Felder erzeugt. Als einzige wirkliche Bedingung muss ein Str8ts mindestens ein schwarzes Feld haben.
Typische Str8ts haben 15 bis 25 schwarze Felder. Oft werden weitere Einschränkungen gemacht. Dazu gehört die Symmetrie des Musters, weil insbesondere die häufig verwendete Punktsymmetrie um den Mittelpunkt zu einem ästhetisch befriedigenderen Muster führt. Eine Bedingung kann auch sein, keine Straßen der Länge 1 zuzulassen. Interessante Str8ts haben viele lange Straßen, schwierige haben oft 3 oder auch 4 Straßen in einer Zeile oder Spalte. Hält man solche Bedingungen beim Entwerfen eines Musters ein, können ganz gezielt Muster für einfachere oder schwierigere Str8ts erzeugt werden.
Weiße Felder füllen
Im zweiten Schritt wird das leere Muster in den weißen Feldern mit Ziffern so gefüllt, dass alle Regeln eingehalten werden. Dieser Schritt entspricht der Lösung eines fertigen Str8ts, allerdings mit der Einschränkung, dass das leere Muster keine eindeutige Lösung hat, sondern meist sehr viele. Es ist aber auch möglich, dass es für ein gewähltes Muster gar keine Lösung gibt. Im zweiten Schritt ist deshalb das Ziel, irgendeine Lösung für alle weißen Felder zu finden.
Zum Ausfüllen der leeren weißen Felder wird ein Lösungsprogramm eingesetzt, das entweder die oben beschriebenen deduktiven Methoden verwendet oder ein Backtracking durchführt.
Schwarze Felder füllen
Im dritten Schritt werden die schwarzen Felder soweit möglich mit Ziffern gefüllt, wobei die Zeilen-Spalten-Regel beachtet werden muss. Hier können deshalb auch schwarze Felder leer bleiben, wenn es keine zulässige Ziffer gibt.
Weiße Felder leeren
Im vierten Schritt werden nach und nach Ziffern aus weißen Feldern gelöscht. Nach jeder Löschung wird geprüft, ob das dabei entstehende Str8ts lösbar ist. Das wird wiederholt, solange das Str8ts lösbar bleibt.
Verwendet man zu dieser Überprüfung ein Programm, das die deduktiven Methoden verwendet, dann kann man durch Aktivieren bzw. Deaktivieren der einzelnen Methoden steuern, welche der Methoden zur Lösung des entstehenden neuen Str8ts erforderlich sind.
Schwarze Felder leeren
Im fünften Schritt werden nach und nach auch die Ziffern aus schwarzen Feldern gelöscht. Nach jeder Löschung wird wieder geprüft, ob das Str8ts eindeutig lösbar bleibt.
Bis zum fünften Schritt kann zur Überprüfung der eindeutigen Lösbarkeit auch ein Programm eingesetzt werden, das Backtracking verwendet.
Schwierigkeitsgrad bestimmen
Im letzten Schritt wird das neue Str8ts mit dem deduktiven Lösungsprogramm gelöst und dabei ausgezählt, welche Methode wie oft verwendet wird, um die Lösungsziffern zu ermitteln. Aus dem so bestimmten Summenwert wird dann der Schwierigkeitsgrad abgeleitet. Wenn vorher die Lösbarkeit mit Backtracking geprüft wurde, kann sich jetzt herausstellen, dass die deduktiven Methoden nicht ausreichen, um zu einer Lösung zu kommen. In diesem Fall ist ein extremes Str8ts der höchsten Schwierigkeitsstufe entstanden.
Sollte sich herausstellen, dass der Schwierigkeitsgrad höher als gewünscht ist, können weitere Ziffern als Vorgaben eingesetzt werden. Das verringert dann die Schwierigkeit bis zum gewünschten Level.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
