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

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.

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

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

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

Hmm... ich wusste gar nicht, dass es da noch andere Verfahren gibt? Also ich löse Sudokus eigentlich immer so. Und ich bin zu folgender Erkenntnis gekommen: Die wenigsten Sudokus lassen sich so lösen. Meistens nichtmal die Mittelschweren.

Hallo Jakob,

dann teste doch einmal das Programm an den nicht lösbaren Mittelschweren.

XUDO

Hi

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,

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.

[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.

Hidden hat folgendes geschrieben :

Hi 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. mfG,

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

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

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,

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. Das ist eine Definition 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,

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.

Bei deinem zweiten Beispiel findet mein Programm anscheinend eine eindeutige Lösung. Ob sie wirklich eindeutig ist, muss ich noch überprüfen, aber es sieht so aus.

Benutzt du auch schwierigere logische Verfahren wie die globale Paarsuche?

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

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

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: de.wikipedia.org/w/i...stamp=20070318111345

Dieses kann mein Programm rein logisch sofort lösen.

Hab ich auch gerade gesehen
Hatte das nur genommen weil so wenige Zahlen vorgegeben sind...

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.

@Jaenicke: Was verstehst du unter mathematisch?