Sudoku, Teil 4
Die Suche nach nackten und versteckten Einern, Paaren, Tripeln oder gar Quadrupeln und nach Zweiern mit Konsequenzen für betroffene Blöcke, Zeilen und Spalten ist recht mühsam und führt in schweren Sudoku allein nicht zum Ziel. In den einfachen Sudoku für Busse und Bahnen aber kann man sich nicht nur auf elementare Methoden beschränken, sondern auch zwischen ihnen wählen. Als Mensch sollte man ausnutzen, was ein Leben lang trainiert wurde und nicht viel Mühe macht. Also wird man nicht wie ein Computer alle Felder abgrasen, sondern die bewährte Mustererkennung einsetzen, die nach viel Übung so reflexhaft arbeitet wie man Fahrrad fährt.
+-------+-------+-------+
| 2 . . | . 7 8 | . . . |
| 6 . 1 | . 9 . | . 4 5 |
| . 9 . | . 4 . | 1 8 . |
+-------+-------+-------+
| . . 7 | . 2 6 | 3 5 . |
| . . 9 | 7 . . | . 1 6 | [1]
| 8 . 5 | . . 9 | . . . |
+-------+-------+-------+
| . 7 . | 4 3 . | 2 . . |
| . 1 2 | 5 8 . | 6 . 4 |
| . 3 8 | 9 . . | . . 1 |
+-------+-------+-------+
In diesem Sudoku würden Computer oder Buchhalter zu jedem freien Feld notieren, welche Ziffern noch möglich sind, um sofort 12 Felder ausfüllen zu können:
+-------+-------+-------+
| 2 . . | . 7 8 | 9 . . |
| 6 8 1 | . 9 . | 7 4 5 |
| . 9 3 | . 4 . | 1 8 . |
+-------+-------+-------+
| . 4 7 | . 2 6 | 3 5 . |
| . . 9 | 7 . . | . 1 6 |
| 8 . 5 | . . 9 | . . . |
+-------+-------+-------+
| . 7 6 | 4 3 1 | 2 9 . |
| 9 1 2 | 5 8 7 | 6 . 4 |
| . 3 8 | 9 6 . | . 7 1 |
+-------+-------+-------+
In den verbleibenden 31 Feldern fallen dadurch einige Möglichkeiten fort. Weitere Felder können ausgefüllt werden. Und bald ist man am Ziel.

Das mag für den Computer gut sein, nicht dagegen für den Menschen. Zum einen gehen für die Anfangsüberprüfung schon fünf Minuten drauf. Zum anderen sollte die Lösung auch ohne Notizen gefunden werden. Und wer sieht mit dieser Methode ohne Mühe zum Beispiel die rote vier, weil in ihrem Block samt ihrer Zeile und Spalte alle anderen acht Ziffern vorkommen? Erst nach dem Scheitern einfacherer Überlegungen hätte ich die vierte Zeile untersucht, in deren vier freien Feldern nur die Ziffern 1, 4, 8 und 9 vorkommen können, um dann möglicherweise zu sehen, daß für die zweite Position alle außer 4 ausscheiden. Viel wahrscheinlicher hätte ich schneller gesehen, daß in der letzten Position eine 9 stehen muß, woraus dann der Rest der vierten Zeile sich ergibt.

Woran liegt das? Der Mensch kann auch mit viel Training kaum erkennen, an welchen Stellen sich acht oder auch nur sieben verschiedene Ziffern kreuzen, er muß alle Felder abgrasen oder sich auf solche beschränken, in denen sich viele Ziffern kreuzen, vor allem die seltenen. Doch glücklicherweise kann ein Mensch sehr schnell einen holografischen Blick entwickeln, um die Postionen gleicher Ziffern zu erkennen. In Gedanken kann er dann ihre Zeilen und Spalten kreuzen und sehen, in welchen Blöcken nur noch ein Feld übrig bleibt. Auf diese Weise erledigt man zumindest einfache Sudoku immer schneller.

Ich will wenigstens einmal im Detail aufschreiben, wie diese Methode grundlegend funktioniert: Streicht man im Ausgangssudoku [1] alle Zeilen und Spalten mit Ziffer 1, so schrumpft es auf
  | a | d e f |
--+---+-------+
1 | X | . X X |
--+---+-------+
4 | . | . X X |
6 | X | . . X |
--+---+-------+
7 | X | X X . |
--+---+-------+
worin Zeilen mit Nummern 1 bis 9 und Spalten mit Buchstaben a bis i bezeichnet sind. Ein X bedeutet, daß in diesem Feld bereits eine Ziffer steht oder im zugehörigen Block eine 1 vorkommt. Schon der Augenschein sagt, daß an den Postionen 1d, 4a und 7f Einsen stehen müssen, womit für die letzte 1 nur noch 6e bleibt. Die Einsen sind damit allesamt auf einen Schlag erledigt:
+-------+-------+-------+
| 2 . . | 1 7 8 | . . . |
| 6 . 1 | . 9 . | . 4 5 |
| . 9 . | . 4 . | 1 8 . |
+-------+-------+-------+
| 1 . 7 | . 2 6 | 3 5 . |
| . . 9 | 7 . . | . 1 6 |
| 8 . 5 | . 1 9 | . . . |
+-------+-------+-------+
| . 7 . | 4 3 1 | 2 . . |
| . 1 2 | 5 8 . | 6 . 4 |
| . 3 8 | 9 . . | . . 1 |
+-------+-------+-------+
Praktisch macht man es natürlich einfacher und schneller: Zunächst ergeben sich die Einsen bei 1d und 7f. Die anderen beiden folgen dann ohne weiteres. Diesen Stiefel kann man weiter durchziehen. Für die 2 ergibt sich folgendes Teildiagramm:
  | b | d f | h i |
--+---+-----+-----+
2 | X | . . | X X |
3 | X | . . | X . |
--+---+-----+-----+
5 | . | X X | X X |
6 | . | X X | . . |
--+---+-----+-----+
9 | X | X . | X X |
--+---+-----+-----+
Es fallen alle fünf fehlenen Zweien, denn 3i ist einzige Möglichkeit im oberen rechten Block, 5b einzige in der fünften Zeile, 6h in der Spalte h und 9f in Zeile 9, woraufhin die letzte 2 nur noch bei 2d Platz hat.
+-------+-------+-------+
| 2 . . | 1 7 8 | . . . |
| 6 . 1 | 2 9 . | . 4 5 |
| . 9 . | . 4 . | 1 8 2 |
+-------+-------+-------+
| 1 . 7 | . 2 6 | 3 5 . |
| . 2 9 | 7 . . | . 1 6 |
| 8 . 5 | . 1 9 | . 2 . |
+-------+-------+-------+
| . 7 . | 4 3 1 | 2 . . |
| . 1 2 | 5 8 . | 6 . 4 |
| . 3 8 | 9 . 2 | . . 1 |
+-------+-------+-------+
Weiter geht es mit der 3, die nur dreimal vorkommt. Trotzdem sind die übrigen sechs Dreien sofort fällig:
+-------+-------+-------+
| 2 . . | 1 7 8 | . . 3 |
| 6 . 1 | 2 9 3 | . 4 5 |
| . 9 3 | . 4 . | 1 8 2 |
+-------+-------+-------+
| 1 . 7 | . 2 6 | 3 5 . |
| 3 2 9 | 7 . . | . 1 6 |
| 8 . 5 | 3 1 9 | . 2 . |
+-------+-------+-------+
| . 7 . | 4 3 1 | 2 . . |
| . 1 2 | 5 8 . | 6 3 4 |
| . 3 8 | 9 . 2 | . . 1 |
+-------+-------+-------+
Der Rest ist ein Kinderspiel, gleich ob man nun mit der 4 fortfährt oder einen Block nach dem anderen ausfüllt.

Wenn es auch nur selten so leicht wie im vorangehenden Beispiel ist, kann doch fast jedes Sudoku, daß nicht die Stufe 3 übersteigt oder als sehr schwer gekennzeichnet ist, auf dieser Basis gelöst werden: Zunächst geht man die Ziffern 1 bis 9 nach der beschriebenen Methode durch, um die Zahl der ausgefüllten Felder zumindest leicht zu erhöhen, wodurch eine Reihe von Blöcken, Zeilen und Spalten mit vier oder weniger freien Feldern entstanden sein sollte. Diese geht man durch und sucht in ihnen weitere versteckte Einer. Sobald ein Feld mit einer Ziffer ausgefüllt wird, schaut man sofort nach weiteren erzwungenen Positionen für diese Ziffer. Diese Vorgehensweise sollte samt gelegentlichen kleinen Zusatzkombinationen zur Lösung ausreichen.

Solange man mit diesem Verfahren nicht in eine Sackgasse gerät, ist es nicht nötig, Paare, Tripel usw. zu suchen, auch keine nackten Einer. Es ist aber von Vorteil, andere Kombinationen zu nutzen oder sich kurzzeitig besondere Umstände zu merken, wenn dadurch der eine oder andere Fortschritt mitgenommen werden kann. Zeitverschwendung aber ist es, solche Konstellationen systematisch zu suchen, zumal man sie sich so und so nicht alle merken kann. Vielmehr ist es wichtig zu ahnen, welche Objekte Fortschritt mit wenig Aufwand versprechen. Dazu gehören nicht nur die mit wenig freien Feldern, sondern auch die von einer neu gefundenen Ziffern betroffenen Objekte. Und wenn Zeilen unergiebig erscheinen, sollte man rechtzeitig auf Spalten und Blöcke wechseln oder umgekehrt. Auch Paare und Dreierketten freier Felder links liegen zu lassen, von denen man ahnt, daß sie sich erst gegen Ende auflösen werden, erspart Mühe und Zeit.

Allmählig ist es mir schon langweilig geworden, mit diesem Stiefel alle Sudoku der Stufe 3 in sieben bis fünfzehn Minuten lösen zu können, sofern mir kein Flüchtigkeitsfehler unterläuft. Und in den Bahnhofsbuchhandlungen sind die Hefte mit schwierigeren Rätsel schon recht selten. Trotzdem ist es wohl gut, ein paar hundert davon abzuhaken, um die Geläufigkeit für spätere Aufgaben zu erreichen, die nicht dadurch unlösbar werden sollen, daß die Routine für die einfachen Kombinationen fehlt und ich sie munter übersehe.
[1]  2...78...6.1.9..45.9..4.18...7.2635...
97...168.5..9....7.43.2...1258.6.4.389....1
Teil 1: Anfang
Teil 2: Einer
Teil 3: Paare
Teil 4: Raster

... link (9 Kommentare)   ... comment



Gewinn und Verlust
Wenn man 18 Prozent mehr Umsatz als Hysterie bezeichnen mag, dann hat es eine solche um die 26 Millionen in Lotto-Jackpot gegeben. Und sollte am Montag keiner gewonnen haben, dann wird er nächste Woche noch größer sein. Ab wann lohnt es sich für mich mitzuspielen?

Um das einschätzen zu können, habe ich mich nach dem Einsatz für ein Spiel erkundigt. Es sind wohl 75 Cent. Der Normalgewinn ist 37,5 Cent, daß selbst ohne Berücksichtigung der Gebühren der Jackpot etwa 37,5*140.000.000 Cent also mindestens 50 Millionen Euro betragen müßte, was wohl kaum erreicht werden wird, weil er vorher "geknackt" oder der Gewinnklasse 2 zugeschlagen wird.

Um aber ehrlich zu sein, habe ich nicht darüber nachgedacht, wann ich zum Lottospieler würde, sondern mir erneut die Frage gestellt, ab welcher Gewinnquote q(x) der normale Mensch bereit ist einen Betrag x zu setzen.

So blöd die Sendung "Deal or no deal" auch ist, bietet sie neben dem Lottospiel und dem Roulette dafür doch gewisse Anhaltspunkte. Anders als in den meisten Gewinnspielsendungen schwankt der zu erwartende Gewinn auf den einen Koffer nur wenig. Nur die von der "Bank" angebotene Quote wird immer besser, bis der Kandidat weich wird und um die 75 Prozent der zu erwartenden Summe aufgibt.

Während im Bereich eines Einsatzes von 10.000 bis 50.000 Euro offensichtlich die Gewinnquote deutlich über 120 Prozent liegen muß, daß ein Mensch seinen schon sicheren Gewinn weiterhin riskiert und im normalen Leben auch bei 200 Prozent keine 10.000 dafür vom Konto abheben würde, reichen ihm beim Lottospiel offensichtlich 50 Prozent.

Wenn die Quote q(x), ab der ein normaler Mensch einen Betrag x einsetzt eine stetige Funktion ist, dann muß irgendwo im Bereich von 0,75 und 10.000 Euro der Betrag b liegen, für den q(b)=1 ist, dessen Verlust so schmerzhaft ist wie freudig sein Gewinn, nicht mehr und nicht weniger. Ich würde b über 100 Euro sehen, sonst gäbe es nicht die Lotto-Systemspieler.

Ganz gerecht wird diese Überlegung dem Lotto aber nicht. Während im Fernsehen zwar hohe Gewinnsummen winken, sind sie doch in mehreren Schritten der Vervielfachung zu erwirtschaften. Beim Lotto aber winken Millionengewinne für 75 Cent. Die genauere Frage muß also lauten: Ab welcher Quote q(x,y) geht ein normaler Mensch auf eine Wette ein, wenn er den Betrag x einzusetzen hat und möglicherweise den Betrag y gewinnt?

Vielleicht hat schon einmal irgendeiner den Faktor w(z) bestimmt, mit dem der Betrag z überbewertet wird. Wenn die Entscheidungsgrenze bei q(x,y) liegt, dann muß w(-x)=q(x,y)w(y) sein. Ich würde dem normalen Menschen ungefähr die folgenden Werte unterstellen:
z in Euro  w(z)  w(-z)
----------------------
        1   1,0    0,9
      100   1,2    1,3
   10.000   1,4    1,7
1.000.000   2,0    3,0

... link (1 Kommentar)   ... comment



Cosmic Connection
Bild-Leser wissen mehr, sonst wäre ich gar nicht auf die Arte-Sendung "Cosmic Connection" am heutigen Abend aufmerksam geworden, auf die ich mich jetzt schon freue, denn sie wird sicherlich ein neues Lehrbeispiel für die Natur des Menschen sein, die wir den Außerirdischen besser verschweigen.

"Das UFO (Unidentifizierbares Fernsehobjekt) richtet sich zwar an Außerirdische, doch ist CosmicConnexion ebenfalls eine Aufforderung an die Bewohner der Erde, über ihre Existenz und ein mögliches Leben außerhalb des eigenen Sonnensystems nachzudenken." Aber eben nur in zweiter Linie. Wir wissen ja bereits, daß unsere Kleidung kein angewachsenes Fell ist. Nicht so die Aliens: "Während Außerirdische auf der Pioneer-Raumsonde lediglich eine Metallplatte mit einem Piktogramm der Gattung Mensch vorfinden können, werden sie bei CosmicConnexion von einem unbekleideten Moderatorenpaar durch die Sendung geführt."

Die auch in den Weltraum ausgestrahle Sendung wird sich nicht an interstellare Biologen richten, die sich hinter dem Mond, im Asteroidengürtel oder unter uns verstecken und schon viele nackte Menschen seziert haben. Sie wissen schon alles aus den üblichen Chart-Shows. Die Informationen sind wohl für Außerirdische bestimmt, die uns auf ihrem Vorbeiflug entlang der galaktischen Handelsstraßen nicht bemerkten, links liegen lassen oder nur unsere Entwicklung abwarten, bis Guido Westerwelle "auf gleicher Augenhöhe" mit ihnen verhandeln kann.

Und so wie eine Fliege sich gut überlegen sollte, meine Aufmerksamkeit zu erregen oder mir auf die Nerven zu gehen, so sollten wir uns laut Bildzeitung ebenfalls ruhig verhalten. Ufo-Forscher warnen vor den Folgen einer solchen Show, denn nicht alle Weltraumbewohner sind uns gut gesonnen. Sie könnten uns alle mit Mönchskutten einkleiden und in Bergwerken nach Kryptonit graben lassen oder uns gar jagen und töten, weil sie glauben, unsere Nierensteine fördern ihre Potenz. Später würden sie uns zu diesem Zwecke überzüchten und wie Gänse stopfen. Nicht alle sind so nett wie wir und die Amerikaner, es gibt auch Perser und Chinesen unter ihnen.

Und nun noch die Zuschauerfrage (Außerirdische sind von der Teilnahme ausgeschlossen) des heutigen Abends. Zu gewinnen gibt es ein Service aus vulkanischem Porzellan mit 12 fliegenden Untertassen.

Was ist größer?
Mars
Milky Way

  Ergebnis anzeigen

Erstellt von wuerg am 2006-09-30 16:40.

... link (8 Kommentare)   ... comment



Robin Wilson
Für wenige Euro habe ich das kleine Buch "Sudoku" von Robin Wilson zusammengeschweißt mit einem Abreißblock von Eberhard Krüger mit 200 Rätseln erstanden. Auf dem Einband verspricht das Buch "die besten Lösungsstrategien", um "Schritt für Schritt zur Sudoku-Meisterschaft" zu gelangen. Erläutert werden aber nur wenige einfache und für den Menschen gut geeignete Methoden. Zunächst das Auffinden von Einern, wenn in einem 3x9-Block eine Ziffer zweimal vorkommt, in einem Objekt nur noch wenige Positionen frei sind, die drei gemeinsamen Felder einer Zeile oder einer Spalte mit einem Block allesamt eine Zahl enthalten und in Zeile, Spalte und Block eines Feldes bereits acht verschiedene Ziffern vertreten sind. Fortgeschrittenen wird anschließend empfohlen, in jedes Feld die noch möglichen Ziffern klein einzutragen, um auf diese Weise nackte Paare oder Tripel zu finden, die dann zu Streichungen anderer kleiner Ziffern und hoffentlich auf Einer führen.

Natürlich kann man es mit diesen Methoden allein nicht zur versprochenen Meisterschaft bringen. Doch das habe ich auch gar nicht von einem kleinen Büchlein erwartet, auch wenn es auf dem Einband steht. Für die 200 Rätsel des Blockes reichen die beschriebenen Verfahren nicht aus. So kommt man in Nummer 199 mit Einern, Paaren und Tripeln nicht ans Ziel, während die Nummer 200 zur Lösung nichts als Einer erfordert. Die Staffelung der Rätsel nach Schwierigkeitsgrad ist also nicht gut umgesetzt. Doch wer kommt schon in die letzte Abteilung "die echte Herausforderung"? Insgesamt also eine Anleitung für wenig Geld und Anfänger, die das Bahnen- und Busse-Niveau nicht hinter sich lassen wollen.

... link (0 Kommentare)   ... comment



Herbstanfang
Hat sich eigentlich schon einer darüber beschwert, daß zum Herbstanfang immer noch die Sonne scheint, die Benzinpreise drastisch gesunken sind und der Weihnachtsverkauf begonnen hat? Es ist also die beste Zeit für Frederik, sich noch einmal in die Sonne zu legen, während die anderen für den Winter Süßigkeiten horten und die Kanister füllen.

... link (1 Kommentar)   ... comment



Sudoku, Teil 3
In den letzten Tagen begegneten mir Sudoku, bei denen meine im Teil 2 dargestellten Methoden versagten, die ich nur durch weitergehende Überlegungen lösen konnte. Und damit meine ich nicht so einfache Kombinationen wie in diesem Diagramm:
+-------+-------+-------+
| 1 2 # | . . . | 4 5 6 |
| . . . | . . . | . . . |
| . . . | . 3 . | . . . |
+-------+-------+-------+
Im rechten Block kann die 3 nur in der mittleren Zeile stehen, womit im linken Block für die 3 nur noch die mit # bezeichnete Postion bleibt. Das hätte auch eine vollständige Überprüfung der ersten Zeile (blaue Methode) erbracht. Natürlich fand der Computer oftmals von mir übersehene einfache Lösungen, doch nicht immer. Und es tröstet mich, daß in diesem Sudoku
+-------+-------+-------+
| . 6 7 | 2 5 . | . . 8 |
| . 2 . | . . . | . . . |
| . . . | 6 1 . | . 5 . |
+-------+-------+-------+
| 3 . . | . . . | . . . |
| 2 . 4 | . . 5 | 8 1 . | [1]
| . . . | 8 . . | 4 3 . |
+-------+-------+-------+
| . 3 2 | . . 8 | 9 . . |
| 7 . 1 | . 2 . | . . 5 |
| . . . | . 6 . | 3 . . |
+-------+-------+-------+
der Computer an der gleichen Stelle ins Grübeln kam wie ich:
+-------+-------+-------+
| . 6 7 | 2 5 3 | 1 . 8 |
| 1 2 5 | . 8 . | 7 6 3 |
| . . 3 | 6 1 7 | 2 5 . |
+-------+-------+-------+
| 3 . . | . . . | 5 . . |
| 2 . 4 | . 3 5 | 8 1 6 | [2]
| . . . | 8 . . | 4 3 . |
+-------+-------+-------+
| 6 3 2 | 5 . 8 | 9 . 1 |
| 7 . 1 | 3 2 . | 6 . 5 |
| . . . | . 6 . | 3 . . |
+-------+-------+-------+
Irgendwann hätte ich eine Fortsetzung gefunden, und sei es durch Fallunterscheidung, habe aber aufgegegeben, weil ich unbedingt wissen wollte, ob der Computer an dieser Stelle noch eine einfache Kombination findet. Auch er kam mit den Methoden des 2. Teils nicht weiter, fand aber zwei sogenannte nackte Paare, eines davon im mittleren Block, obwohl darin gemeinerweise nur drei Ziffern stehen:
  |  2 6  | 5 8 1 |  3 7  |
--+-------+-------+-------+--
  | 1     |       | 1 2   |
3 | 4     | 4     | 4   6 | 5
  | 7   9 | 7   9 |     9 |
--+-------+-------+-------+--
2 |       | +---+ | +---+ | 8
  |       | | 3 | | | 5 | | 1
4 | 7   9 | +---+ | +---+ | 6
--+-------+-------+-------+--
  | +---+ |       | 1 2   | 4
  | | 8 | |       |     6 |
  | +---+ | 7   9 |     9 | 3
--+-------+-------+-------+--
  | 5 3   | 2 6   |  8    |
Zweimal nackt (rot) stehen 7 und 9 unten links und müssen in der einen oder anderen Weise diese beiden Felder füllen, daß sie in den anderen Stellen (grün) nicht mehr vorkommen können, wo die kleinen 7 und 9 also gestrichen werden können. Und nicht immer hat man Glück wie hier, denn danach steht die 4 (blau) allein nackt da, und man ist einen Schritt weiter.

Grundsätzlich ist diese Vorgehensweise nicht neu. Es werden alle zulässigen Kombinationen innerhalb eines Blockes, einer Zeile oder einer Spalte in der Hoffnung überprüft, auf irgendwelche Beziehungen zu stoßen. Im Teil 2 betrachtete ich ein einfaches Beispiel:
    | . 8 . |
    | . 4 . |         | 2 4 5 7 8     |       |
----+-------+----   --+----------   --+-------+--
3 5 | A B C | 4 .   A | . . . o .     | 7 2 8 |
. 2 | 1 3 9 | 8 .   B | o . . o .     | 1 3 9 |
. 9 | 6 D E | 3 .   C | o . . . o     | 6 5 4 |
----+-------+----   D | o . o o .   --+-------+--
    | 2 . 7 |       E | o o . . o     |       |
    | 8 . 5 |
Die fetten schwarzen Ziffern waren vorgegeben, die freien Felder sind mit A bis E gekennzeichnet, und die Matrix in der Mitte gibt durch o wieder, welche Ziffer in welchem Feld noch möglich ist. Es gibt nur eine einzige Auswahl von fünf o, daß in jeder Zeile und Spalte genau eines steht. Sie ist blau hervorgehoben.

Normalerweise gibt es eine solche eindeutige Kombination nicht, man sucht auch nicht ewig nach ihr, sondern betrachtet nur die Zeilen und Spalten der Matrix, in der sich nur ein o befindet. Das sind die nackten Einer (rot) oder die versteckten Einer (grün). Hier nun die aktuelle Lage im mittleren Block:
    | . 5 . |
    | 2 8 3 |
    | 6 1 7 |           | 1 2 4 6 7 9   möglich
----+-------+------   --+----------------------
. 3 | A B C | 5 . .   A | o . o . o o   1 1 1 1
2 4 | D 3 5 | 8 1 6   B | . . o . o o   4 4 4 4
. . | 8 E F | 4 3 .   C | o o o o . o   2 2 6 6
----+-------+------   D | . . . . o o   7 9 7 9
    | 5 2 8 |         E | . . . . o o   9 7 9 7
    | 3 6 . |         F | o o . o . o   6 6 2 2
Diesmal gibt es keine eindeutige Lösung für den ganzen Block, vielmehr bleiben vier Möglichkeiten, die rechts dargestellt sind. Man erkennt sofort A=1 und B=4. Daß sich 7 und 9 die Felder D und E sowie 2 und 6 die Felder C und F teilen, muß man nicht unbedingt im Kopf behalten, denn mit A=1 und B=4 geht es an anderer Stelle weiter.

Für einen Menschen ist es mühsam, alle verbleibenden Möglichkeiten zu finden, und für den Computer (besser: den Pogrammierer) ist es schwer, daraus die einfachen Schlußfolgerungen zu ziehen. Deshalb suchen beide lieber nackte oder versteckte Paare. Ein nacktes Paar bezieht sich auf zwei Felder, in denen nur zwei gemeinsame Ziffern möglich sind. Hier sind es die Felder D und E mit den Ziffern 7 und 9. Ein verstecktes Paar wird aus zwei Ziffern gebildet, die nur in zwei gemeinsamen Felder vorkommen können. Hier sind es die Zifern 2 und 6 in den Feldern C und F.

Was hat man davon? Der Computer sieht solche nackten Paare leidenschaftlos und entfernt die beiden Ziffern, wo sie nunmehr nicht mehr vorkommen können. Ob ihm diese Streichung etwas einträgt oder nicht, interessiert ihn nicht. Doch hier stellt er im nächsten Schritt im Feld B eine 4 als nackten Einer fest. Die Folge ist eine 1 als nackter Einer in Feld A. Die restlichen vier Felder bleiben erst einmal offen. Auch der Rest des Sudoku wird mit den üblichen Einer-Methoden bewältigt.

Im Gegensatz zum Computer oder Buchhalter liegt es mir oder gar den meisten Menschen mehr, die versteckten Paare zu finden. Man geht einfach alle noch möglichen Ziffern durch, und wenn eine davon nur in zwei Felder paßt, dann merkt man sich diese oder malt die Ziffer zwischen die Felder, notfalls an eine Verbindungslinie. Ein Glücksfall ist eine zweite Ziffer mit den gleichen Feldern. Dann hat man einen verstecktes Paar gefunden.

Der Nutzen ist im Prinzip der gleiche wie beim Einer: Wenn beide Felder eines Paares in einem zu überprüfenden Objekt vorkommen, liefern sie die gleichen Beschränkungen wie zwei Einer. Doch wie findet man solche (versteckten) Paare? Normalerweise beim Abgrasen aller Blöcke, Zeilen und Spalten nach Ziffern, die nur noch zwei Felder haben. Das ist jedoch recht mühsam, und besser nutzt man Besonderheiten: Im aktuellen Beispiel kommen die Ziffern 2 und 6 in der linken und der mittleren Spalte bereits vor. Im Block bleibt für sie deshalb nur die rechte Spalte, wo aber nur zwei Felder frei sind.

Und wie geht es dann weiter? Ganz allgemeinen ist ein Paar eine nützliche Information für später. Oft sind es zwei Felder, die sowohl in einem gemeinsamen Block als auch in einer gemeinsamen Zeile oder Spalte liegen, so daß es direkt zu weiteren Schlüssen kommen kann. Und manchmal hat man Glück, wie im aktuellen Beispiel. Durch 2 und 6 in den Feldern C und F findet die 1 nur noch in Feld A Platz. Sitzt sie dort bleibt der 4 nur Feld B. Und schon ist man mit dem versteckten Paar genauso weit wie der Computer mit dem nackten, das man als Mensch dann natürlich auch schnell findet.

Mit dieser leicht fortgeschrittenen Überlegung gibt es in der Folge keine Probleme mehr:
+-------+-------+-------+
| . 6 7 | 2 5 3 | 1 . 8 |
| 1 2 5 | . 8 . | 7 6 3 |
| . . 3 | 6 1 7 | 2 5 . |
+-------+-------+-------+
| 3 . . | 1 4 # | 5 . . |
| 2 . 4 | . 3 5 | 8 1 6 |
| . . . | 8 . # | 4 3 . |
+-------+-------+-------+
| 6 3 2 | 5 . 8 | 9 . 1 |
| 7 . 1 | 3 2 . | 6 . 5 |
| . . . | . 6 . | 3 . . |
+-------+-------+-------+
Das Diagramm zeigt mit # das versteckte Paar aus 2 und 6 an. Es hat die rote 1 und die rote 4 zur Folge.
+-------+-------+-------+
| . 6 7 | 2 5 3 | 1 . 8 |
| 1 2 5 | . 8 . | 7 6 3 |
| . . 3 | 6 1 7 | 2 5 . |
+-------+-------+-------+
| 3 . . | 1 4 # | 5 . . |
| 2 9 4 | 7 3 5 | 8 1 6 | [3]
| . . . | 8 9 # | 4 3 . |
+-------+-------+-------+
| 6 3 2 | 5 7 8 | 9 4 1 |
| 7 . 1 | 3 2 . | 6 . 5 |
| . . . | . 6 1 | 3 . . |
+-------+-------+-------+
In der mittleren Spalte gibt es nur noch eine Lage für die fehlenden blauen Ziffern 7 und 9. Die rote 4, die rote 7 und die rote 9 sind direkte Folge, womit das nackte Paar ebenfalls aufgedeckt ist, obgleich es nie hätte gesehen werden müssen. Die blaue 1 hat keine andere Position in der sechsten Spalte mehr, was aber auch ohne das versteckte Paar nicht anders mehr ginge.
[1]  .6725...8.2..........61..5.3........2.
4..581....8..43..32..89..7.1.2...5....6.3..

[2]  .672531.8125.8.763..361725.3.....5..2.
4.35816...8..43.6325.89.17.132.6.5....6.3..

[3]  .672531.8125.8.763..361725.3..14.5..29
4735816...89.43.6325789417.132.6.5....613..
Teil 1: Anfang
Teil 2: Einer
Teil 3: Paare
Teil 4: Raster

... link (3 Kommentare)   ... comment



Sudoku, Teil 2
Jetzt habe ich einige Sudoku hinter mir, die Rate der Leichtsinnsfehler ist gesunken, und ich kann nunmehr auch als mittelmäßig bezeichnete Aufgaben ohne Zusatznotizen in zwanzig Minuten lösen. Den Lösungsweg eines nicht zu schweren Sudoku mit 28 vorgegebenen Ziffern habe ich aufgezeichnet, um mit der Vorgehensweise eines Computers zu vergleichen. Erstaunlicherweise ging das Programm völlig anders vor als ich und begann sofort mit ganz einfachen Kombinationen, die ich überhaupt nicht sah. Doch waren unsere Fortschritte gar nicht sehr verschieden, weil von beiden der gleiche Engpaß zu überwinden war, wie das bei einem ordentlichen Sudoku zu sein hat, auch wenn es leicht ist:


­ 8 ­
2 ­ ­
­ ­ 1

­ ­ ­
­ 8 ­
­ 4 ­

­ 2 ­
­ ­ 9
3 ­ ­

3 5 ­
­ ­ 2
­ ­ 9

­ ­ ­
1 3 9
6 ­ ­

­ ­ 4
­ ­ 8
­ 3 ­

1 ­ ­
­ 2 ­
­ ­ ­

2 ­ ­
­ ­ 7
8 ­ 5

­ ­ ­
­ 1 ­
7 4 ­

[Es ist ärgerlich, wie schlecht hier vor allem Tabellen umgesetzt werden. Das ist wohl der Preis dafür, daß der Kalender am rechten Rand ordentlich aussieht und für Absätze nur die Zeile zu wechseln ist. Ich ändere jetzt aber nichts an den Voreinstellungen und lebe mit den zu großem Abständen hier und dem zentrierten Text weiter unten.]

Erstaunlicherweise genügt sowohl dem Computer als auch mir die einfachste aller Grundideen: Für jedes Gebiet (Zeile, Spalte, Block) wird ein quadratisches Diagramm gezeichnet, daß zu allen offenen Feldern angibt, welche der fehlenden Zahlen noch ohne direkten Widerspruch eintragbar ist. Für den mittleren Block sieht das wie folgt aus:
    | . 8 . |
    | . 4 . |         | 2 4 5 7 8     |       |
----+-------+----   --+----------   --+-------+--
3 5 | A B C | 4 .   A | . . . o .     | 7 2 8 |
. 2 | 1 3 9 | 8 .   B | o . . o .     | 1 3 9 |
. 9 | 6 D E | 3 .   C | o . . . o     | 6 5 4 |
----+-------+----   D | o . o o .   --+-------+--
    | 2 . 7 |       E | o o . . o     |       |
    | 8 . 5 |
Blau markiert ist die einzige Möglichkeit, in jeder Zeile und in jeder Spalte genau eine gültige Kombination o zu haben, womit der Mittelblock vollständig gelöst ist. Im allgemeinen aber klappt das nicht so gut, und es lohnt sich auch nicht, für alle 27 Gebiete ein solches Bild zu malen. Doch ist es zumeist völlig ausreichend, mit der einen Methode die rot markierten Felder zu finden, in die nur noch eine Ziffer paßt, und mit der anderen Methode die grün markierten Ziffern, für die nur noch ein Feld bleibt.

Der Computer und meine kleine Tochter bevorzugen die rote Methode, mit der man jedes beliebige freie Feld testen kann: Sind in den drei Gebieten (Zeile, Spalte, Block) dieses Feldes acht verschiedene Ziffern, so ist die neunte die gesuchte. So einfach diese Methode auch ist, hat sie doch zwei Nachteile: In einem schweren Sudoku kommt man damit zumindest am Anfang nicht weit. Und von einfachen Fällen abgesehen sieht der Mensch nur schlecht, an welcher Stelle diese Methode Erfolg verspricht.

Ich bevorzuge deshalb die grüne Methode, obwohl sie vollständig angewendet den dreifachen Überprüfungsaufwand erfordert. Es ist deshalb wichtig, nur die erfolgversprechenden Objekte zu überprüfen. Das sind die mit wenig freien Feldern. Zu Beginn überprüfe ich für jede Ziffer alle Blöcke gleichzeitig, indem ich mir waagerechte und senkrechte Balken durch die Ziffer denke und schaue, in welchem Block nur noch ein Feld frei bleibt.

Im folgenden Vergleich meiner Lösung mit der des Computers entsprechen die Farben der Ziffern dieser roten bzw. grünen Methode, wobei ich allerdings blau benutze, wenn die grüne Methode nicht auf Blöcke, sondern auf Zeilen oder Spalten angewendet wird.

meine Lösung ­ Computerlösung
+-------+-------+-------+
| . 8 . | . . . | . 2 1 |
| 2 . . | . 8 1 | . . 9 |
| . . 1 | . 4 2 | 3 8 . |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| . . 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 . . | 2 . . | . . . |
| . 2 . | 4 . 7 | . 1 . |
| . . . | 8 1 5 | 7 4 2 |
+-------+-------+-------+
­
+-------+-------+-------+
| . 8 . | . . . | . 2 . |
| 2 . . | . 8 . | . . 9 |
| . . 1 | . 4 . | 3 . . |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| . . 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 . . | 2 . . | . . . |
| . 2 . | . . 7 | . 1 . |
| . . 3 | 8 . 5 | 7 4 . |
+-------+-------+-------+
Ich bin die Ziffern von 1 bis 9 einmal nach der grünen Methode durchgegangen, habe also darauf verzichtet, in einem zweiten Durchgang noch weitere Treffer zu finden. Es hätte auch ausgereicht, in jedem der sechs 3x9-Streifen nach doppelten Ziffern mit möglichen Konsequenzen zu suchen, obwohl dann die grünen Vieren unentdeckt geblieben wären. Aber ich versuche, das ganze Sudoku zu überblicken, was letztlich schneller ist als das Durchhecheln von 3x9-Streifen. Zum Dank blieben sofort zwei Einzelfelder übrig, die nach der roten Methode mit Siebenern zu besetzen waren. Danach folgt auf die gleiche Weise die rote 6. Als Ergebnis ist der mittlere waagerechte 3x9-Streifen bis auf zwei Feldpaare ausgefüllt. Um die kümmert man sich besser nicht, weil die darin möglichen Ziffern 4 und 7 bzw. 5 und 6 weitgehend vertauschbar sind. ­ Ich benutze die rote Methode nur in einfachen Fällen und zu Beginn gar nicht, weil in schweren Rätseln nichts herauskommt und für einfache zu viel Zeit für die Suche draufgeht. Für einen Computer liegen die Verhältnisse anders. Hier hat er Glück und findet die einzige rote Konsequenz, nämlich die rote 7 im mittleren Block. Nach diesem Anfang käme auch ein Mensch zügig voran. Der Computer findet nach der roten 7 die rote 2, sodann 8 und 5 gefolgt von 4 und 6. Weiter mit der roten Methode, jedoch orange dargestellt, geht es mit 9 und 3 gefolgt von 1, 2 und 7. Schließlich stellen die fett dargestellten Ziffern 8 und 1 den 3x9-Streifen bis auf vier Felder fertig. Es ist fast das gleiche Ergebnis erzielt, wie ich es mit meiner Methode erhielt. Es fehlen zwar einige Zahlen im Umfeld, dafür ist die strategisch wichtige orange 3 unten links gefunden, gleichwohl sie unmittelbar nichts nützt. Wegen ihrer abseitigen Lage, hätte ich sie bei Anwendung der roten Methode übersehen.
+-------+-------+-------+
| . 8 . | . 7 6 | . 2 1 |
| 2 . . | . 8 1 | . 7 9 |
| . . 1 | . 4 2 | 3 8 . |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| . . 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 . . | 2 . 3 | . . . |
| . 2 . | 4 . 7 | . 1 3 |
| . . 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
­
+-------+-------+-------+
| . 8 . | 3 7 6 | . 2 1 |
| 2 3 . | 5 8 1 | . . 9 |
| . . 1 | 9 4 2 | 3 8 . |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| . . 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 . . | 2 . 3 | . . . |
| . 2 . | 4 . 7 | . 1 3 |
| . . 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
Weil es so schön war, wiederhole ich die grüne Methode. Erwartungsgemäß erbringt sie kaum sofort sichtbaren Fortschritt. Auch die rote 6 nicht. So greife ich zur blauen Methode. Für Zeilen und Spalten mit zwei freien Feldern bringt sie nichts. Bei denen mit drei Leerstellen eigentlich auch nicht, doch beachte ich in solchen Fällen nebenbei rote Konsequenzen: In der letzten Zeile fehlen die Ziffern 3, 6 und 9, die zwar alle drei in mehreren Positionen möglich sind, doch stehen 6 und 9 beide bereits in der dritten Spalte, womit die rote Methode die rote 3 liefert. ­ Nun ist die rote Methode zunächst am Ende. Der Computer zieht die blaue der grünen Methode vor und findet eine Reihe von Ziffern, die ich nach meiner Methode im zweiten Durchgang ebenfalls erhielt. Nur die Lage bei den Dreiern ist etwas unterschiedlich. Als konsequenter Anwender der roten Methode erhält der Computer nun aber die roten Ziffern 5, 9, 3 und 6, gefolgt von der orange eingezeichneten 3. Der Unterschied zu meinem Diagramm ist weder groß noch von Bedeutung.
+-------+-------+-------+
| 9 8 5 | 3 7 6 | 4 2 1 |
| 2 3 4 | 5 8 1 | 6 7 9 |
| . . 1 | 9 4 2 | 3 8 5 |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| . . 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 . . | 2 . 3 | . . 6 |
| . 2 . | 4 . 7 | . 1 3 |
| . . 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
­
+-------+-------+-------+
| 9 8 . | 3 7 6 | . 2 1 |
| 2 3 . | 5 8 1 | . 7 9 |
| . . 1 | 9 4 2 | 3 8 . |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| 4 7 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 4 7 | 2 . 3 | 8 . . |
| . 2 8 | 4 . 7 | 9 1 3 |
| . 9 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
Die 3 im Block unten links erweist sich als der Durchbruch. Zunächst liefert die grüne Methode die oberen Dreien, im Anschluß die blaue Methode 5 und 9 in der vierten Spalte, dann 4 und 6 in der zweiten Zeile, gefolgt von 9, 5 und 4 in der ersten Zeile. Unmittelbare Konsequenz sind die beiden roten Ziffern. ­ Wieder hat die rote Methode nichts mehr ergeben, weshalb der Computer erneut zur blauen greift. Durch seine gnadenlose Konsequenz, auch Felder zu überprüfen, die für den Menschen wenig erfolgversprechend aussehen, findet er einige nützliche Belegungen mehr als ich. Warum aber nicht 4 und 6 in der zweiten Zeile?
+-------+-------+-------+
| 9 8 5 | 3 7 6 | 4 2 1 |
| 2 3 4 | 5 8 1 | 6 7 9 |
| . . 1 | 9 4 2 | 3 8 5 |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| . . 2 | 1 3 9 | . 6 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 . 7 | 2 9 3 | . 5 6 |
| . 2 8 | 4 6 7 | . 1 3 |
| 6 9 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
­
+-------+-------+-------+
| 9 8 . | 3 7 6 | . 2 1 |
| 2 3 4 | 5 8 1 | . 7 9 |
| . 6 1 | 9 4 2 | 3 8 . |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| 4 7 2 | 1 3 9 | . . 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 4 7 | 2 . 3 | 8 . . |
| . 2 8 | 4 6 7 | 9 1 3 |
| 6 9 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
Der Rest ist mechanische Arbeit. Die blaue Methode wird auf die letzte Zeile sowie die Spalten 3, 5 und 8 angewendet. Danach ist es einfach: Einmal um Uhrzeigersinn die Löcher auffüllen. ­ Auch der Computer kommt an die Stelle, wo die widerspenstigen Sechsen auf einen Schlag fallen. Der Rest ist gnadenlose Routine nach der roten Methode. Erst die roten, dann die orangen und schließlich die fetten Ziffern.
+-------+-------+-------+
| 9 8 5 | 3 7 6 | 4 2 1 |
| 2 3 4 | 5 8 1 | 6 7 9 |
| 7 6 1 | 9 4 2 | 3 8 5 |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| 4 7 2 | 1 3 9 | 5 6 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 4 7 | 2 9 3 | 8 5 6 |
| 5 2 8 | 4 6 7 | 9 1 3 |
| 6 9 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
­
+-------+-------+-------+
| 9 8 5 | 3 7 6 | 4 2 1 |
| 2 3 4 | 5 8 1 | 6 7 9 |
| 7 6 1 | 9 4 2 | 3 8 5 |
+-------+-------+-------+
| 3 5 6 | 7 2 8 | 1 9 4 |
| 4 7 2 | 1 3 9 | 5 6 8 |
| 8 1 9 | 6 5 4 | 2 3 7 |
+-------+-------+-------+
| 1 4 7 | 2 9 3 | 8 5 6 |
| 5 2 8 | 4 6 7 | 9 1 3 |
| 6 9 3 | 8 1 5 | 7 4 2 |
+-------+-------+-------+
Ich bin etwas enttäuscht zu sehen, wie ein Computer fast alle Sudoku mit der roten und der blauen Methode lösen kann, viele sogar mit der roten allein. Nicht weil ich oftmals Mühe mit ihnen habe, sondern weil ich in Bussen und Bahnen vorwiegend Sudoku mit vielen Vorgaben sehe, die wahrscheinlich alle ohne Probleme lösbar sind. Eigentlich muß man nur ein guter Buchhalter sein, sich in allen leeren Feldern die Restmöglichkeiten eintragen, um sodann nach Feldern mit nur noch einer Ziffer (rote Methode) oder nach einer Ziffer mit nur noch einem Feld (grüne bzw. blaue Methode) zu suchen.

Teil 1: Anfang
Teil 2: Einer
Teil 3: Paare
Teil 4: Raster

... link (2 Kommentare)   ... comment