Sudoku - nur weiter mit Probieren?

[MacLeod]

Hi, zunächstmal danke an alle.

Vorallem danke Surbier für den Tip mit den besseren Programmen. Sehr hilfreich.

Jetzt habe ich betreffendes Sudoku in den Solver gehackt und siehe da: "Forcing Chains"
Wie Euklid schon schrieb: "Wenn hier eine 5 reinkommt.... 6 Felder Später -> widerspruch"

Das würde ich persönlich eben schon als "Raten" bezeichnen, weil mir keine technik bekannt ist, mit der ich herausfinde welche Zahl ich testen soll.

Und dieses Rätsel ist aus der Endrunde der 2. Deutschen Sudokumeisterschaft 2006...

Man muss sich wohl damit abfinden, dass man manchmal Probieren muss..
Schade aber ist halt so.

[berni]

Jetzt habe ich betreffendes Sudoku in den Solver gehackt und siehe da: "Forcing Chains"
Wie Euklid schon schrieb: "Wenn hier eine 5 reinkommt.... 6 Felder Später -> widerspruch"

Das würde ich persönlich eben schon als "Raten" bezeichnen, weil mir keine technik bekannt ist, mit der ich herausfinde welche Zahl ich testen soll.

Das ist eben das Problem: Wo enden logische Schlußfolgerungen, und wo beginnt "raten"? Wenn ich so will, kann ich selbst die einfachsten Schlußfolgerungen als "raten" ansehen: "1 geht nicht, weil da in der Zeile schon eine 1 steht. 2 geht nicht, weil da in der Spalte schon eine 2 steht..." Und am Ende habe ich auch hier 9 Fälle ausprobiert und einer hat zum Ziel geführt.

Wenn man mal etwas drüber nachdenkt stellt man fest, dass wenn man auf "raten" komplett verzichten möchte, das effektiv heißt, dass man nur noch ein bereits komplett ausgefülltes Sudoku lösen kann.

Ich hab' inzwischen den Eindruck, dass die Grenze für jeden wo anders ist, nämlich da, wo man die Fallunterscheidung nicht mehr im Kopf hinbekommt.

Berni

[MacLeod]

Ok dann eben anders: Streiche Raten setze Fallunterscheidung.

Zurück zur eigentlichen Frage:
Wann und wo setze ich die Fallunterscheidung an? Gibt es einen Punkt in einem Sudoku an dem man diese Technik verwenden sollte? Gibt es eine Strategie/Technik an welcher Stelle man mit der Fallunterscheidung anfängt, denn Sie führt ja nicht an jeder Stelle zum Widerspruch.

[berni]

Zurück zur eigentlichen Frage:
Wann und wo setze ich die Fallunterscheidung an? Gibt es einen Punkt in einem Sudoku an dem man diese Technik verwenden sollte? Gibt es eine Strategie/Technik an welcher Stelle man mit der Fallunterscheidung anfängt, denn Sie führt ja nicht an jeder Stelle zum Widerspruch.

Ich glaube, da könnte man ein ganzes Buch zu füllen. Ein paar Ansätze:

• Wo man anfangen sollte? Am Besten an einer Stelle, wo es nur zwei Möglichkeiten gibt und beide Möglichkeiten viele weitere leichte Schlußfolgerungen zulassen. Da besteht dann eine gute Chance, dass man bei einem Fall leicht zum Widerspruch kommt.
  
• Bei der Fallunterscheidung kann man auch ein Auge drauf haben, ob es nicht Felder gibt, die in beiden Fällen die gleiche Zahl enthalten müssen. Manchmal braucht man dann nämlich die Fallunterscheidung garnicht weiter fortsetzen, sondern kann mit dieser neuen Zahl weitermachen. Das geht insbesondere recht gut, wenn man beide Fälle parallel abarbeitet: Der eine Fall ist eine kleine Zahl links unten, der andere rechts unten.
  
• Und mit welchem von den beiden Fällen beginnt man? Die Geister scheiden sich da, aber ich denke, es ist sinnvoll, den Ansatz zu versuchen, bei dem man vermutet, dass er schnell zum Widerspruch führt. Das hat nämlich den Vorteil, dass die Gefahr, sich während der Fallunterscheidung zu vertun, kleiner wird und zudem verringert es die Gefahr von verschachtelten Fallunterscheidungen.
  
• Zuletzt noch die Frage, wann man damit anfangen sollte. (Ich gehe hierbei von Wettbewerbsbedingungen aus.) Die Frage ist sehr schwer zu beantworten. Meiner Erfahrung nach macht es Sinn, damit recht früh anzufangen; aber erst, wenn man einen gewissen Überblick über das Sudoku gewonnen hat. Letzteres hilft in der Regel, einen geeigneten Startpunkt zu wählen.
  

[euklid]

Wie Euklid schon schrieb: "Wenn hier eine 5 reinkommt.... 6 Felder Später -> widerspruch"

Nur der Vollstaendigkeit halber: Das habe ich nicht gemeint und geschrieben.

Ich habe geschrieben: Falls an Position1 eines fiktiven Sudokus die Ziffer 2 reinkommt und dies an einer anderen Position2 die Ziffer 6 erzwingt, dann fuehrt das an einer weiteren Position3 dazu dass dort sowohl die Ziffer 2 als auch die Ziffer 6 eingetragen werden muesste. Also ist an Position1 keine Ziffer 2.

Das ist eine Ueberlegung, die nur 3 Felder betrifft und leicht im Kopf durchgefuehrt werden kann.

Zusammenfassend koennte man sagen: Fortgeschrittene Methoden sind teilweise nicht mehr dazu da, zu zeigen, dass an einer Stelle eine bestimmte Zahl reinkommt, sondern um zu zeigen, dass an einer Stelle eine bestimmte Zahl NICHT reinkommt. Wenn es in einem 3x3 Kaestchen 3 Moeglichkeiten gibt, eine bestimmte Ziffer einzutragen und ich eine von den dreien ausschliessen kann, dann ergibt sich vielleicht auf den verbleibenden 2 Feldern ein Paerchen und das Sudoku ist einfachst zu loesen.

Ich weiss nicht wer Nonogramme kennt. Das sind die Malraetsel, wo man in waagrechter und senkrechter Richtung Informationen erhaelt, welche Bloecke von Kaestchen man anmalen muss. Hier ist die Information, dass ein Kaestchen weiss bleiben muss genau so wichtig als die Information, dass ein anderes Kaestchen ausgemalt werden muss. Wuerde man die weissen Kaestchen nicht markieren, dann wird das Raetsel 100mal schwerer.

Genauso ist bei schwierigen Sudokus das Wissen, dass an einer Stelle eine Ziffer NICHT hinkommen kann, eine entscheidende Information. Wen das nicht interessiert, der hat es halt schwerer, das Sudoku zu loesen.

Zur Fallunterscheidung stimme ich berni bei allem zu. Wann und wo man damit beginnt ist eine Gefuehlssache und macht sicherlich auch schnelle Wettbewerbsloeser aus. Eine kleine Anektote mag fuer Erheiterung und auch Verwunderung sorgen: Der Sudoku-Weltmeister Thomas Snyder schrieb in einem seiner Blogs, dass er zu Raten beginnt, wenn er eine Minute keine Zahl eintragen kann. Dazu moechte ich bemerken, dass das bedeutet, dass er so gut wie nie Fallunterscheidungen verwendet. :-)

Liebe Gruesse,
Stefan

[surbier]

Man muss sich wohl damit abfinden, dass man manchmal Probieren muss.
Schade aber ist halt so.

Ich meinte genau das Gegenteil.
Wenn du S nicht ohne Raten loesen kannst, koennte es daran liegen dass dein Repertoire an Tricks noch nicht ganz ausreicht. Schwierige Raetsel erforden nun mal anspruchsvolle Methoden. Die gibt es aber. Bevor ich nichts anderes kannte, musste ich frueher S oft mit Raten loesen. Fuendig wirst du z.B. bei sudopedia.

Bei Wettbewerben, ist die Situation anders. Dort ist fuer den Erfolg die Schnelligkeit wesentlich wichtiger ist als die logische Eleganz des Loesungswegs. Ich kann deshalb berni's Hinweis (siehe frueheren post in diesem thread) bestaetigen, dass man hier mit Raten schneller am Ziel ist als z.B. einen x-wing oder ein anderes kompliziertes Muster zu suchen. Wenn deine Frage so gemeint war: 'ab welchem Schwierigkeitsgrad' ist es zeitlich guenstiger zu Raten, habe ich fuer mich gefunden: 2er, 3er, Linien-Block Interaktion loese ich noch logisch. Wenn das nicht ausreicht, rate ich. Bei der kuerzlichen Quali der 4. SM war allerdings nur ein einziges klassiches Sudoku dabei, das den Schwierigkeitsgrad eines x-wings erreichte, d.h. bei dem diese Frage ueberhaupt relevant war.

surbier