Sudoku

[seth]

gudn tach!

was meinst du mit tests? funktionsaufrufe der checkfunktion oder anzahl der abfragen/schleifen innerhalb dieser funktion?
ich meinte rekursionsdurchlaeufe. die anzahl der funktionsaufrufe der check-funktion duerfte bei mir schaetzungsweise aber immerhin noch weit unter 1000 liegen.

Mein Algorithmus zum Erzeugen des Sudokus setzt irgendwo eine Zahl und prüft, ob sie regelkonform ist. Wenn nicht, nächste Zahl probieren. Wenn alle Zahlen durchprobiert sind und keine war ok, dann zurück.

wohin genau "zurueck"? (erstmal hoert sich das nach backtracking an)
von welchem algorithmus redest du gerade? du hast ja zwei. ich verstand dich in diesem teilthread bisher so, als spraechest du von jenem (schnellen), der in der wikipedia als "3. weg" beschrieben wird.

Ich habe das Programmieren (Fortran und C) bei Messtechnik- und Numerikproblemen (PDEs) gelernt. Rekursionen, Backtracing etc. sind (noch) nicht meine Welt.

ah, ok, das erklaert so ein bissl dein vorgehen. bei mir war es uebrigens anders herum (erst backtracking in basic und pascal und erst viel spaeter num. pdes und ein klein wenig fortran).

Übrigens ist das größte Problem bei meinem zufällig erzeugten Sudoku, dass ich nur weiß, dass es lösbar ist. Ob es [das] auch eindeutig ist, weiß ich nicht.

ich habe das zwar noch nicht gemacht, aber der erste ansatz der mir dazu einfaellt ist folgender:
man koennte beim aufbauen des feldes ab dem x-ten belegten feld _immer_ _alle_ kombinationen durchprobieren und _nicht_ aufhoeren, wenn man _eine_ gueltige loesung gefunden hat. in backtracking-massstaeben gedacht waere das afais recht einfach zu bewaeltigen.
bei deinem schnellen verschiebe-algorithmus ("3. weg") allerdings, kommt man wohl nicht drumherum erst das komplette feld aufzubauen und nachtraeglich sukzessive einzelne felder wieder zu loeschen, wobei man anschliessend (ab der vierten geloeschten zahl) jeweils mit einem loese-algorithmus ueberprueft, ob man mit einer anderen als der urspruenglichen zahl das sudoku ebenfalls loesen koennte.
ist halt recht aufwendig.

Da auch die Felder mit den Vorgaben zufällig ermittelt werden, weiß ich noch nicht einmal, ob es einen eindeutigen Weg zum Ziel gibt, oder ob ich als Spieler viele Möglichkeiten durchprobieren muss.

naja, das ist ja auch egal. hauptsache das problem ist eindeutig loesbar. der rest (also der weg) ist sache des spielers. ist ja beim sudoku-spielen auch so, dass man manchmal im kopf backtracking betreiben muss.

prost
seth