Helmut's Sudoku Helper

Copyright 2010-2011 Helmut Saueregger

Welcome to Helmut's Sudoku Helper !

Import

Import Puzzle

Copy and paste your puzzle from various sources into the area to the right.

It is also possible to enter the numbers by hand: use "0" or "." for empty cells, single digits for solved cells. All other characters, including +,-,|,a,b,c,*,# etc. will be ignored.
The whole grid must contain exactly 81 cells (0-9 or a period).

Typical grid lines look like this: |64.|3..|5..|
or like this: | 5 . 3 | 8 1 9 | . . 6 |

Try it! Copy the next three lines into the import area and hit "Do it!":
500600800200040035060800000
700090000000000214400030000
020500000100070069300900100

Pencil marks are allowed instead of zeroes or periods. If used, pencil marks must form continuous strings of single digits without any intervening characters (except "+" and "-" which are commonly used within pencil marks)

To find out more, look at the "HSH Help" section .

Log:

FAQ - Helmut's Sudoku Helper

Is this yet another Sudoku solver ?

Good question.

Why would anyone need another Sudoku solving program, when there are already lots of them available? Why bother writing such a program ? And what is it that you can expect from it?

Helmut's Sudoku Helper is not there to solve the puzzle for you, but to help you during the solving process. The goal is not so much the final result that will be reached, but the way how to do it.

Helmut's Sudoku Helper is a tool that is designed to guide you through the solving process, but will leave you in control: for each single step, there will usually be a couple of good alternatives that are presented - together with a short explanation. The cells that will be affected by this step are highlighted, and it is up to you to choose which step to take.

I like to solve Sudoku puzzles in newspapers. With a pen. Real ink on real paper. In a newspaper, there are no pushbuttons 'show me all possibilities'.

Same here.

This Sudoku Helper does not rely on shortcuts or computer tricks. Like with pen&paper, we start with few clues and many empty cells. One by one, the cells will be filled with 'pencil marks' and solutions

Enjoy !

How do I start ?

You can copy/paste Sudokus from many sources all over the internet and import them into Helmut's Sudoku Helper. If the puzzle cannot be copied, or if you only have a printed version, just enter the position by hand: zeroes mean "empty", all other digits represent a solution. Like this:

000300500503819006000006000
050604072060090080230107050
000900000100763905006001000

Takes about 40 seconds.

Use as many spaces, letters or special characters as you like (+,-,|,a,b,c,*,# etc.) but do not use tabs.

The most important thing to remember is that a Sudoku has 81 cells, so there should be exactly 81 digits and/or period ('.') characters.

Can I print the Sudoku and continue on paper?

Yes, you can!

There are many interesting puzzles all over the web, and frequently the only option that is given by those sites is to solve them online (or they have a crummy 'print' facility that does not provide enough space to write in).

Helmut's Sudoku Helper can be printed using your browser's 'print' function (without scaling) on any 8 1/2 by 11, or "A4" sheet of paper, and the grid is big enough to hold all the pencil marks you need.

A perfect way to take those nice puzzles from the web with you on a plane, or solve the Sudoku at breakfast over a cup of coffee or tea.

Where are those nice puzzles ?

HSH has been tested with puzzles from these sites:

How do I export a position ?

Sometimes one would like to send a Sudoku position to someone else, maybe to show an interesting solution, or maybe to ask for help.

Use the "Save" function. Save will not store anything on your hard disk or in a "cookie", but just remember the position until you leave Helmut's Sudoku Helper. Every time a position is saved, a character representation of the grid - including pencil marks - is written to the 'log' area at the bottom right corner of the screen.

Copy (Ctrl-A, Ctrl-C) this text and insert it wherever you like: mail, word document, or maybe a Sudoku forum ...

Don't forget to add [code] and [/code] tags, to ensure proper alignment.

This is what it looks like:

[code]
+--------------------------+--------------------------+--------------------------+ 
| 234579  2579    234      | 134     8       49       | 14569   5679    124579   | 
| 23459   259     1        | 7       349     6        | 8       59      2459     | 
| 4789    6       48       | 5       149     2        | 149     3       1479     | 
+--------------------------+--------------------------+--------------------------+ 
| 269     4       7        | 26      269     58       | 3       1       58       | 
| 1       29      23       | 234     7       58       | 459     589     6        | 
| 36      8       5        | 136     136     49       | 7       2       49       | 
+--------------------------+--------------------------+--------------------------+ 
| 2578    3       268      | 9       26      1        | 56      4       578      | 
| 457     157     9        | 8       46      3        | 2       567     157      | 
| 248     12      2468     | 246     5       7        | 169     689     3        | 
+--------------------------+--------------------------+--------------------------+
[/code]

Can I import puzzles with pencil marks, too ?

Sure you can !

Never mind if someone added additional markup to the puzzle, it will usually import ok, like this one here:


+--------------------------+--------------------------+--------------------------+
| 47      89      1        | 56      2       56       | 3       89#     4-7      |
| 3       2       79       | 1       4       8        | 79*     5       6        |
| 6       48      5        | 3       9       7        | 24      28      1        |
+--------------------------+--------------------------+--------------------------+
| 19      16      8        | 7       36      4        | 5       23      239      |
| 2       7       3        | 9       5       1        | 6       4       8        |
| 5       69      4        | 8       36      2        | 1       379#    37a      |
+--------------------------+--------------------------+--------------------------+
| 8       34      6        | 2       1       9        | 4-7     37b     5        |
| 47      5       79       | 46      8       36       | 29      1       234      |
| 19      13      2        | 45      7       35       | 8       6       349      |
+--------------------------+--------------------------+--------------------------+ 

Do I have to do everything by hand ?

Well, yes - wasn't that the whole point ?

Still, sometimes it happens that you may be interested only in part of the solution process. A very difficult position, maybe. Then you would like to avoid the tedious early stages and start with the 'very hard'/'fiendish' parts.

Helmut's Sudoku Helper can perform the standard solution steps (not the 'advanced' steps) automatically for you.

'AUTOMATE BASICS' will try to solve all but the very hard puzzles that require advanced methods.

Which advanced techniques are available in Helmut's Sudoku Helper ?

Currently, Helmut's Sudoku Helper supports:

I'm not sure if I'll ever implement xy-chains, I don't particularly care for those and never look for xy-chains in pen&paper puzzles.

Uniqueness ('Unique Rectangle')

A valid Sudoku must have a single (unique) solution.

Any position that makes it possible to create another solution just by exchanging two candidates (the 'deadly pattern') is not possible in a valid sudoku.

Therefore, we can eliminate all possibilities that would create such a deadly pattern.

HSH is able to identify a very common class of deadly patterns, the 'Unique Rectangle' (UR). A Unique Rectangle consists of four cells that form a rectangle and contain exactly the same two candidates. If the corners of the rectangle are confined to two boxes, then the two candidates cannot occur in the same rows, columns or boxes outside the rectangle. It would be possible to create two solutions for the Sudoku by switching the two candidates.

This is one of the 'deadly' patterns that are impossible in a valid Sudoku. At least one of the four corners must contain a different number.

The 'Unique Rectangle' method aims at avoiding such a deadly pattern. This can be accomplished by removing one or both of the DP candidates from one or more corners of the rectangle.

In many cases, this leaves a 'Naked Single' in one of the corners ('Type 1' UR), but there are other types, depending on additional strong links in one or both of the DP candidates.

Example:

+----------------+----------------+----------------+
| 3    6    29   | 7    89   5    | 4    129  18   |
| 29   8    4    | 1    3    6    | 7    29   5    |
| 17   17   5    | 2    89   4    | 89   3    6    |
+----------------+----------------+----------------+
| 12   9    8    | 6    12   3    | 5    7    4    |
| 167  4    16   | 5    17   9    | 23   8    23   |
| 257  357  23   | 8    4    27   | 1    6    9    |
+----------------+----------------+----------------+
| 1589 2    139  | 4    57   17   | 6    19   138  |
| 4    13   7    | 9    6    8    | 23   5    123  |
| 689  15   69   | 3    25   12   | 89   4    7    |
+----------------+----------------+----------------+

In this position we can see candidates '2' and '3' in all four cells of the rectangle formed by rows 5 and 8 / columns 7 and 9.

If r8c9 were '2' or '3', the deadly pattern would arise. Therefore, r8c9 must be '1'.

Swordfish and Jellyfish

When we find two rows, where a certain candidate is restricted to the same two columns, that is called an 'x-wing'.

When we find three rows, where a candidate is restricted to the same three columns, that is called a 'swordfish'.

Same with four rows / columns. That's a 'jellyfish'.

Both patterns are rather rare, and it is extremely unlikely that you'll ever need the method for a real Sudoku. Chances are that you'll find a couple of wings before you spot the swordfish ...

This is one of the very few examples, where a swordfish is needed:

+--------------------------+--------------------------+--------------------------+ 
| 3469    13469   5        | 2       3469    8        | 7       34      1346     | 
| 7       8       69       | 34569   34569   13459    | 36      2       1346     | 
| 2346    12346   26       | 3467    3467    1347     | 9       5       8        | 
+--------------------------+--------------------------+--------------------------+ 
| 2456    7       3        | 8       456     45       | 1       9       26       | 
| 1       2469    269      | 34679   34679   3479     | 2368    38      5        | 
| 569     69      8        | 1       3569    2        | 4       7       36       | 
+--------------------------+--------------------------+--------------------------+ 
| 23689   2369    4        | 359     28      359      | 238     1       7        | 
| 238     5       1        | 47      28      47       | 238     6       9        | 
| 2389    239     7        | 39      1       6        | 5       348     234      | 
+--------------------------+--------------------------+--------------------------+ 

FAQ - Helmut's Sudoku Hilfe

Worum geht's hier eigentlich ?

Eine gute Frage!

Es ist ja nun nicht gerade so, dass es keine Sudoku Solver auf der Welt gäbe. Wozu also noch ein solches Ding ? Was will ich - der Autor - damit bezwecken und was kannst Du, geschätzter Besucher dieser Seite, davon erwarten:

'Helmut's Sudoku Hilfe' ist dazu da, Dich beim Lösungsweg zu unterstützen. Hier steht nicht primär das Ergebnis im Vordergrund, sondern Helmut's Sudoku Hilfe ist ein Werkzeug, das Dir hilft, Techniken zu üben und Rätsel selbst zu lösen !

Zu beinahe jedem Zeitpunkt während der Lösung eines Sudokus gibt es eine ganze Reihe von guten Alternativen. Diese werden übersichtlich angezeigt und Du kannst Dir eine davon aussuchen.

Zu jeder dieser Alternativen gibt es eine kurze Erklärung, und die beteiligten Zellen werden optisch hervorgehoben, sodass man mit einem Blick sieht, woraus der Lösungsschritt besteht und wie man ihn finden kann.

Ich selbst löse gern Sudokus in Zeitungen. In gedruckten Zeitungen gibt es keine Knöpfe, mit denen man sich alle Möglichkeiten in allen Zellen anzeigen lassen kann. Helmut's Sudoku Hilfe bietet solche Computertricks gar nicht erst an, weil man sie im realen Leben auch nicht zur Verfügung hat.

Genau wie mit Papier und Bleistift starten wir mit einigen wenigen Angaben und vielen leeren Kästchen. Diese werden dann, eines nach dem anderen, zunächst mit 'pencil marks/potential marks' (kleine Zahlen, die die Möglichkeiten anzeigen) und dann mit Lösungen gefüllt.

Viel Vergnügen !

Wie fange ich an ?

Du kannst aus vielen Quellen im Internet Sudokus hier einfach mittels 'Kopieren/Einfügen' importieren.

Wenn das nicht funktioniert, oder das Rätsel nur auf Papier vorliegt, kannst Du ein Sudoku auch direkt eingeben:

verwende '0' oder '.' für leere Kästchen, einzelne Ziffern für die vorgegebenen Zellen. Alle anderen Zeichen, wie z.B. +,-,|,a,b,c,*,# etc. werden ignoriert.

Keinen Tabulator verwenden!

Wichtig ist, dass insgesamt genau 81 Ziffern und/oder Punkte vorhanden sind.

Kann ich das Sudoku auch ausdrucken und auf Papier lösen?

Ja, das geht ganz leicht!

Oftmals findet man im Internet interessante Rätsel, die dann aber nur online zu lösen sind oder ausgedruckt nicht genügend Platz zum hineinschreiben bieten.

Helmut's Sudoku Hilfe ist so konzipiert, dass der gesamte Bildschirm ohne Skalierung bequem auf eine A4 Seite passt und das Sudoku selbst in angenehmer Grösse ausgedruckt wird.

Ideal, um Sudokus aus der online Ausgabe von Zeitungen oder aus einer speziellen Internet Sudoku Seite bequem am Frühstückstisch zu lösen oder auf Reisen mitzunehmen.

Wo finde ich solche Rätsel im Internet ?

HSH kann fast alles importieren, was sich irgendwie aus der jeweiligen Seite markieren lässt und ein Sudoku ist ;)

Solche Rätsel gibt es zum Beispiel auf:

Kann ich auch mittendrin wieder von vorne beginnen?

Aber sicher!

Es gibt zwei Methoden, wieder neu anzufangen:

  1. Dasselbe Rätsel noch einmal von vorne: die Auswahl 'ZUM ANFANG' stellt das Sudoku wieder so her, wie es zu importiert oder eingegeben wurde. Alle zwischendurch gespeicherten Spielstände bleiben erhalten.
  2. Komplett von vorn anfangen: die Auswahl 'ZURÜCKSETZEN' macht 'tabula rasa', löscht das aktuelle Rätsel und alle Spielstände dazu und präsentiert sich - klar und rein wie frisch gefallener Schnee - wie beim ersten Aufruf der Seite mit der Möglichkeit, ein neues Sudoku zu importieren.
    Eigentlich ist das dieselbe Funktion wie LADEN, nur dass die Anfangsposition automatisch gespeichert wird und daher immer zur Verfügung steht.

Heisst das, ich kann Spielstände speichern und später wieder laden?

Genau das heisst es.

Sobald ein Sudoku erfolgreich importiert oder eingegeben wurde, steht die Funktion SPEICHERN zur Verfügung. Dabei wird nichts auf der Festplatte oder in irgendwelchen 'Cookies' gespeichert, sondern 'Helmut's Sudoku Hilfe' merkt sich die Position bis zum Verlassen der Seite oder bis Du mit ZURÜCKSETZEN ein neues Rätsel startest.

Damit man sie leichter wiederfindet, erhält jede Position einen Zeitstempel (Tag, Datum, Uhrzeit) und einen frei wählbaren Namen.

Nach dem Laden werden nicht nur die gelösten Zellen angezeigt, sondern auch pencil marks und potential marks wiederhergestellt.

Kann ich mein (Zwischen-) Ergebnis anderen mitteilen ?

Manchmal möchte man seine Position an andere Sudoku Spieler schicken, bei einem sehr schwierigen Rätsel um Rat fragen, oder auch in einem Forum posten.

Das geht ganz leicht.

Zu diesem Zweck wird bei jedem Speichern die Stellung zusätzlich rechts unten in einem Format ausgegeben, das einfach kopiert und irgendwo anders eingefügt werden kann.

In Deinem Mail-Programm, zum Beispiel. Oder in einem Internet Forum ...

In den meisten Foren wird die Software phpbb verwendet. Wenn Du da einen Beitrag schreibst, fügst Du einfach die Position ein und fügst vor und nach der Position ein [code] bzw [/code] 'tag' ein, damit die Zahlen schön untereinander formatiert werden.

Das sieht dann so aus:

[code]
+--------------------------+--------------------------+--------------------------+ 
| 234579  2579    234      | 134     8       49       | 14569   5679    124579   | 
| 23459   259     1        | 7       349     6        | 8       59      2459     | 
| 4789    6       48       | 5       149     2        | 149     3       1479     | 
+--------------------------+--------------------------+--------------------------+ 
| 269     4       7        | 26      269     58       | 3       1       58       | 
| 1       29      23       | 234     7       58       | 459     589     6        | 
| 36      8       5        | 136     136     49       | 7       2       49       | 
+--------------------------+--------------------------+--------------------------+ 
| 2578    3       268      | 9       26      1        | 56      4       578      | 
| 457     157     9        | 8       46      3        | 2       567     157      | 
| 248     12      2468     | 246     5       7        | 169     689     3        | 
+--------------------------+--------------------------+--------------------------+
[/code]

Kann ich solche Sudokus mit 'pencil marks' auch importieren ?

Aber sicher!

Die Stellungen können auch weitere Sonderzeichen enthalten, wie in diesem Beispiel:


+--------------------------+--------------------------+--------------------------+
| 47      89      1        | 56      2       56       | 3       89#     4-7      |
| 3       2       79       | 1       4       8        | 79*     5       6        |
| 6       48      5        | 3       9       7        | 24      28      1        |
+--------------------------+--------------------------+--------------------------+
| 19      16      8        | 7       36      4        | 5       23      239      |
| 2       7       3        | 9       5       1        | 6       4       8        |
| 5       69      4        | 8       36      2        | 1       379#    37a      |
+--------------------------+--------------------------+--------------------------+
| 8       34      6        | 2       1       9        | 4-7     37b     5        |
| 47      5       79       | 46      8       36       | 29      1       234      |
| 19      13      2        | 45      7       35       | 8       6       349      |
+--------------------------+--------------------------+--------------------------+ 

Muss ich alles selbst tun ?

Na ja, im Prinzip ist das doch der Sinn der Sache, oder ?

Das Interessante beim Sudoku ist doch nicht, dass in Zeile 2/Spalte 3 die Zahl '7' steht. Sondern vielmehr, warum das so ist, bzw. dass man zu dieser Lösung nicht durch Probieren, sondern durch logische Schlussfolgerung gelangt ist.

Manchmal ist man jedoch trotzdem nur an einer bestimmten Stelle des Lösungsweges interessiert. Dann ist es oft mühsam, sich durch alle einfachen Schritte bis zu der interessanten Stelle durchzuklicken.

Helmut's Sudoku Hilfe kann daher Standard-Lösungsschritte automatisch durchführen.

'AUTOMATIK: alles' löst selbständig alle Rätsel bis auf jene Sudokus, die fortgeschrittene Spezialtechniken erfordern.

Welche fortgeschrittenen Spezial - Techniken kennt HSH ?

Zur Zeit findet Helmut's Sudoku Hilfe folgende Muster:

Einige dieser Muster (xy-wing und xyz-wing) findet man relativ leicht direkt aus den pencil marks im Rätsel selbst. Auch die Methoden, die auf dem Prinzip der Eindeutigkeit der Lösung basieren ('unique rectangles', 'big universal grave') können direkt im Rätsel angewendet werden.

Für die meisten anderen Techniken verwendet man am besten die sogenannten 'Nataraj Diagramme'

Was sind Nataraj Diagramme ?

Jene Methoden, die auf strong link / weak link Beziehungen beruhen, werden extrem erleichtert, wenn man diese Beziehungen visualisiert. Das geht auf dem Papier ganz einfach, indem man kleine Zeichnungen - eine pro Kandidat - anfertigt, in denen diese Beziehungen direkt ablesbar sind, die 'Nataraj-Diagramme'.

Für jede Zelle, in denen der betreffende Kandidat in den pencil marks vorkommt (die Zahl also noch möglich ist), wird im betreffenden Diagramm ein Punkt oder kleiner Kreis gezeichnet. Falls diese Zelle aber nur zwei Möglichkeiten hat, z.B. '14', dann wird im Diagramm jeweils die andere Zahl anstelle des Punktes geschrieben, also im Diagramm für '1' kommt die Zahl '4' in die Zeichnung, im Diagramm für '4' die Zahl '1'. Damit ist auf einen Blick erkennbar, dass dies eine sogenannte 'zweiwertige' Zelle ist. Solche Zellen spielen bei den xy(z)-wings, w-wings und m-wings eine grosse Rolle.

Wenn in einer Zeile, Spalte oder Box nur zwei Stellen sind, an denen die betreffende Zahl vorkommen kann, dann verbinden wir die beiden Punkte bzw. Zahlen im Nataraj Diagramm mit einer Linie. Diese Linie zeigt an, dass hier ein 'strong link' existiert.

Ein Beispiel:

+-----------------------------------------------------------------------+
|  5      9      4      |  71     71     6      |  2      8      3      |
|  2      7      3      |  94     94     8      |  1      5      6      |
|  1      8      6      |  2      3      5      |  947    47     947    |
|-----------------------+-----------------------+-----------------------|
|  347    2      9      |  5      8471   71     |  83467  34671  471    |
|  347    31     5      |  8471   6      9      |  8347   3471   2      |
|  8      6      71     |  471    2      3      |  47     9      5      |
|-----------------------+-----------------------+-----------------------|
|  6      31     82     |  89371  8971   71     |  5      34712  9471   |
|  9      5      82     |  83671  871    4      |  367    36712  71     |
|  37     4      71     |  9361   5      2      |  936    361    8      |
+-----------------------------------------------------------------------+ 

Versuchen wir einmal, in diesem Sudoku das Nataraj Diagramm für die Zahl '1' zu zeichnen.

In der ersten Box ist 1 schon gelöst, langweilig. Aber in der zweiten Box - da kommt '1' zweimal vor, jeweils mit '7' in einer zweiwertigen Zelle. Wir schreiben zwei kleine '7' in das Diagramm und verbinden die beiden mit einer Linie.

In Box 4 kommen wieder zwei Zahlen (3 und 7), und weil wir nur zwei Einträge in dieser Box haben, verbinden wir sie mit einer Linie.

Box 5 erhält drei Punkte und einmal '7', keine Linie in der Box, aber in Spalte 6 kommt '1' ja nur zweimal vor, daher eine senkrechte Linie. Und so weiter. Fertig gezeichnet sieht das dann so aus:

Im zweiten Diagramm sieht man sehr schön das 'x-wing' Muster. Der Name kommt übrigens aus den Star Wars Filmen, der x-wing ist ein Fluggerät mit charakteristischen vier Flügeln, so wie hier gezeichnet:

Wenn eine Zahl in einer Zeile nur in zwei Spalten vorkommen kann, und in einer anderen Zeile ebenfalls genau zweimal und in denselben beiden Spalten, dann kann die Zahl nirgendwo anders mehr vorkommen als in genau diesen vier Zellen.

Das x-wing Muster ist in den Nataraj Diagrammen mit ein wenig Übung extrem leicht zu sehen, hingegen in den pencil marks unter den vielen anderen Kandidaten sehr schwer zu erkennen.

Im Nataraj Diagramm für '1' ist übrigens ein weiteres Muster zu finden: der 'skyscraper'.

In Spalte 2 und Spalte 6 finden sich auch - genau wie beim x-wing - zwei parallele Linien. Diese sind aber nun nicht genau gleich lang und enden daher auch nicht in genau denselben Zeilen.

Wenn einander die beiden Linien zumindest an einem Ende 'sehen', dann muss die betreffende Zahl zumindest in einem der beiden anderen Enden vorkommen. In unserem Beispiel 'sehen' sich die beiden unteren Enden der Linien (beide enden in Zeile 7), daher ist entweder Zeile 5, Spalte 2 gleich '1', oder Zeile 4, Spalte 6 (oder sogar beide). Das bedeutet aber, dass Zeile 5, Spalte 4 - wo noch ein Punkt steht - nicht '1' sein kann.

Der Name 'skyscraper' kommt vermutlich daher, weil in Manhattan ein charakteristischer Wolkenkratzer, das 'Citicorp building', genau diese Form hat: parallele Kanten und ein schräges Dach. Man soll sich nur nicht zu sehr von dem Bild leiten lassen - beim Sudoku können solche Wolkenkratzer auch liegend vorkommen!

Was bedeutet 'strong link' und 'weak link' und wozu dienen diese linken Dinger?

Vorsicht, 'Logik' !

Sudoku ist bekannt als Logik-Rätsel. Das bedeutet, dass die Lösung nicht durch Vermuten, Probieren oder gar 'Eingebung' gefunden werden muss, sondern logisch - durch Schlussfolgerungen - abgeleitet werden kann.

Strong links und weak links sind nützliche, einfach zu erkennende Beziehungen zwischen Zellinhalten, die in Sudokus immer wieder vorkommen, nämlich:

Beispiele für 'strong' bzw. 'weak' links

+--------------------------+--------------------------+--------------------------+ 
| 9       12      8        | 14      3       6        | 5       7       24       | 
| 12      3       7        | 9       5       14       | 8       6       24       | 
| 5       6       4        | 7       2       8        | 3       19      19       | 
+--------------------------+--------------------------+--------------------------+ 
| 7       5       3        | 24      1       24       | 9       8       6        | 
| 6       8       1        | 5       7       9        | 4       2       3        | 
| 4       9       2        | 8       6       3        | 1       5       7        | 
+--------------------------+--------------------------+--------------------------+ 
| 128     12      6        | 3       4       125      | 7       19      1589     | 
| 128     4       5        | 12      9       7        | 6       3       18       | 
| 3       7       9        | 6       8       15       | 2       4       15       | 
+--------------------------+--------------------------+--------------------------+ 

Wozu aber die ganze schöne Logik ?

Bis auf wenige Ausnahmen beruhen alle fortgeschrittenen Methoden auf diesen drei Erkenntnissen:

  1. Links sind immer symmetrisch (in der Sprache der Logik lauten die Verknüpfungen "ODER" bzw. "NICHT UND" )
  2. ein Kandidat, der die beiden Enden eines 'strong link' sieht, kann eliminiert werden
  3. die Abfolge 'strong link','weak link','strong link' ist äquivalent zu einem einzelnen strong link

Zuerst die Kombination strong-weak-strong: verknüpfen wir doch in unserem Beispiel einfach die Spalten 1 und 4. Wir fangen bei der Zelle Zeile 7 Spalte 2 an.

erste Zeile und letzte Zeile dieser logischen Abfolge zusammengenommen sind ein neuer 'strong link', nämlich:

Wenn Zeile 7, Spalte 2 nicht '1' ist, dann ist Zeile 8, Spalte 4 gleich '1'.

Damit sieht es aber für die Zahl 1 in der Zeile 8, Spalte 1 finster aus: denn egal ob jetzt das eine Ende des neuen strong links stimmt oder das andere Ende, in jedem Fall ist die Zahl '1' in der Box 7 schon besetzt. Das ist das Prinzip des 'skyscraper', steckt aber auch - in leicht abgewandelter Form - hinter all den 'wings', die mittels der Nataraj Diagramme gefunden werden können.

Bei x-wing, skyscraper, kite und turbot fish werden alle beteiligten strong links durch gerade Linien im Nataraj Diagramm repräsentiert, beim m-wing handelt es sich um einen strong link innerhalb einer Zelle (durch eine Ziffer repräsentiert) und zwei Linien, beim w-wing um eine Linie und zwei (gleiche) Ziffern.

Eindeutigkeit ('Unique Rectangle')

Ein Sudoku muss immer eine eindeutige Lösung haben.

Eine Position, in der es möglich ist, einfach durch vertauschen zweier Kandidaten eine weitere Lösung zu erzeugen - ein charakteristisches Muster (auf Englisch 'deadly pattern' genannt) - darf in einem Sudoku nicht vorkommen.

Daher können wir alle Kandidaten eliminieren, die zu so einem 'deadly pattern' führen würden.

HSH findet eine besonders häufige Klasse von deadly patterns, nämlich das 'unique rectangle (UR)'. Dabei stehen vier Zellen in einem Rechteck, und enthalten genau dieselben zwei Zahlen. Wenn je zwei Ecken des Rechtecks dann auch noch in derselben Box stehen, dann können die beteiligten beiden Zahlen weder in den beiden Zeilen noch in den beiden Spalten und auch nicht in den beiden Boxen anderswo vorkommen. Sie könnten daher vertauscht werden und würden eine weitere gültige Lösung ergeben.

Das ist das Muster, welches nicht sein darf.

Die Methode 'Unique Rectangle' (also 'eindeutiges Rechteck') zielt also darauf ab, ein nicht eindeutiges Rechteck zu vermeiden. Zum Beispiel eben, indem aus einer oder mehreren der vier Ecken des Rechtecks Kandidaten eliminiert werden. Im einfachsten Fall bleibt dann in einer Ecke eine einzige Zahl übrig (ein sogenanntes Typ I UR), andere Typen von URs berücksichtigen eventuell vorhandene 'strong links', um weitere Eliminierungen vorzunehmen.

Ein Beispiel:

+----------------+----------------+----------------+
| 3    6    29   | 7    89   5    | 4    129  18   |
| 29   8    4    | 1    3    6    | 7    29   5    |
| 17   17   5    | 2    89   4    | 89   3    6    |
+----------------+----------------+----------------+
| 12   9    8    | 6    12   3    | 5    7    4    |
| 167  4    16   | 5    17   9    | 23   8    23   |
| 257  357  23   | 8    4    27   | 1    6    9    |
+----------------+----------------+----------------+
| 1589 2    139  | 4    57   17   | 6    19   138  |
| 4    13   7    | 9    6    8    | 23   5    123  |
| 689  15   69   | 3    25   12   | 89   4    7    |
+----------------+----------------+----------------+

In diesem Rätsel stehen die Zahlen 2 und 3 in vier Zellen, die genau in einem Rechteck angeordnet sind, nämlich in Zeile 5 und Zeile 8, sowie Spalten 7 und 9.

Wenn nun in Zeile 8, Spalte 9 nicht "1" stünde, dann könnte man für das Sudoku zwei Lösungen finden. Daher muss Zeile 8, Spalte 9 gleich "1" sein.

'Schwertfisch' und 'Qualle'

Das Muster, bei dem eine Zahl in zwei Zeilen nur in genau denselben zwei Spalten vorkommen kann, kennen wir bereits unter dem Namen 'x-wing'.

Wenn eine Zahl in drei Zeilen genau in denselben drei Spalten vorkommt, dann nennt man das einen Schwertfisch ('swordfish').

Dasselbe mit vier Zeilen bzw. Spalten heisst Qualle ('jellyfish').

Beide Muster sind ziemlich schwer zu finden und werden auch extrem selten für die Lösung von Sudokus gebraucht. Meist findet man einen anderen 'wing' eher.

Hier eines der ganz seltenen Beispiele, wo man tatsächlich einen Schwertfisch braucht:

+--------------------------+--------------------------+--------------------------+ 
| 3469    13469   5        | 2       3469    8        | 7       34      1346     | 
| 7       8       69       | 34569   34569   13459    | 36      2       1346     | 
| 2346    12346   26       | 3467    3467    1347     | 9       5       8        | 
+--------------------------+--------------------------+--------------------------+ 
| 2456    7       3        | 8       456     45       | 1       9       26       | 
| 1       2469    269      | 34679   34679   3479     | 2368    38      5        | 
| 569     69      8        | 1       3569    2        | 4       7       36       | 
+--------------------------+--------------------------+--------------------------+ 
| 23689   2369    4        | 359     28      359      | 238     1       7        | 
| 238     5       1        | 47      28      47       | 238     6       9        | 
| 2389    239     7        | 39      1       6        | 5       348     234      | 
+--------------------------+--------------------------+--------------------------+ 

Welche anderen fortgeschrittenen Techniken kommen noch?

Schwer zu sagen. Wenn ein Sudoku mit den hier bereits verfügbaren Techniken nicht lösbar ist, dann interessiert es mich eigentlich nicht mehr. Ein paar kleine Verallgemeinerungen der verfügbaren Lösungsmethoden sind aber auch dann möglich und nützlich, wenn man mit Papier und Bleistift bzw. Kugelschreiber 'arbeitet':

Auf der Basis der Nataraj Diagramme kann man zum Beispiel die (multi-) coloring Methode nutzen, das ist das Verbinden von strong links (Linien im Nataraj Diagramm) durch jeweils einen 'weak link' (die Enden der Linien 'sehen' einander), ebenso der 'Transport' von sogenannten 'flügellahmen' wings, also solche, die selbst keine Eliminierungen erzeugen, aber als Baustein für weitere Schlussfolgerungen dienen.

Diese Techniken kommen vermutlich hier in absehbarer Zeit noch dazu. Möglicherweise auch xy-chains, die mich persönlich aber nicht besonders interessieren.

15.August 2010

Fragen, Anregungen und Wünsche an: helmut@saueregger.at

Viel Spass beim Sudoku-Lösen !