Hi,
Ich möcht ein zufälliges Sudoku generieren. ALs Algorithmus dachte ich folgendes:

Nimm dir das aktuelle Feld (am Anfang [0,0]) und schreibe eine Zufallszahl hinein
Teste das Suoku Feld auf Zeilen, Spalten und Blöcke (leeres Feld gilt als Joker)
Wenn Test positiv, gehe zum nächsten
Wenn Test negativ, dann wiedehole Schritt 1 und 2 solange bis der Test positiv ist oder alle Zahlen versucht wurden
Wenn test negativ und alle Zahlen bereits versucht wurden, leere das Sudoku und beginne von neuem


Ich weiss, das ganz von neuem beginnen ist etwas krass und kostet mit Sicherheit Zeit, aber generell müsste man so doch in annehmbarer Zeit ein zufälliges Sudoku Feld generieren können, oder nicht?

Wenn ich meine Prozedur ausführe rechnet und rechnet er und nichts kommt dabei rum. Also habe ich entweder den Algorithmus falsch umgesetzt oder er dauert einfach viel zu lange.

Was meint ihr dazu?

Ich hatte auch mal einen (nichtfunktionierenden) sudoku-generator nach obigem prinzip gebaut. Nur bei Schritt 4 hat mein programm das störende feld ermittelt und abgeändert (die prozedur mit den neuen koordinaten rekursiv aufgerufen) statt neu anzufangen.

Ergebnis: Entweder, es hat sich aufgehängt, es kam totaler quatsch raus ( z.b. mehrmals dieselbe zahl in einer reihe) oder es gab nen stack überlauf...

Erm.. Such mal hier in der DP nach Soduko - vor allem nach den Threads in denen Olli und Hagen (negaH) was geschrieben haben.

Quintessenz war, dass es wohl geschickter sei, erst einen Sudoku-Löser zu bauen und denn dann Rückwärts anzusetzen um an Sudokus zu kommen, die auch lösbar sind.

Und ne MENGE Tipps und Tricks generell dazu und auch wie man da auch von der Geschwindkeit her passabel hinkommt stehen da auch drin.

danke für die antworten.

Ich hab mich etwas durchgelesen und mich für die backtracking methode entschieden. Also fülle ich wie gehabt Zufallszahlen in das Sudoku rein und wenns nicht mehr weitergeht gehe ich ein Feld zurück und haue eine andere Zahl rein usw.

Ist auch von der Geschwindigkeit her i.O.