Sudoku, Zeitproblem oder logischer Fehler?

Du irrst dich. Ich denke nur inzwischen das es keinen Sinn hat da du schon alles weißt.

Da ich mich mit meinem Programm und dem Code ausgiebig beschäftigt habe, weis ich naütrlich auch einiges darüber.

Meine Ursprüngliche Anfrage galt deshalb auch nur nach dem Finden einer möglich vorhanden Endlos-Schleife.

Und warum du deinen Affenspruch gebracht hast, wenn ich ein Programm anpreise welches vom Prinzip nunmal auf Zufallswerten basiert, ist mir auch schleierhaft, aber du willst ja nur helfen ...
 
Um mal von der Polemik zur Sachlichkeit zurückzukehren:
Dragonate hat insofern recht, dass er tatsächlich sicherstellt, dass in jedem 3*3-Block wirklich nur die Zahlen von 1-9 vorkommen; in dem Punkt war ich tatsächlich im Irrtum. Dass seine Methode trotzdem extrem ineffizient ist, ist eine Tatsache.
Sudokus mit 18 vorgegebenen Zahlen sind eindeutig lösbar; das wären durchschnittlich 2 Zahlen pro Block. Gehen wir einmal von einem Sudoku mit 4 vorgegebenen Zahlen pro Block aus, was schon als ziemlich einfaches Sudoku einzustufen ist. Die Anzahl der Möglichkeiten, jeweils in einem Block die übrigen 5 Zahlen zu platzieren, ist 5! = 120. Die Anzahl der Möglichkeiten für 9 Blöcke sind dann
5!^9 = 120^9, also ca. 5*(10^18).
Und davon ist nur eine richtig.
Und viele davon werden mehrfach getestet.
Zufallsbasierte Lösungsverfahren werden in der Informatik tatsächlich angewandt; meistens wird dabei eine zufällige Startverteilung ausgewürfelt und dann versucht, durch Umgruppieren eine gültige Lösung zu finden. Wenn nach einer festgelegten Anzahl von Umgruppierungen keine Lösung gefunden wurde, wird eine neue Startverteilung ausgewürfelt. Wenn das Spielfeld groß genug ist, wird dadurch schneller eine Lösung gefunden als durch Backtracking. Bekanntestes Beispiel hierfür ist das N-Damen-Problem. Für ein Spielfeld mit 18*18 Feldern ist ein solcher intelligent implementierter Algorithmus tatsächlich schneller.
Für das Standard-Sudoku ist es allerdings schwierig bis unmöglich, gute Kriterien für die Umgruppierung zu finden, so dass ein Backtracking im allgemeinen die einzig effiziente Methode ist, eine Lösung zu finden.
Die derzeit effizienteste Methode, ein Backtracking zu implementieren, ist der Algorithmus X, auch 'Dancing Links' oder kurz DLX genannt, der von Donald Knuth entwickelt wurde. Genaueres dazu findest du z.B. über die Sudopedia.
 
Danke das du wieder das Niveau herbeigerufen hast, ich bin selber auch zu sehr ausgeschweift....

Und du triffst es auch genau auf den Punkt, wiegessagt das mit den Zahlen ist sichergestellt, sollte vor allem auch deep_throat das die ganze Zeit mit meinen "schlechten Zufallszahlen" gemeint haben, ist denke ich meine Aufregung und Kritik berechtigt, meinte er etwas anderes, wiegesagt, dann habe ich das nicht rauslesen könen.

Zufallsbasierte Lösungsverfahren werden in der Informatik tatsächlich angewandt; meistens wird dabei eine zufällige Startverteilung ausgewürfelt und dann versucht, durch Umgruppieren eine gültige Lösung zu finden. Wenn nach einer festgelegten Anzahl von Umgruppierungen keine Lösung gefunden wurde, wird eine neue Startverteilung ausgewürfelt.

Und genau das hatte ich vor, würde mein nächster Schritt sein. Dem ist nichts mehr hinzuzufügen, genauso wollte ich Backtracking mit Zufallswerten kombinieren.

Wie du aber schon sagst, es wird nicht einfach sein und ich hänge nachwievor an meinem Ursprünglichem Problem, woran ich aber weiterhin arbeiten werde.

Danke.
 
Gern geschehen.
Ich lege dir aber wirklich ans Herz, die Lösungsmethoden in der Sudopedia zu studieren. Schau dir auch mal den Sudoku Explainer an; das ist ein Programm, das nicht nur Sudokus erstellen und (auch schrittweise!) lösen kann, sondern auch genau erklärt, mit Hilfe welcher Methode die nächste Zahl ermittelt werden kann. Solltes du weitere Fragen zu DLX oder Backtracking haben, kannst du sie gerne hier veröffentlichen. Ich rate dir jedoch ab, weiterhin zufallsbasiert zu arbeiten, auch wenn du vorhast, Umgruppierungen einzubauen; die Chancen sind einfach zu schlecht.
 
Mir war natürlich auch klar das es schon Lösungen dafür gibt, und natürlich solche vom professionellen Charakter.

Ich wollte nur gerne eine eigene Lösung erarbeiten, ist einem ja dann mehr Wert wenn mans geschaft hat ^^

Sobald ich meine Lösung zum laufen gebracht habe, diese dann noch selber mit leichten back-tracking-Ansätzen hoffentlich effizient ergänzen kann, werde ich mich dann auch belesen : >
 
Zurück