Sudoku Löser

[simonko]

Hier ein einfacher Sudoku Löser in C gschrieben. Er liest die Werte aus einer txt datei ein und gibt sie in einer anderen aus. Ich hab andere Lösungen hier gesehen, und hab mich aufgeregt, dass die
objektorientierung alles so kompliziert macht.

MFG

[omata]

Hallo Hagen,

das ist schon klar. Das ist ja gerade der Witz. Es gibt keine Lösung.
Die Frage ist wie lange brauchst das Lösungsprogramm, um das herauszufinden.

MfG
Thorsten

[negaH]

Schon beim Eintippen der Zahlen in meinen Sodoku Solver hat dieser erkannt das es nicht gehen kann. Dh. mein Solver überprüft schon beim Laden des Games das es nicht gehen kann. Er macht dies einfach per logischer Analyse der Abhängigkeiten. Übrigens kannst du die Sourcen meines Solvers hier in der DP finden.

http://www.delphipraxis.net/internal...oduko&start=26

Gruß Hagen

[omata]

Ja stimmt, habe mir mein Beispiel nochmal angesehen. Da sieht man schon gleich das es nicht gehen kann.
Folgende Variante ist da besser...

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 1 | 0 | 0 | 2 | 0 | 0 | 3 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 3 | 4 | 2 | 0 | 0 | 0
0 | 4 | 0 | 5 | 0 | 1 | 0 | 6 | 0
0 | 0 | 0 | 9 | 6 | 7 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 7 | 0 | 0 | 8 | 0 | 0 | 9 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

Dein Programm ist super. Dort wird leider diese Problematik gar nicht zugelassen. Das heisst man kein deinem Programm gar kein ungültiges Sudoku unterjubeln. Das ist ja ok. Ist allerdings nicht das was ich meinte. Aber ist natürlich auch eine Lösung.

MfG
Thorsten

[negaH]

Hi Thorsten,

naja das Ziel im Sodoku ist es ja nur durch reine logische Überlegung das Game zu lösen. Dh. die Trial&Error Methode und das Backtracking sind unter Sodoku-Solvern verpönt. Auch Rätsel die mehrere Lösungen haben sind verpönt. Und da ist mein Solver noch nichtmal ein besonders guter (ok besser als viele andere die nur Trial&Error benutzen). Es gibt im WEB Solver die jede bekannte logische Taktik anwenden, was meiner definitiv nicht kann.
Wichtig ist eben nur das schon die logischen Regeln was geht und was nicht gehen kann in der Gameengine integriert sind, eben wie in meinem Solver.

Davon mal abgesehen: warum soll ein Sodoku Solver überhaupt versuchen ein per Definition unlogisches Rätsel lösen zu wollen ?

Gruß Hagen

[omata]

Hallo Hagen,

ja natürlich. So sehe ich das ja auch.
Nur hier werden immer wieder solche Solver veröffentlicht (was ich als gute Übung sehe) und ich bin bei meinem eigenen eben genau auf das Problem der ungültigen Sudokus gestoßen. Und da war einfach nur die Frage wie löst man das. Wenn man nämlich so einen einfachen Solver hat, dann kann man den nach einem Tag abbrechen und man hat immer noch keine Lösung. Ok es gibt auch keine - und da war ja setzt nun genau meine eigentlich Frage. Kann man das schneller herrausfinden als da Tage rumzuprobieren. Wenn man das so wie in deinem Programm gar nicht erst zulässt, ist das ja auch eine super Lösung.
Meine Intention war ja nur mal darauf aufmerksam zu machen, was passiert bei einem ungültigen Sudoku?

Weiter war nichts.

Zu deinem Edit...
Warum soll man ungültige Sudokus lösen? Na ganz einfach, wenn ich mich z.B. bei diesem Solver in der Input.txt Datei vertippe, versucht der Solver da eine Woche etwas zulösen. Nur um dann irgendwann mal festzustellen, das es keine Lösung gibt. Das wäre doch schöner wenn man das schneller wüste. Ausserdem, wenn ich das nicht so löse wie du, also eine ungültige Situation erst gar nicht zulasse ist ja alles ok, aber so wie bei dem hier vorgestellen Solver gibt es keine solche Kontrolle. Also was passiert im worst case?

Zitat von negaH:

Davon mal abgesehen: warum soll ein Sodoku Solver überhaupt versuchen ein per Definition unlogisches Rätsel lösen zu wollen?

Weil er (das Programm) es nicht weiss?!

Ich weiss das sind nur theoretische Fragen. Aber warum kann ich sie nicht stellen? Ist doch nur eine Frage.

Grüsse
Thorsten

[negaH]

Hi Thorsten,

Zitat:

Ich weiss das sind nur theoretische Fragen. Aber warum kann ich sie nicht stellen? Ist doch nur eine Frage.

das ist ja auch gut und richtig so. Es ist also wichtig das die Engine des Solvers bei jedem Zug ausrechnet welche verbleibenden Zahlenkombinationen in jeder noch offenen Zelle übrig bleiben. Wenn du das programmierst und dann in einer BELIEBIGEN Reihenfolge die Vorgabezahlen einzeln nacheinander in das Game einfügst, wird durch diese Übrprüfung autom. jedes ungültige Game erkannt. Die gleiche Funktionalität benötigst du dann sowieso in der Solve Funktion.

Gruß Hagen

[jmit]

Zitat von 3_of_8:

So wie ich den Code interpretiere, löst er nur eindeutige Sudokus. Wenn es mehrere Lösungen gibt, wird der nicht funktionieren, oder?

Ich habe bisher immer gedacht, dass bei Sodoku immer nur eindeutige Lösungen gibt.

Gruß Jörg

[Gravitar]

Zitat von omata:

Hallo Hagen,

das ist schon klar. Das ist ja gerade der Witz. Es gibt keine Lösung.
Die Frage ist wie lange brauchst das Lösungsprogramm, um das herauszufinden.

MfG
Thorsten

Hi,

mein Programm benötigt 0 Millisec.

Gruß, Andreas