Entwickler-Ecke :: Thema anzeigen - Eine etwas andere SUDOKU-Lösung zum Nachvollziehen / Lernen

XUDO - So 21.12.08 17:46
Titel: Eine etwas andere SUDOKU-Lösung zum Nachvollziehen / Lernen

Sudoku-Lösung

Es gibt eine ganze Reihe von Lösungsprogrammen, die sogar im
gegenseitigen Wettbewerb angewendet werden, aber im Ablauf nicht
nachvolllziehbar sind, ich meine damit, daß der Lösungsweg unsichtbar ist.

Dieses arbeitet anders, und man kann vom ihm lernen.

Es arbeitet nicht wie manche Menschen mit Versuch und Irrtum, also Bleistift und Radiergummi, sondern streng logisch - es trägt eine Ziffer erst dann als Lösung ein, wenn keine andere möglich ist.
Die Vorbedingungen hierzu, also das Bereinigen des Spielfeldes / das Entfernen nicht möglicher Ziffern in einem Einzelfeld, führt es selbst durch.

Andererseit verweigert es die weitere Mitarbeit dann, wenn es logisch nicht weitergeht - es gibt Sudokus, die sich **logisch** nicht zu Ende lösen lassen.

Man kann die Lösungsschritte einzeln verfolgen.
Im Grunde arbeitet es (nahezu) so, wie ich selber Sudokus löse - daher die hohe Versionsnummer, denn bis alle Bio-Überlegungen bei vollem Blick auf das Spielfeld auf Maschinen-Verfahren umgesetzt waren, hat es doch ein wenig gedauert: Fand ich eine logische Lösung und das Programm nicht, so hatte ich ihm noch nicht alles beigebracht - heute ist es manchmal besser als ich und hat eine logische Weiterführung, wenn ich selbst nicht weiterkomme.

Ein Mensch überblickt ein 3x3-Quadrat und dessen Nachbarn, eine Maschine / ein Programm braucht hierzu eine ganze Menge exakt definierter Schritte - übersieht dabei aber absolut nichts - falls richtig und umfassend erstellt.

Möglicherweise führt das schrittweise Verfolgen der Lösungswege dieses
Programmes die/den eine/n oder andere/n zu neuen Lösungswegen.

Es würde mich interessieren, ob noch Fehler oder Lücken vorhanden sind, denn ich selbst bin auch keine Maschine...
Da das Programm eine Aufgabe / einen Feldinhalt speichern kann, wäre eine interessante Ausgabe auch übermittelbar. (Inhalt.dat)

XUDO

XUDO - Mi 24.12.08 14:25
Titel: Zusatz zum Sudoku

Vier SUDOKU-Beispiele bzw vier INHALT.[DAT]:

Nummer 1 ist nur lösbar wenn links oben in der Ecke eine 8 eingetragen
wird; bei Nummer 2 fehlt ganz rechts oben eine 9 und Nummer 3 benötigt im zentralen Mittelfeld eine 2, also Beispiele für logisch nicht lösbare ... nur per Try and Error.
Das jeweils zu verwendende muß natürlich in INHALT.DAT umbenannt werden und sollte im gleichen Verzeichnis wie die EXE stehen.

XUDO

PS: Da "vier" nicht geht, also nur drei.

Yogu - Mi 24.12.08 16:29

Das gibt es doch nicht! Vor einer etwas längeren Zeit hatte ich genau die selbe Idee, ein Sudoku zu lösen. Mein Programm scheiterte aber leider schon an der GUI :(

Ich habe auch versucht, die Strategie auf dem Papier durchzuführen, aber irgendwann wurde das mir zu blöd. Ich blieb aber bei der Ansicht, dass so jedes beliebige Sudoku zu lösen ist.

Leider habe ich gerade überhaupt keine Zeit, mir dein Programm anzuschauen. Aber ich werde es sicherlich nachholen.

Grüße,
Yogu

XUDO - Do 25.12.08 14:03

Yogu hat folgendes geschrieben :

... dass so jedes beliebige Sudoku zu lösen ist....

Ist es aber nicht, Yogu, daher die Beispiele.
Das Programm löst Schritt für Schritt logisch, nicht mit Bleistift und Radiergummi wie mancher ratende Mensch; ebenso mache ich es auch, und daher stoße ich manchmal auf nicht lösbare.
Das bedeutet, daß die Aufgabe entweder nicht eindeutig ist oder zu wenig vorgegebene Ziffern enthält, die man nur mit Raten und ggf. streichen finden oder auch nicht kann.

XUDO

Yogu - Do 25.12.08 14:52

XUDO hat folgendes geschrieben :

Yogu hat folgendes geschrieben :

... dass so jedes beliebige Sudoku zu lösen ist....

Ist es aber nicht, Yogu, daher die Beispiele.

Oh, gibt es doch "unlösbare"?

XUDO hat folgendes geschrieben :

Das Programm löst Schritt für Schritt logisch, nicht mit Bleistift und Radiergummi wie mancher ratende Mensch

Genauso habe ich das ja auch probiert. Ich habe mich dumm gestellt, und "Roboter gespielt". :)

XUDO hat folgendes geschrieben :

Ebenso mache ich es auch, und daher stoße ich manchmal auf nicht lösbare.
Das bedeutet, daß die Aufgabe entweder nicht eindeutig ist oder zu wenig vorgegebene Ziffern enthält, die man nur mit Raten und ggf. streichen finden oder auch nicht kann.

Das ist dann aber kein richtiges Sudoku, wenn es nicht eindeutig ist.

Wie dem auch sei, ich mag Sudokus :D

Hidden - Fr 26.12.08 16:32

Hi :D

Ein Sudoku ist ein mathematisches Gebilde. Ich würde zwei alternative Lösungen, also eine Lösungsmenge auch als Lösung bezeichnen ;)

Gerade, dass es z.B. nur 2 oder gleich 500 Löungen gibt, sollte imho dann das Ergebnis einer Analyse sein.

Die meißten "unlösbaren" lassen sich aber doch logisch eindeutig lösen, nämlich durch ausprobieren. Was du meinst ist eventuell, dass man mit Axiomen nichtmehr weiterkommt. Hier setzt dann Bruteforce ein.

mfG,

jaenicke - Fr 26.12.08 17:15

Hidden hat folgendes geschrieben :

Die meißten "unlösbaren" lassen sich aber doch logisch eindeutig lösen, nämlich durch ausprobieren. Was du meinst ist eventuell, dass man mit Axiomen nichtmehr weiterkommt. Hier setzt dann Bruteforce ein.

Richtig, das habe ich auch getestet bei meinem Programm, indem ich einfach mal nicht bei einer Lösung angehalten habe. Das hat dann zwar sehr lange gedauert, aber letztlich wurde dann normalerweise keine weitere Lösung gefunden. Genau das macht ja eben ein (echtes) Sudoku aus.

Jedenfalls sind in manchen Zeitschriften ja Sudokus verschiedener Schwierigkeitsstufe drin. Die einfachen lassen sich rein logisch lösen, die schwereren nicht. Trotzdem sind die aber i.d.R. eindeutig lösbar.

XUDO - Sa 27.12.08 10:25

[quote="

jaenicke"(540848)]

Hidden hat folgendes geschrieben :

Jedenfalls sind in manchen Zeitschriften ja Sudokus verschiedener Schwierigkeitsstufe drin. Die einfachen lassen sich rein logisch lösen, die schwereren nicht. Trotzdem sind die aber i.d.R. eindeutig lösbar.

Hallo jaenicke,
ein solches würde mich sehr interessieren.
Vielleicht stellt du einmal die INHALT.DAT davon hier hinein.
Machbar ist das mit meinem Programm nach der Eingabe der Ziffern und Speichern; Umfang ist lediglich 1 KB.
XUDO

PS: Hier kommt eines von heute, 27.12. aus dem Schleswig-Holsteinischen Zeitungsverlag, Wochenendbeilage, angeblich sehr schwer.
Es ist logisch ohne Raten und Radieren zu lösen, das Programm schafft es
ebenfalls und es ist eindeutig.
Da die Endung DAT hier verboten ist, mußte ich in TXT umbenennen.

XUDO - Sa 27.12.08 10:32

Hidden hat folgendes geschrieben :

Hallo Hidden,
ein Soduko mit zwei oder mehr Lösungen? Das möchte ich sehen!
Natürlich nicht ein fast leeres Feld mit einer einzigen Ziffer - das ist keine sinnvolle Lösungs- sondern dann eine Konstruktions-Aufgabe, eine angefangene und nicht beendet Neuerstellung.
Wenn es mehrere Lösungen gibt, handelt es sich um eine nicht zu Ende geführte Erstellung aber nicht um eine Lösungsaufgabe.
XUDO

Hidden - Sa 27.12.08 12:12

XUDO hat folgendes geschrieben :

Wenn es mehrere Lösungen gibt, handelt es sich um eine nicht zu Ende geführte Erstellung, aber nicht um eine Lösungsaufgabe.

Das ist eine Definition :zwinker:

Aber gut, wenn du es so ausdrücken willst :) Beim Erstellen eines Sudokus(wenn man es denn mal nicht rückwärts macht) interessiert aber schon, wie viele Sudokus daraus noch gemacht werden können.

mfG,

XUDO - Sa 27.12.08 15:11

Hidden hat folgendes geschrieben :

XUDO hat folgendes geschrieben :

Wenn es mehrere Lösungen gibt, handelt es sich um eine nicht zu Ende geführte Erstellung, aber nicht um eine Lösungsaufgabe.

Hallo Hidden,
dann hole dir bitte einmal die drei Beispiele (INHALT-1 bis -3) aus meinem Beitrag vom 24.12. oben.
Alle drei sind logisch nicht lösbar, weil man ohne Radiergummi nicht weiterkommt - auch das Programm nicht.
Erst wenn man jeweils eine (per Radiergummi gefundene Ziffer) ergänzt, werden es lösbare Aufgaben.
Es sind also unfertige Aufgabenstellungen, oder andersrum, es ist jeweils eine Ziffer zu viel aus einem vollständigen korrekten Raster gelöscht.
Das verstehe ich dann unter logisch nicht lösbar - für Leute, die gerne raten und radieren mag es ja trotzdem reizvoll sein.
Gruß XUDO

PS: Die jeweils anzuwendende/zu ladende Aufgabe muß natürlich in INHALT.DAT umbenannt werden, sonst kann sie das Programm nicht lesen.

Hidden - Sa 27.12.08 16:47

Hidden hat folgendes geschrieben :

Was du meinst ist eventuell, dass man mit Axiomen nichtmehr weiterkommt. Hier setzt dann Bruteforce ein.

XUDO hat folgendes geschrieben :

Alle drei sind logisch nicht lösbar, weil man ohne Radiergummi nicht weiterkommt - auch das Programm nicht. [..]
Das verstehe ich dann unter logisch nicht lösbar - für Leute, die gerne raten und radieren mag es ja trotzdem reizvoll sein.

Ich sehe wir versteh'n uns :D

Im Prinzip meinen wir beide das Gleiche; reiben tun wir uns nur an eindeutig lösbar :beer: .

jaenicke - Sa 27.12.08 17:46

Es geht ja nicht nur um die Anzahl sondern auch darum welche Zahlen man z.B. wegnimmt um ein Sudoku schwerer zu machen.

Genau das ist das Problem, das ich beim Generieren von Sudokus hatte, und für das ich auch keine gute Lösung gefunden habe. Bei den von meinem Programm generierten schweren Sudokus kann ich nicht dafür garantieren, dass es nur eine Lösung gibt. Diese sind allerdings mit einfacher Logik teilweise nicht zu lösen.

Jedenfalls habe ich versucht mathematisch an das Generieren heranzugehen, aber die Lösungen waren alle nicht so wie ich sie mir vorgestellt hätte. :nixweiss:

XUDO - So 28.12.08 10:36

[quote="

Hidden"(540965)]

Hidden hat folgendes geschrieben :

Im Prinzip meinen wir beide das Gleiche; reiben tun wir uns nur an eindeutig lösbar :beer: .

Hallo Hidden,
so ist es; das Wikipedia-Sudoku von Thorsten83 ist hierbei ein gutes Beispiel: Nur 17 Ziffern vorgegeben erweckt den Eindruck, es könnte mehrdeutig sein, also keine eindeutige Lösung haben.
Geht man numerisch aufsteigend bei der Suche vor, so ergeben sich die Einsen in J5,, G9, A7, A3, F4 und E2 zwingend logisch eindeutig.
(Spalten A bis J ohne I, Zeilen 1 bis 9.)
Weiter durch die Ziffern nach oben ist dann erst die 5 in F7 eindeutig.
Alle weiteren ergeben sich dann nach und nach und führen zu einer logischen eindeutigen Lösung - es gibt keine andere; wird eine nicht eindeutige Ziffer falsch eingetragen, führt das ins Chaos.
XUDO

Thorsten83 - So 28.12.08 12:56

jaenicke hat folgendes geschrieben :

Unter anderem Permutationen, und noch einiges andere. Ich habe einiges ausprobiert.

Und die Dinger waren entweder zu leicht oder zu schwer?

wikipedia hat folgendes geschrieben:

Alle lösbaren n-feldrigen Sudokus mit mehr als n - 4 vorbelegten Feldern (z. B. 81 - 4 = 77 Felder bei der Standardvariante) sind eindeutig lösbar. Es lassen sich Sudokus konstruieren, bei denen anfänglich n - 4 Felder vorbelegt sind, die aber trotzdem nicht eindeutig lösbar sind. Wenn nämlich vier freie Felder ein Rechteck bilden, so dass jeweils zwei Ecken in zwei verschiedenen Blöcken liegen und in beide Blöcke etwa die Zahlen 1 und 2 oder ein beliebiges anderes Zahlenpaar eingetragen werden kann, gibt es zwei Möglichkeiten, diese Zahlen einzutragen, da beide Zahlen vertauscht werden können.

XUDO - So 28.12.08 13:19

Thorsten83 hat folgendes geschrieben :

Hey,
ich habe mich vor längerer Zeit auch mal an solch eine Lösungsstrategie gesetzt, auch mit dem Ergebnis, dass schwere Sudokus damit nicht lösbar waren...Z.B. das hier: http://de.wikipedia.org/w/index.php?title=Datei:MinimalSudoku.jpg&filetimestamp=20070318111345

Hallo Thorsten83,
Die ersten Lösungsschritte (alle 1 + eine 5) stehen bereits in meinem Beitrag; weiter geht es mit 8 in A8, 8 in F6, 8 in H4, 8 in J7, 9 in F8, 9 in H5, 9 in J9, 9 in C7 und dann je nach Geschmack 5 in H9 oder 6 in C8 und 4 in C9, oder auch erst 7 in E7; warum da die 7?
Weil E8 und E9 durch 2 und 3 belegt sind, auch wenn sie dort noch nicht
stehen, bzw nur klein in den Ecken als Vormerkung von zwei(!) möglichen Positonen.
Trägt man nun ebenso die 7 und die 2 als Vormerkung in Minischrift in die Ecken von A9 und B9 ein, kann man sofort 2 in E8 und 3 in E9 eintragen. Und weiter schaffst Du es bestimmt selbst.
Jedenfalls ist das Ding nicht nur mit meinem Programm sondern auch per Hand lösbar.
XUDO

Thorsten83 - So 28.12.08 14:15

Hey,

hab mir jetzt nicht en detail angeguckt was dein Programm macht, aber die prinzipielle Vorgehensweise ist mir schon klar...

Das alte Programm, das schwerere Sudokus nicht lösen konnte hab ich halt vor Jahren geschrieben, damals wusste ich gerade mal was eine Schleife ist und hab wohl schlicht und ergreifend nicht genügend Techniken implementiert...
Werd mal suchen ob ich den Mist noch irgendwo finde :)

XUDO - So 28.12.08 14:20

jaenicke hat folgendes geschrieben :

Hallo jaenicke,
vielleicht gefällt dir das beiliegende Programm.
Ist lediglich eine EXE aber wegen 50% Ersparnis gezippt.
Es erstellt Aufgaben, die alle lösbar sind.
XUDO

jaenicke - So 28.12.08 14:41

Bei mir bleiben maximal 27 Zahlen stehen (einfachste Schwierigkeitsstufe). :D
Da funktioniert das Generieren fast sofort. Du kannst es dir ja anschauen:
http://www.delphi-forum.de/viewtopic.php?p=291436
Wie bei allen meinen kostenlosen Programmen natürlich mit Quelltext. ;-)

Leider ist die Vorgehensweise zufallsbasiert, da ich leider wie gesagt mathematisch nicht zum Ziel gekommen bin. :(
Ach ja: bei dieser alten Version enthält der Löser nur einfachste Logiken.

XUDO - So 28.12.08 19:19

jaenicke hat folgendes geschrieben :

Ach ja: bei dieser alten Version enthält der Löser nur einfachste Logiken.

Hallo jaenicke,
das kann man an Deinem Beispiel 2 gut sehen, das nur über die Iteration lösbar ist; die Aufgabe ist allerdings "von Hand" und auch mit meinem Programm eindeutig und mit Deiner Lösung übereinstimmend zu erreichen -
ist also eindeutig.
Und zu meinem Beispiel 2 mit der ergänzten 9:
Sie kommt per Iteration korrekt heraus, wie die beiliegende JPG zeigt.
Gefällt mir aber sehr, Dein Programm, wenn es auch noch ein wenig intelligenter werden könnt.
Ich bin einen anderen Weg gegangen, habe dem Programm nach und nach(!) beigebracht, wie ich systematisch vorgehe - heute frage ich es manchmal um Rat per schrittweiser Lösung, wenn ich nicht weiterkomme ;-)
Gruß Xudo.

XUDO - Mo 29.12.08 10:41

Thorsten83 hat folgendes geschrieben :

Was halt noch fehlt ist ein Lösen in 2 Stufen: Erst ein intelligenter Ansatz, und wenn dieser nicht zum Ziel führt ein Umschalten auf einen "schlauen" Backtrackingalgorithmus, der die bisherigen Erkenntnisse weiterverwendet.

Hallo Thorsten83,

Genau das macht ja das Programm von jaenicke.
Obwohl ich zu diesem Lösungsschritt 2 eine andere Auffassung habe:
Die Iterations-Arbeit, die das Programm dabei verrichtet, ist Konstruktion.
Es probiert, wie aus einigen vorgegebenen Ziffern ein vollständiges
Sudoku erstellt werden kann und geht dabei sämtliche (un)möglichen Kombinationen durch.
Ein Lösungsprogramm dagegen sollte ähnlich wie ein Mensch lediglich logisch vorgehen - wenn beide dann nicht zum Ergebnis kommen, ist das kein gutes Sudoku, weil mit logischem Denken nicht lösbar; vorausgesetzt natürlich, daß das Programm umfassend "denkt", weil der Mensch bei der Erstellung umfassend gedacht hat.

Darin liegt doch der Reiz der Lösungsprogrammerstellung:
Der blinde Geschwindigkeitsvorteil des Computers in Verbindung mit einem
sämtliche Möglichkeiten durchprobierende Eintragungen als ein Verfahren zur Lösung ist unfair - als Erstellungsverfahren aber völlig korrekt.
Was selbstverständlich nicht bedeutet, daß jaenicke unfair ist, und
außerdem ist das meine persönliche Ansicht zum Lösungsverfahren.
XUDO

XUDO - Mo 29.12.08 13:18

jaenicke hat folgendes geschrieben :

Aber ich habe in dem alten von mir vorgestellten Programm noch keine besonderen Tricks zum Lösen verwendet.

Hallo Jaenicke,
Was ist der (Trick?-)Unterschied zwischen Label.top und Label.explicittop?
Da besteht jeweils eine Differenz von 3 Pixeln, aber ... alles weitere auf dem beiliegenden Screenshot.
Gruß vom "bahnhofverstehenden" Xudo

PS: Falls das eine umfangreiche Diskussion wird, müssen wir vielleicht mit dem Thema "umziehen".

XUDO - Mo 29.12.08 13:28

jaenicke hat folgendes geschrieben :

Das kannst du einfach ignorieren, das gab es in älteren Versionen nicht, aber es sollte normal alles funktionieren, wenn durch ignorieren diese Werte gelöscht werden.

Bist du aber schnell.
Ich habs auch ignoriert und alles klappt.
Aber das erklärt nicht, was die drei Pixel Differenz bedeuten bzw was der Sinn des expliziten Top ist.
Gruß XUDO
PS: Eine Vermutung:
Zwischen älteren und neueren Win-Versionen gibt es einen bei manchen Programmen störenden Unterschied: Der Kopfbalken ist ab XP oder schon früher einige Pixel breiter, was manchmal zu seltsamer Optik führt.
Nimmt sich das eine neuere Delphi-Version damit "zur Brust"?

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!