Sudoku lösen durch Ausprobieren

Hallo Rätselfreunde,

einfache Sudoku löst man bekanntlich mit den Methoden Hidden Single und Naked Single.

Bei schweren Sudokus bleibt einen Ausprobieren und Korrigieren nicht erspart. Kennt jemand für diese Methode einen englischen Namen? Trial and Error Single vielleicht?

Dank und Gruß!
Franz

Hallo,

einfache Sudoku löst man bekanntlich mit den Methoden Hidden
Single
und Naked Single.

Bei schweren Sudokus bleibt einen Ausprobieren und Korrigieren
nicht erspart.

gar nicht wahr! :wink:
Nur bei den ganz very hards oder bei evils ist das vielleicht nötig.
Die normal-schweren lassen sich meistens(!) mit Logik allein lösen.

Kennt jemand für diese Methode einen englischen
Namen? Trial and Error Single vielleicht?

Ich nicht. :wink:
Bis vor ca. einem halben Jahr habe ich noch nichtmal gewußt, daß es für die Methoden irgendwelche Namen gibt, dabei versuche ich mich schon seit Jahren an Sudokus. :wink:

Ich finde es auch verkehrt (Achtung: das ist meine Meinung!), für einen verkehrten Ansatz nach einem Methoden-Namen zu suchen.

Das Ziel muß sein: Lösung durch Logik.

Wenn Du einen „Hänger“ hast, kannst Du gerne Deinen Zwischenstand als Bild hier hochladen und ich bin sicher, die Sudoku-Spezies helfen Dir, Deinen „Blick“ zu schärfen.

Von „wie schwer“ reden wir hier eigentlich?
Ich fand z.B. das aktuelle aus dem Zeitmagazin (Nr. 49/2013) ganz schön happig, dennoch hat es sich nur durch Logik lösen lassen.
http://sudoku.zeit.de

Gruß

Es ist alles eins
Hallo Franz

Was du mit Ausprobieren bezeichnest, ist auch nur Logik! Ab einem gewissen Grad von Komplexität musst du halt mehr Schritte vorausdenken, als du im Kopf speichern kannst. Letztendlich ist auch die einfachste Schlussfolgerung Trial and Error, mit dem einzigen Unterschied, dass du den kompletten Gedankengang sofort überblickst.

Von daher alles eine Frage der individuellen Speicherkapazität. Schachgrossmeister dürften auch mit den schwierigsten Sudokus wenig Probleme haben.

Namen von Methoden kenn ich genausowenig wie Gudrun. Ich mach’s einfach… :wink:

Liebe Grüsse
dodeka

Also ich nehme an was du mit „Ausprobieren“ meinst ist einfach die potentielle Zahl einzugrenzen.

Du weisst, dass in diesem Bereich entweder eine 2 eine 5 oder eine 8 stehen kann.
Selbiges im Nachbarfeld.
Also schreibst du mit Bleistift hinein und achtest darauf, was dies für einen Einfluss auf die anderen involvierten Felder hätte.

Ich selber würde es als Wahrscheinlichkeitsrechnung betrachten. Also Propability calculus.

Wenn du aber wirklich nur irgendetwas einträgst und schaust ob es stimmt, dann nennt sich das laut englischem Wikipedia Stochastische Suche oder Optimierungsmethode (stochastic search / optmization methods). Dies sind allerdings Methoden die ein Computer anwenden würde. Also zuerst alle Felder füllen. Schauen wieviele Fehler generiert werden. Die Zahlen wild umhertauschen und schauen ob es nun weniger Fehler gibt. Dies so lange bis Fehler = 0.

Hallo Gudrun

>>von wie schwer reden wir

Hallo,

>>von wie schwer reden wir5 in Spalte G /Zeile 1 eintragen.

Wenn die Hidden und Naked Singles abgearbeitet sind, überlasse
ich das Aufsuchen der paar „Radiergummizahlen“ aus
Zeitgründen schon mal www.sudoku-schule.de.
Das ist natürlich nicht die sportliche Art!

Das ist nicht nur unsportlich, das ist vermutlich sogar hinderlich, jemals weiter zu kommen.
Es sei denn, Du benutzt den Solver, um für Dich eine bessere Lösungs-Strategie zu entwickeln. Das kostet Zeit und Geduld, zahlt sich langfristig aber ganz sicher aus.

Wenn Du es schaffst, mir zu erklären, wie ich auf die 5 gekommen bin, brauchst Du keinen Solver mehr. :wink:
Dann brauchst Du einfach nur mehr Geduld und ein bißchen mehr Ehrgeiz. :wink:

Ich mach Sudokus nur online und in der ZEIT gibt’s außer dem wöchentlichen im Magazin täglich 3 neue (leicht, mittel, schwer) und ein Riesen-Archiv.
Ich hätte gar keine Lust, mir so ein Sudoku in einen Solver abzutippen.
Was ich nicht sofort bis zum Ende gelöst kriege, bleibt eben solange online, bis ich es raus habe (PC runterfahren geht dann nicht, aber Ruhestand funktioniert).

Für mich steht die Knobelei als solche im Vordergrund.
Der Weg ist das Ziel. :wink:

Gruß

.

Danke Gudrun, fürs Rätsel aus der ZEIT,

ich brauchte einige Zeit, aber es war ohne Raten mit reiner Logik lösbar. Wie du schon sagtest: Den Schwierigkeitsgrad bestimmte in diesem Rätsel die Verteilung der Anfangszahlen. Ich rätsle erst seit einem Jahr, fing an mit den Sudokus aus dem Heimatblatt SZ und aus handelsüblichen Heften.

Nach ein paar Wochen kam ich drauf: Da gibt es ja eine hilfreiche Regelmäßigkeit, die das Lösen erleichtert: Reine Logik aus der Disziplin Mengenlehre. Bis heute habe ich nichts darüber geschrieben gefunden, ich nenne sie 6-er Regel. Man zerlegt Blockreihen (senkrechte wie waagrechte) gedanklich in 6er-Gruppen, zusammengezählt macht das 54 Zerlegungsbilder. Der Vorteil: Auf der Suche nach Treffern hat man es nicht mehr mit 9 Zahlen, sondern nur mit 6 Zahlen zu tun. Ich habe eine Grafik dafür gezeichnet, aber einen Anhang gibt es hier ja nicht.

Die schlimmen „Radiergummizahlen“ aber ermittelt meine 6er-Regel nicht.

Gruß Franz

Hallo Dodeka,

manchmal sehe ich auf Videos den Profis beim Lösen zu, den Spezialisten also, die mit den grauslichsten Sudokus in 10 Minuten fertig sind und dafür Preise kassieren. Auch sie machen sich auf dem Tableau Notizen, vermutlich krixeln sie Bruchstücke einer Kandidatenliste aufs Papier, weil sie sich nicht alles merken können.

Mal extrem ausgedrückt: Wer beim Lösen eines Sudoku überhaupt ein Hilfsmittel braucht, ist ein …
Sag ich jetzt nicht, sonst schmeißt mich der Moderator aus dem Brett :smile:
Gruß Franz

Bilder hochladen

Ich habe eine
Grafik dafür gezeichnet, aber einen Anhang gibt es hier ja
nicht.

Dochdochdoch, das gibt es hier. Du konntest doch das Rätselbild auch sehen!

Hier klicken: http://www.pic-upload.de/, Bild auswählen und einen der erzeugten Links hier posten. Ich nehme meistens „Direktlink für Originalgröße“ —>zweiter von unten.

Soviel auf die Schnelle.

Gruß

Hallo,

Nach ein paar Wochen kam ich drauf: Da gibt es ja eine
hilfreiche Regelmäßigkeit, die das Lösen erleichtert: Reine
Logik aus der Disziplin Mengenlehre. Bis heute habe ich nichts
darüber geschrieben gefunden, ich nenne sie 6-er Regel. Man
zerlegt Blockreihen (senkrechte wie waagrechte) gedanklich in
6er-Gruppen, zusammengezählt macht das 54 Zerlegungsbilder.
Der Vorteil: Auf der Suche nach Treffern hat man es nicht mehr
mit 9 Zahlen, sondern nur mit 6 Zahlen zu tun. Ich habe eine
Grafik dafür gezeichnet, aber einen Anhang gibt es hier ja
nicht.

ich kann mir grad nicht recht vorstellen was Du meinst und daher auf Deine Grafik recht neugierig.
Wie man Bilder hier zeigen kann, habe ich Dir im Posting eins drunter beschrieben.

Die schlimmen „Radiergummizahlen“ aber ermittelt meine
6er-Regel nicht.

Ich schau mir das an und wir werden sehen. :wink:

Gruß

.

Hallo Gudrun,
jetzt probiere ich mal deine Methode zur Herstellung eines Links, wer weiß, was dabei rauskommt:
http://www.pic-upload.de/view-21522880/6er-Regel.jpg…

Drei Blöcke in Reihe nenne ich Blockreihe, davon gibt es 3 waagrechte und 3 senkrechte.
Jede Blockreihe lässt sich 9 Mal in jeweils zwei 6er-Zonen aufteilen (in meinem Bild rot und blau markiert), die exakt dieselben Zahlen beinhalten. Ich zeige 4 Beispiele, es gibt 6x9=54 davon. Rot kann also von Blau abschreiben und umgekehrt, wenn die Zahlen platzierbar sind. Anfangs ist die Ausbeute noch mager, aber je mehr Zahlen gefunden sind, umso nützlicher wird meine 6er-Regel.
Die Regel ist trivial, aufgeschrieben aber klingt sie kompliziert. Wenn das Auge erst mal die Zonenaufteilung wie selbstverständlich macht, dann hat man einen Nutzen davon. In Copyright-Fragen kannst dich an Franz aus dem schönen München wenden!
Viel Erfolg!

Backtracking
Das Wort, dass du suchst ist Backtracking.

Hallo GreenBeret,

kann man sagen, ein mit der Backtracking Methode erzielter Treffer ist ein „Backtracking Single“ in Anlehnung an Hidden Single?
www.sudoku-schule.de zum Beispiel sucht mit der Methode 1 bis X Zahlen, anschließend kann das Rätsel mit Hidden und Naked Single zu Ende gespielt werden.

Wenn ich die Beiträge in diesem Thread richtig verstanden habe, gibt es Methoden, mit denen man jedes Sudoku ohne Backtracking lösen kann??

Gruß Franz

Zur ersten Frage kann ich nichts sagen, ich hab keine Ahnung wie das im Sudoku heißt. I interessiere mich nicht für Sudokus im Speziellen. Aber als Informatiker interessieren mich generell Lösungen und Lösungsstrategien für solche Rätsel.

Zur zweiten Frage: Nein, es gibt definitiv Beispiele, die sich nicht ohne Backtracking lösen lassen. N mal N Sudoku wurde 2002 als NP-Vollständig bewiesen [1].
Man könnte es für „Normalos“ so übersetzen:

Sudoku gehört zu einer Klasse von Problemen, für die noch nicht bewiesen wurde, ob sie sich schnell (d.h., ohne „ausprobieren“) lösen lassen. Da aber schon seit Jahrzehnten nach solchen Lösungsstrategien gesucht wird, und keine Lösungen gefunden wurden, nimmt man an, dass keine schnellen Lösungsstrategien existieren.

Wenn man eine solche Strategie finden würde, wäre man berühmt und reich.

Für das 9x9-Sudoku ist es (für PCs) egal, ob es NP-Vollständig ist. Bei steigenden Problemgrößen (z.B. 100x100, 1000x1000 oder 10.000x10.000) kommt aber selbst der schnellste Computer irgendwann ins Schwitzen.

Alle leichten und normalen Sudokus sollten aber gänzlich ohne Backtracking schaffbar sein, soweit ich das beurteilen kann.

[1] http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#M…

Danke GreenBeret, für den Beitrag aus Sicht der Informatik!

>> Alle leichten und normalen Sudokus sollten aber gänzlich ohne Backtracking schaffbar sein.

Hallo,

jetzt probiere ich mal deine Methode zur Herstellung eines
Links, wer weiß, was dabei rauskommt:
http://www.pic-upload.de/view-21522880/6er-Regel.jpg…

hat doch prima geklappt.
Danke für die Grafiken, die mir nichts nutzen. Ich glaube, ich bin schon einen Schritt weiter, weil ich vielleicht schon etwas länger übe. :wink:

Drei Blöcke in Reihe nenne ich Blockreihe, davon gibt es 3
waagrechte und 3 senkrechte.

[…]

Wenn das Auge erst mal die Zonenaufteilung wie
selbstverständlich macht, dann hat man einen Nutzen davon.

Damit fange ich immer an, nenne es für mich „Dreierpäckchen“ auffüllen und meine Augen sehen sofort, ob und wo was geht.
Als nächstes schaue ich, ob in den kleinen Quadraten auf Anhieb was geht oder ob in den 4 Außenrändern schon Einträge möglich sind.
Und bei jeder gefundenen Zahl habe ich immer meine „Dreierpäckchen“ und die Außenränder im Blick.

Aus Spaß habe ich mal nach Lösungsstrategien gegoogelt und diese Seite
http://hodoku.sourceforge.net/de/tech_intro.php
entdeckt.
Du kannst ja mal schauen, ob es für Dich eine Hilfe sein könnte.

Hätte ich mich damit beschäftigen müssen, wäre mir wahrscheinlich schnell die Lust vergangen. Aber zum Glück gab es noch kein Internet, als ich meine Sudoku-Karriere gestartet habe.
Wie dodeka weiter oben schrieb: einfach machen.

Je mehr Sudokus man macht, desto mehr Übung kriegt man, desto mehr „sieht“ man.
Mein Tip dazu wäre: erstmal nur leichte zu spielen, diese aber flottweg, und wenn solch ein leichtes in ca. 5 Minuten gelöst ist, sich erst dann auf die nächste Schwierigkeitsstufe zu begeben.

Früher (vor 7 Jahren!) habe ich sie noch mithilfe von Excel gemacht. Wie das ging, kannst Du hier nachlesen:
http://www.wer-weiss-was.de/raetsel/sudoko-schwierig…
und auch sonst sind in diesem Thread interessante Beiträge und Links.

Weiterhin frohes Rätseln + Gruß

Hallo Gudrun

Mir geht es anscheinend wie dir: Eine Theorie des Sudokulösens ist so ziemlich das uninteressanteste, was ich mir vorstellen kann – und das, obwohl ich der Mathematik durchaus zugeneigt bin.

Übrigens mache ich seit einigen Monaten so gut wie keine Sudokus mehr, sondern praktisch nur noch „Str8ts“ – kennst du die? Nach einer kurzen Eingewöhnungsphase bin ich jetzt fast süchtig…

Guten Start in den Tag! :wink:
dodeka

Hallo dodeka,

Mir geht es anscheinend wie dir: Eine Theorie des Sudokulösens
ist so ziemlich das uninteressanteste, was ich mir vorstellen
kann – und das, obwohl ich der Mathematik durchaus zugeneigt
bin.

volle Zustimmung.
Allein schon die Feldbezeichnung mit r und c brächte mich völlig durcheinander.
20 Jahre Excel haben tiefe Spuren hinterlassen. :wink:

Übrigens mache ich seit einigen Monaten so gut wie keine
Sudokus mehr, sondern praktisch nur noch „Str8ts“ – kennst du
die? Nach einer kurzen Eingewöhnungsphase bin ich jetzt fast
süchtig…

Noch nie von gehört. Danke für den Hinweis. Ich schau es mir an.
Aber noch sind mir die normalen S. nicht langweilig geworden.

Guten Start in den Tag! :wink:

Danke, Dir ebenso, aber jetzt natürlich —> in die Nacht. :wink:

Gruß

Str8ts

Böse! Ich habe für sowas wirklich keine Zeit!

Hallo Gudrun,

was du Dreierpäckchen nennst, heißt bei mir Blockreihe. Um ganz sicher zu gehen, was wir meinen: Im angehängten Beispiel kann jeder auf Anhieb in der rechten senkrechten Bockreihe die dritte 7 setzen, genauso in der mittleren senkrechten Blockreihe die dritte 3.
In dieser ersten Runde sammelt man quasi Geschenke - einfacher geht’s nicht.

Mit meiner 6er-Regel kann ich ohne Grübeln in der unteren waagrechten Blockreihe die zweite 5 setzen. Je mehr Zahlen gefunden sind, umso effektiver ist die Regel.

Was Sudoku angeht, bin ich auf dem Niveau stehen geblieben, dass ich bei beliebigem Zeitaufwand alle Rätsel lösen kann, auch die aus der 17er Klasse. Es ist vielleicht nicht die eleganteste Art, aber mit den Methoden Hidden Single, Naked Single und Backtracking ist mir noch keine Lösung entgangen. Oder fällt dir ein Beispiel ein, bei dem die 3 Methoden nicht zur Lösung führen?

Gruß Franz

http://www.pic-upload.de/view-21602049/Leichtes-Sudo…