Wie würdet ihr ein Sudoku schreiben/lösen?

Hab ich mir auch schon öfters überlegt, da mich auch schon seit einiger Zeit die Sudoku-Sucht gepackt hat.

Ich würd einen Lösungsalgorithmus schreiben, der Zahlen schrittweise per Ausschlussverfahren ermittelt, dh man schreibt quasi für jedes Feld der Matrix eine Liste, welche Zahlen für dieses Feld in Frage kommen. Irgendwo kann nur eine vorkommen, die kann man einsetzen, das Ganze in einer Schleife so lange, bis es ausgefüllt ist. (Bzw eigentlich keine Schleife, nach Einsetzen einer Zahl reichts ja eigentlich, alle Listen zu ändern, die in demselben 9erblock, derselben Zeile oder Spalte sind.)

Zur Erstellung könnte man dann einfach random Zahlen auf Random Felder vergeben, auch hier wieder mit Zwischenspeicherung der möglichen Zahlen. Je nachdem wie schwer es sein soll lässt man den Algorithmus früher oder später abbrechen, wichtig ist nur, dass man obiges Lösungsscript vorher nochmal drüber laufen lässt, um zu sehen, ob es auch wirklich lösbar ist (d.h. es nur eine Lösung gibt).

lG,
Murmel

ein twoday.tuwien blogger, Roland Lezuo, hat mal einen in python geschrieben:

http://twoday.tuwien.ac.at/alias/stories/8519/

getested hab ich ihn aber nie.

Zitat von Murmel

Zur Erstellung könnte man dann einfach random Zahlen auf Random Felder vergeben, auch hier wieder mit Zwischenspeicherung der möglichen Zahlen.

Oder umgekehrt, zuerst ein vollständiges Sudoku erstellen, und dann erst zufällig Zahlen löschen, solange es noch eindeutig lösbar ist...

Was ich mich eher frage: Sind nicht alle gültigen Sudokus bis auf Umbenennung und Vertauschung von Spalten/Zeilen dieselben?
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3
9 1 2 3 4 5 6 7 8
6 7 8 9 1 2 3 4 5
3 4 5 6 7 8 9 1 2
8 9 1 2 3 4 5 6 7
5 6 7 8 9 1 2 3 4
2 3 4 5 6 7 8 9 1
Würde das Erstellen vereinfachen: ein gültiges Sudoku hernehmen, ein bisschen durcheinanderschütteln und fertig...

Vielleicht ganz interessant:

Mathematics of Sudoku

Ich hab vor kurzem ein Sudoku-Lösgerät in Java geschrieben, dass mittels begrenzter Enumeration funktioniert - War total simpel, hat interessanterweise jedes Sudoku in Nullzeit gelöst. Mir ist nur leider kurz danach die Festplatte ein- und das Programm somit in den Orkus gegangen. Wenns dich interessiert, kann ich den Algorithmus aber gern nochmal rekonstruieren.

für die äpfel unter uns: http://www.apple.com/downloads/dash…dokuwidget.html
ganz wichtiges widget das in keinem dashboard fehlen darf. *sfg* ideal für fade vorlesungen.... vielleicht lässt sich daraus auch was extrahieren.

auf ruby quiz gibt es verschiedene loesungen, inklusive diskussion.

Mein Sudoku-Löser im Anhang.

jeuneS2: Ich glaube, deinem Solver fehlen ein paar Funktionen, die man zum Sudoku-Lösen braucht. Nicht, dass ich mir den ganzen Quellcode durchgelesen hätte - so verrückt bin ich auch wieder nicht - aber von den Kommentaren und Funktionsnamen zu schließen halt.

Du schaust glaub ich zwar, ob es für eine bestimmte Zahl nur eine Möglichkeit in einer Zeile/Spalte/Feld gibt, aber du solltest auch nachschauen, ob, wenn es 2-3 Möglichkeiten gibt, diese respektive in derselben Feld (bei Zeilen und Spalten) bzw Zeile oder Spalte (bei Feld) sind. Wenn alle möglichen Vorkommnisse einer Zahl in einer Zeile/Spalte in demselben Feld sind, kannst du alle anderen Möglichkeiten dieser Zahl in demselben Feld eliminieren. Genauso kannst du, wenn in einem Feld alle Möglichkeiten einer Zahl in derselben Zeile/Spalte liegen, alle anderen Möglichkeiten dieser Zahl in der entsprechenden Zeile/Spalte wegwerfen.

Ich hoffe, das war halbwegs verständlich formuliert

Zitat von Lynx

jeuneS2: Ich glaube, deinem Solver fehlen ein paar Funktionen, die man zum Sudoku-Lösen braucht. Nicht, dass ich mir den ganzen Quellcode durchgelesen hätte - so verrückt bin ich auch wieder nicht - aber von den Kommentaren und Funktionsnamen zu schließen halt.

Du schaust glaub ich zwar, ob es für eine bestimmte Zahl nur eine Möglichkeit in einer Zeile/Spalte/Feld gibt, aber du solltest auch nachschauen, ob, wenn es 2-3 Möglichkeiten gibt, diese respektive in derselben Feld (bei Zeilen und Spalten) bzw Zeile oder Spalte (bei Feld) sind. Wenn alle möglichen Vorkommnisse einer Zahl in einer Zeile/Spalte in demselben Feld sind, kannst du alle anderen Möglichkeiten dieser Zahl in demselben Feld eliminieren. Genauso kannst du, wenn in einem Feld alle Möglichkeiten einer Zahl in derselben Zeile/Spalte liegen, alle anderen Möglichkeiten dieser Zahl in der entsprechenden Zeile/Spalte wegwerfen.

Ich hoffe, das war halbwegs verständlich formuliert

Die letzte Variante ist implementiert, die erste Variante glaube ich tatsächlich nicht (was aber kaum aufgefallen ist). Andererseits ist mir mittlerweile nicht mehr so langweilig daran weiterzubasteln...

Zitat

There might be some further enhancements, feel free to implement them.

http://www.ffconsultancy.com/free/sudoku/index.html

Ein Loeser in ocaml + Links auf andere Implementationen.

nur mal so ne frage, aber so ein sudoku lösen, dafür müsste sich ja prolog schon geradezu anbieten, da müsste man dann nur mehr die regeln in prolog-sprache packen, könnte eine schnelle (schnell geschriebene) lösung sein, wo sind die logikorientierten experten??
aba so hätte gupu (jaja 4. sem S&IE lässt grüßen) doch einen sinn gehabt..

mfg Shine

Zitat von Shine

nur mal so ne frage, aber so ein sudoku lösen, dafür müsste sich ja prolog schon geradezu anbieten, da müsste man dann nur mehr die regeln in prolog-sprache packen, ...

kenn mich mit prolog zwar nicht aus, aber im oktober gabs für die erstsemestrigen einige einführungsveranstaltungen und in einer hat uns ein prof. gezeigt, wie man mit ungefähr 10 zeilen code in prolog ein sudoku löst.
anscheinend ist das ganz einfach machbar.

Zitat von Shine

nur mal so ne frage, aber so ein sudoku lösen, dafür müsste sich ja prolog schon geradezu anbieten, da müsste man dann nur mehr die regeln in prolog-sprache packen, könnte eine schnelle (schnell geschriebene) lösung sein, mfg Shine

http://groups.google.com/group/comp.lan…153e521d069e019

Nicht nur schneller geschrieben, sondern mit hoher Wahrscheinlichkeit auch effizienter als eine selbst-gebastelte Version in C++ oder Java. Laeuft mit SWI-Prolog.

Tut mir leid, hat ein bisschen länger gedauert -
ein relativer einfacher algorithmus schaut so aus:

Vorgegeben ist ein int[]-Array mit 81 Einträgen, z.b. "sudoku". Die Zahl aus Zeile i, Spalte j findet man in sudoku[9*i + j], also die 4. Zahl der dritten Zeile findet man z.b. in sudoku[9*2 + 3] = sudoku[21] (Bei 0 zu zählen anfangen).

Jetzt initialisiert man das int-Array: In die bekannten Felder schreibt man die entsprechende Zahl, in alle anderen Null.

Dann einmal durchlaufen und zählen, wie viele Nullen im Array stehen, speichern in z.b. nullCount. und erzeugen eine neues int[nullCount], z.b. vars, und speichern darin alle indizes aus sudoku, bei denen der Inhalt 0 ist.

z.b. sudoku[3] = 0 => vars[0] = 3;
sudoku[7] = 0 => vars[1] = 0;
...usw...

Jetzt tun wir begrenzte Enumeration anwenden:

void enumerate(int i, int sudoku[], int vars[]){
  if(sudoku[vars[i]] == 9) {
    if(i == 0) print("Keine Lösung gefunden"); exit;
    sudoku[[vars[i]] = 1;
    i--;
  } else {
   sudoku[var[i]] ++;
   if(i != vars.length) i++;
   if(validate(i, sudoku, vars)) print("lösung gefunden"); exit; 
   else enumerate(i, sudoku, vars);
}


Die Funktion validate überprüft, ob sudoku eine lösung ist,
also ob in jeder spalte, zeile und kastl jede zahl nur einmal vorkommt.
Man braucht eh immer nur die Spalte/Zeile/Kastl überprüfen,
wo sich grad was geändert hat.

Ich denk, es sollt so passen, wie gesagt ist mir meine Platte kaputtgeworden, drum kanns sein, dass fehler drin sind.

LG Georg

Sudoku Solver by Logic