Str8ts

Str8ts
Offizielles Logo

Str8ts ist ein Logikrätsel, das an Sudoku erinnert. Auch bei Str8ts wird ein 9 x 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 gefü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 kann die Reihenfolge beliebig sein.

Ein Str8ts-Rätsel besteht aus dem 9 x 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 hatte dabei die Vision, ein Logik-Rätsel mit ähnlich einfachen Regeln wie Sudoku, aber mit einer ähnlich komplexen Logik zu entwerfen. Es war seine Idee, 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-Seite im Web als eine der besten gilt.

Inhaltsverzeichnis

Wo findet man Str8ts?

Einfaches Str8ts...
...und seine Lösung

Es gibt die Internetseite der Erfinder www.str8ts.com.[1] Hier gibt es jeden Tag je ein symmetrisches und ein asymmetrisches neues Str8ts zum Online-Spielen, ein einfaches Einsteiger-Str8ts, Mini-Str8ts in drei Schwierigkeitsstufen und wöchentlich ein extremes Str8ts, das besonders schwierig ist.

Die deutsche Str8ts-Internetseite www.str8ts.de[2] zeigt die gleichen täglichen Rätsel, enthält aber zusätzlich ein Forum, in dem ausführlich über Strategien und spezielle Aufgaben diskutiert wird. Dort sind auch eine Reihe anspruchsvoller Str8ts zu finden.

Die Süddeutsche Zeitung veröffentlicht seit März 2010 täglich auf ihrer Rätselseite ein Str8ts. Die Rätsel der SZ sind für Einsteiger sehr gut geeignet, es gibt aber nur selten besonders schwierige Rätsel.

Die Rheinpfalz veröffentlicht seit August 2010 wöchentlich ein Str8ts in ihrer Samstagsausgabe.

Auf der Online-Seite der WAZ[3] wird seit dem 15. November 2010 ein täglich wechselndes Str8ts angeboten.

Weitere Medien, die regelmäßig Str8ts-Rätsel veröffentlichen:

  • Zeitschrift "freizeit exklusiv" (seit April 2010, monatlich)
  • iPad App der Frankfurter Rundschau (seit September 2010, täglich)
  • Wochenendbeilage der Nürnberger Nachrichten (seit November 2010, zweiwöchentlich)
  • Die zwei Schweizer TV-Magazine TV2 und TVvier (seit Dezember 2010, zweiwöchentlich und monatlich)
  • P.M. Kreativ-Trainer (seit Januar 2011)
  • Die libanesische Tageszeitung The Daily Star (seit Januar 2011, täglich)
  • Zwei Züricher Tageszeitungen: Zürcher Unterländer und Zürichsee-Zeitung (seit Mai 2011, wöchentlich)

Seit August 2009 steht Str8ts als iPhone-Applikation zum Download zur Verfügung. Mittlerweile gibt es auch schon mehrere Bücher mit Str8ts-Rätseln und ein Brettspiel aus Holz.

Regeln und Begriffe

Das Spiel besteht aus einem Gitter mit 9 × 9 Feldern, insgesamt also 81 Felder in 9 Reihen und 9 Spalten. Einige dieser Felder sind schwarz, andere weiß. Zusammenhängende weiße Felder, sowohl in Zeilen- als auch in Spaltenrichtung 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 diese Kandidaten.

Für Str8ts gilt wie für Sudoku, dass zur Lösung keine Rechenkenntnisse erforderlich sind.

Beim Ausfüllen gelten die folgenden Regeln:

  1. Die weißen Felder müssen mit je einer Ziffer zwischen 1 und 9 gefüllt werden.
  2. Keine Ziffer darf in einer Zeile oder Spalte mehrfach vorkommen, egal ob in einem weißen oder in einem schwarzen Feld.
  3. Waagrecht oder senkrecht zusammenhängende weiße Felder dürfen nur Ziffern enthalten, die eine lückenlose Folge, also eine Straße, bilden, egal in welcher Anordnung.

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.

Schwierigkeitsstufen

"Teuflisches" Str8ts...
...und seine Lösung

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 der Schwierigkeitsstufe zugeordnet wird.

Varianten

Das normale Str8ts ist ein Quadrat von 9 x 9 Feldern, wovon einige schwarz sind. Die schwarzen Felder können beliebig angeordnet sein. In typischen Str8ts sind ca. 20 Felder schwarz, die Spanne geht von 1 bis 35.

Symmetrische Str8ts

Dabei ist das Muster der schwarzen Felder punktsymmetrisch um den Mittelpunkt des Spielfeldes. Solche Str8ts sehen harmonisch aus, sie sind aber beim Lösen nicht unterschiedlich zu asymmetrischen Str8ts.

Asymmetrische Str8ts

Asymmetrische Str8ts haben schwarze Felder mit unregelmäßigem Muster. Str8ts mit besonders hohem Schwierigkeitsgrad sind häufiger asymmetrisch.

Mini-Str8ts

Mini-Str8ts bestehen aus einem 4 x 4 oder 6 x 6 Felder großen Spielfeld. Einziger Regelunterschied: es werden nur die Ziffern von 1 bis 4 bzw. 6 verwendet. Mini-Str8ts sind schnell und meistens ohne Aufschreiben von Kandidaten zu lösen.

Transformationen

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:

  1. Drehung um 90°
  2. Drehung um 180°
  3. Spiegelung
  4. Spiegelung der Ziffernfolge

Spiegelung der Ziffernfolge bedeutet dabei, dass jeweils die Ziffer N durch die Ziffer 10-N ersetzt wird. Eine beliebiger Austausch von Ziffern, wie dies bei Sudoku funktioniert, ist wegen der Straßenregel nicht zulässig. Bei Str8ts können die Ziffern auch nicht durch Symbole oder Farben ersetzt werden, weil die Eigenschaft der geordneten Ziffernfolge verloren ginge.

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 dann weiter um das gleiche Str8ts in neuer Darstellung. Durch Transformation können 16 Varianten erzeugt werden.

Lösungswege

Mittelschweres Str8ts mit einem möglichen Lösungsweg

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 mal 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, dann kann oft eine davon ausgeschlossen werden, weil sie die 2. Regel, 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 von 1 bis 9 alle Ziffern 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, dann 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 in den von Sudoku her bekannten Arten 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, sodass 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 Spielregeln klein.

Bei ganz schwierigen Str8ts kann es aber durchaus auch 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. Immer dann, wenn eine neue Lösungsziffer gefunden wird, kann man deren Auswirkung auf die Kandidaten der Felder der gleichen Spalte oder Zeile eintragen. Immer dann, wenn sich in einem Feld die Kandidatenliste verringert hat, folgt aus der 3. Regel, dass sich möglicherweise weitere Kandidaten in den Feldern der zugehörigen Straßen ausschließen lassen.

Unmittelbare Anwendung der Regeln

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 natürlich eine 4 stehen. Die Straßen-Regel führt aber darüber hinaus zu weiteren wichtigen Schlussfolgerungen, sie wird deshalb auch zum „Herzstück“ des gesamten Spiels.

Basis-Lösungsmethoden

Straßen-Prüfung

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 die doppelte Länge der Straße, dann gibt es Ziffern, die sicher in der 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ßen-Regel 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. Dies 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 digits) 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 liegender 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ßen-Prü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 Webseite 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“.

Versteckte Einzelziffer

Sichere Ziffern in rot, mögliche in blau, versteckte sichere 3

Ein versteckte Einzelziffer (hidden single) ist eine sichere Ziffer, die in ihrer Straße nur in einem Feld vorkommt. 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.

Gestrandete Ziffer

Gestrandete 2

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: 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.

Gerade/Ungerade Paare

Enthält ein Feld einer Straße der Länge 2 nur gerade Ziffern, so kann man im benachbarten Feld alle gerade Ziffern streichen. Es können in dem benachbarten Feld nur Ziffern stehen, die um 1 verschieden sind.

Lange Straßen

Straßen mit einer Länge von 5 bis 7 Feldern schließen garantiert Ziffern in anderen Straßen der selben 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 weiße Ziffer in einem schwarzen Feld der Zeile oder Spalte, kann man weitere Ziffern ausschließen.

Weitere Lösungsmethoden

Mit den oben beschriebenen Basis-Lösungsmethoden lassen sich die meisten einfachen bis mittelschweren Str8ts lösen. Die im folgenden genannten weiteren Lösungsmethoden werden seltener gebraucht, sind aber für schwere, teuflische oder gar extreme Str8ts erforderlich.

Regel der großen Lücke

Ist in einem Feld ein Zahlen-Paar, und die Differenz der zwei Ziffern ist mindestens so groß wie die Länge der Straße, dann können diese beiden Ziffern in allen anderen Feldern gestrichen werden. Dies liegt daran, dass weder beide gemeinsam in einer Straße existieren können, noch doppelt vorkommen können. Jede der beiden Möglichkeiten schließt also das Vorkommen beider Ziffern an jeder andere Stelle aus. Keine der beiden Ziffern kann deshalb „sicher“ sein.

Beispiel sei ein Feld mit dem Paar 19 in einer Straße kürzer als neun Felder. Wäre irgendwo anders in der Straße eine 1, würde dort die 9 stehen. Wäre irgendwo anders eine 9, müsste dort eine 1 stehen, was aber beides nicht möglich ist, da in einer Straße mit acht oder weniger Feldern nicht 1 und 9 stehen können.

Regel der Zeilen/Spalten-Anzahl („Setti-Regel“)

Aus der Notwendigkeit, dass in der Lösung jede Ziffer genauso oft in Spalten wie Zeilen vorkommen muss, kann man bestimmen, wie oft eine Ziffer höchstens vorkommt, wenn die Anzahl der sicheren Felder für eine Ziffer in allen Spalten oder allen Zeilen kleiner neun ist. Kommt also eine Ziffer in einer Zeile nicht vor, muss es auch eine Spalte geben, in der sie nicht vorkommt (und umgekehrt). Dazu ist das gesamte Spielfeld zu untersuchen, was diese Lösungsmethode recht aufwendig macht.

Nackte Gruppen

Paar (naked pair): Kommen in zwei Feldern einer Zeile oder Spalte lediglich die gleichen zwei Ziffern vor, dann können diese beiden Ziffern aus den übrigen Feldern der Zeile bzw. Spalte gestrichen werden.

Paar 45

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 (naked triple): Kommen in drei Feldern einer Zeile oder Spalte lediglich die gleichen drei Ziffern 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 (naked quadruple): Kommen in vier Feldern einer Zeile oder Spalte lediglich die gleichen vier Ziffern 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.

Versteckte Gruppen

Verstecktes Paar 35

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-Gruppe

X-Wing:[4] 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 hierbei ist, dass eine Ziffer in einer Zeile sicher sein kann und gleichzeitig in der Spalte möglich, aber nicht sicher ist.

Die Felder, in denen die sichere Ziffer vorkommt, bilden ein Rechteck, in dem die Ziffer in einer der zwei diagonal gegenüber liegenden Eckenpaare als Lösung vorkommen muss. Die beiden Diagonalen bilden das X, das zum Namen X-Wing als Sudoku-Lösungsmethode geführt hat.

Wenn eine 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. Dies gilt entsprechend auch für X-Wings in Zeilenrichtung.

Eine Erweiterung der X-Wing-Logik auf drei Zeilen und Spalten wird Swordfish[5] 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[6] 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 5x5 („Starfish“) usw. erweitern, solange man es nur auf sichere Ziffern anwendet.

Hypothese und Widerspruch

Wenn es gar nicht weiter geht, hilft eine Hypothese (oder: was-wäre-wenn?, Ausprobieren, Ariadnes Faden, trial-and-error, 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. Man hat dann 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.

Logisch lösbar?

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.

Programmierbare Lösungswege

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 Internetseiten www.str8ts.com und www.str8ts.de. Dieser Solver enthält allerdings nicht alle oben beschriebenen Methoden, insbesondere auch nicht das abschließende Backtracking. Er kann deshalb auch nicht alle Str8ts lösen.


Backtracking-Methode

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ück gegangen 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.

Hilfen beim Lösen

Uhrzeigerstrichmethode: Eine Darstellung für mögliche Lösungen
Kandidatenpunkte

Die beim Sudoku bewährten Methoden zum Merken von Kandidaten können beim Str8ts genauso übernommen werden.

Die „Kandidatenliste“

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 aber auch durch farbige Punkte in zwei Farben die sicheren Kandidaten der beiden Richtungen markieren.

Die Methode kann bei kleingedruckten und schwierigen Str8ts unübersichtlich werden. Dann hilft nur kopieren und vergrößern des Rätsels.

Die „Uhrzeigerstrichmethode“

Für klein gedruckte Str8ts in Zeitungen ist die Uhrzeigerstrichmethode hilfreich, 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, kann man einen Kandidatenstrich einfach durchstreichen, wenn weitere Überlegungen diesen ausschließen. Diese Methode gilt als leserlicher als das Schreiben von kleinen Zahlen. Die Markierung sicherer Ziffern kann wieder durch zwei Farben erfolgen.

Punkte für Kandidaten notieren

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.

Erzeugen neuer Str8ts

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. Hierzu gehört die Symmetrie des Musters, weil insbesondere die häufig verwendete Punktsymmetrie um den Mittelpunkt zu einem ästhetisch befriedigenden 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 verwendet, 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. Dies 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 heraus stellen, dass die Schwierigkeit höher als gewünscht ist, können weitere Ziffern als Vorgaben eingesetzt werden. Dies verringert dann die Schwierigkeit bis zum gewünschten Level.

Literatur

  • Jeff Widderich, Andrew Stuart: STR8TS - Das neue Zahlenrätsel mit Suchtpotential, jezza! Verlag, Geltendorf 2009, ISBN 978-3-941969-00-1
  • Jeff Widderich & Andrew Stuart: STR8TS, Süddeutsche Zeitung GmbH, München 2010, ISBN 978-3-86615-810-8.

Weblinks

 Commons: Str8ts – Beispiele zu Strategien und Lösungen

Einzelnachweise

  1. www.str8ts.com – Die englischsprachige offizielle Str8ts-Seite der Erfinder von Str8ts.
    Hier gibt es jeden Tag je ein symmetrisches und ein asymmetrisches neues Str8ts zum Online-Spielen, ein einfaches Einsteiger-Str8ts, Mini-Str8ts in drei Schwierigkeitsstufen und wöchentlich ein extremes Str8ts, das besonders schwierig ist.
  2. www.str8ts.de – Die deutschsprachige offizielle Str8ts-Seite des jezza! Verlages
    Auch hier kann man die beiden täglichen Str8ts online spielen. Zusätzlich gibt es ein zunehmend umfangreiches Forum mit Erklärungen, Lösungsstrategien, besonderen Rätseln und Diskussionen zu extremen Str8ts.
  3. WAZ-Online – Spieleseite der WAZ
    Hier gibt es jeden Tag ein Str8ts zum Online-Spielen und ein 30-Tage-Archiv.
  4. X-Wing im Sudokuwiki
  5. Sword-Fish im Sudokuwiki
  6. Jelly-Fish im Sudokuwiki

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Sudoku — (jap. 数独 Sūdoku, kurz für 数字は独身に限る Sūji wa dokushin ni kagiru, wörtlich so viel wie „Isolieren Sie die Zahlen“) ist ein Logikrätsel und ähnelt lateinischen Quadraten. In der üblichen Version ist es das Ziel, ein 9×9 Gitter mit den Ziffern 1 bis 9 …   Deutsch Wikipedia

  • Sudoku — Not to be confused with Sodoku. A Sudoku puzzle …   Wikipedia

  • Backtracking — Der Begriff Rücksetzverfahren oder englisch Backtracking (deut. Rückverfolgung) bezeichnet eine mathematische Problemlösungsmethode innerhalb der Algorithmik. Backtracking arbeitet nach dem Prinzip der Tiefensuche Inhaltsverzeichnis …   Deutsch Wikipedia

  • Crossword — For other uses of crossword, see crossword (disambiguation) An American style crossword grid layout A crossword is a word puzzle that normally takes the form of a square or rectangular grid of white and shaded squares. The goal is to fill the… …   Wikipedia

  • Mathematical puzzle — Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules as do multiplayer games, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must …   Wikipedia

  • Alphabetische Liste der Spiele — Die Liste der Spiele führt alle Spiele (Gesellschaftsspiele, Kinderspiele, Brettspiele, Kartenspiele, Würfelspiele usw.) auf, zu denen es einen eigenen Artikel gibt. Siehe auch Thematische Liste der Spiele Liste der Pen Paper Rollenspiele Liste… …   Deutsch Wikipedia

  • Constraint-Satisfaction-Problem — Ein Constraint Satisfaction Problem (dt.: Bedingungserfüllungsproblem, abgekürzt CSP) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu… …   Deutsch Wikipedia

  • Mathematisches Rätsel — Ein mathematisches Rätsel ist ein auf mathematischen Sachverhalten basierendes Rätsel. Die mathematischen Sachverhalte stammen oftmals aus der Zahlentheorie oder der Geometrie. Ein berühmter Erfinder von solchen Rätseln war der Amerikaner Samuel… …   Deutsch Wikipedia

  • Rätsel — Ein Rätsel ist eine Aufgabe, die durch Denken gelöst werden muss. Rätsel können dem Zeitvertreib, der Unterhaltung und der Bildung des Rätsellösers dienen. Ihre Lösung wird teilweise durch irreführende, mehrdeutige Angaben erschwert. Schwierig zu …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”