Sudoku Programmieren
- Ersteller werter
- Erstellt am
- 20 April 2006
- 22.682
- 1.316
Eine gute Aufgabe. Also ich hab gehört, dass ein Sudoku zu erstellen sehr schwer sein soll. Wir haben an der Uni damals Sudoku mittels Java gelöst, aber nicht erstellt.
Mein erster Ansatz - sicherlich ned toll - wäre einfach, dass du die eine Anzahl von Feldern vorgibst, die du füllen willst. Per Zufallsgenerator die Felder gemäß der Richtlinien füllst und dann ausprobierst, ob es mindestens eine Lösung gibt.
Kann zu Endlosschleifen und ewigen Laufzeiten führen, drum sicherlich ned perfekt.
Ich bin gespannt, ob jemand n besseren Vorschlag hat. Das würde mich nämlich auch sehr interessieren.
Mein erster Ansatz - sicherlich ned toll - wäre einfach, dass du die eine Anzahl von Feldern vorgibst, die du füllen willst. Per Zufallsgenerator die Felder gemäß der Richtlinien füllst und dann ausprobierst, ob es mindestens eine Lösung gibt.
Kann zu Endlosschleifen und ewigen Laufzeiten führen, drum sicherlich ned perfekt.
Ich bin gespannt, ob jemand n besseren Vorschlag hat. Das würde mich nämlich auch sehr interessieren.
ice-breaker
return void
- 27 April 2006
- 6.257
- 585
also ich hatte mich mal damit beschäftigt und das ist alles andere als trivial,
also es gibt da 2 gute Möglichkeiten:
Ich habe das dann wieder aufgegeben weil ich nen Sudoku-Generator für Handys programmieren wollte und diese dann doch DEUTLICH weniger Leistung haben als unsere Rechner^^
also es gibt da 2 gute Möglichkeiten:
- man erzeugt per Backtracking ein neues Sudoku wodurch man durch geschickte Bedingungen viele fehlerhafte Rätsel gleich von Anfang ausschließen kann
- Man hat ein Grund-Repertoire von 40 Rätseln und modifiziert diese um ein neues Rätsel zu erstellen, aber keine Ahnung wie das geht
Ich habe das dann wieder aufgegeben weil ich nen Sudoku-Generator für Handys programmieren wollte und diese dann doch DEUTLICH weniger Leistung haben als unsere Rechner^^
Aus dem letztjährigen bwinf lassen sich bestimmt auch einige Ansätze herausholen, auch wenn es dort auf Bidoku bezogen ist 
ice-breaker
return void
- 27 April 2006
- 6.257
- 585
neija dieses Bidoku lässt sich nicht im Ansatz mit Sudoku vergleichen, da ist die Komplexität deutlich höher
Ich hab nur gesagt, dass man da einige Ansätze rausziehen kann, wie man sowas prinzipiell erstellen kann (reverse etc). Der Rest ist deine (falsche) Interpretation
tobias1985
Der Erlöser
- 24 April 2006
- 4.963
- 607
Zuerstmal festlegen, wie groß dein Sudoku sein soll. Anschließend füllst du per Script das Sudoku-Rätsel nach den Regeln und hast damit ein gelöstet Sudoku. Nun machste einfach zufällig bestimmte Felder leer. Fertig ist das Rätsel. Oder hab ich einen Denkfehler? 
Prinzipiel ist das erstellen eigentlich relativ einfach... du nimmst ein vorhandenes Sudoku und veränderst dieses. Verändern kannst du es zb in dem du Spiegelst... da kannst du das ganze Feld, Blockzeilen und Blockspalten spiegeln. Du kannst einzelne Zeilen oder Spalten tauschen (nur jeweils in einem Quadrat, aber auf der ganzen Achse). Damit kannst du eine relativ hohen anzahl an unterschiedlichen Sudokufeldern erzeugen.
Als nächstes musst du Zahlen streichen... was auch relativ einfach ist. Zufällig zahlen X Zahlen streichen. Damit bekommt man schon brauchbare Sudokus...
Natürlich kann man jetzt noch das Sudoku per Logik lösen lassen und damit zugleich ein Schwierigkeitsgrad bestimmen. Wobei das eigentlich das Ressourcen intensivste wäre. Ist aber auch nicht wirklich nötig solang man keine schweren Sudokus erstellen will. Schwer heißt ja meistens relativ wenig Zahlen, und da kanns zu uneindeutigen Sudokus kommen oder welchen wo man Raten muss. Wobei letzteres unterumständen beabsichtigt sein kann... aber da kann man nicht wirklich prüfen ob es eindeutig lösbar ist.
Als nächstes musst du Zahlen streichen... was auch relativ einfach ist. Zufällig zahlen X Zahlen streichen. Damit bekommt man schon brauchbare Sudokus...
Natürlich kann man jetzt noch das Sudoku per Logik lösen lassen und damit zugleich ein Schwierigkeitsgrad bestimmen. Wobei das eigentlich das Ressourcen intensivste wäre. Ist aber auch nicht wirklich nötig solang man keine schweren Sudokus erstellen will. Schwer heißt ja meistens relativ wenig Zahlen, und da kanns zu uneindeutigen Sudokus kommen oder welchen wo man Raten muss. Wobei letzteres unterumständen beabsichtigt sein kann... aber da kann man nicht wirklich prüfen ob es eindeutig lösbar ist.
Wenn man aus einem gelösten Sudoku einfach irgendwelche Zahlen streicht, kann es zu Mehrdeutigkeiten kommen.
Ich würde ja verschiedene "Regeln" nach denen sich eine Zahl ergibt programmieren und aus einem vollständigen Feld sukzessive Zahlen löschen, die sich aus den noch vorhandenen nach diesen Regeln schließen lassen.
Du kannst dann sogar den Regeln Schwierigkeitsgrade zuordnen und aus einem gelösten Sudoku durch Einschränkung des Regelsatzes verschieden schwierige Sudokus basteln.
Manche Regeln muß man eventuell miteinander kombinieren. Die einfachste Lautet übrigens: "In jedem Set (Zeile, Spalte, 9x9-Block) kommt jede Ziffer genau einmal vor."
Eine andere könnte lauten: Wenn zur Vervollständigung einer Zeile/Spalte eine Ziffer fehlt, kann die nur in denjenigen an dieser Zeile/Spalte beteiligten 9x9 Blöcken vorkommen, in denen diese Ziffer nicht schon an anderer Stelle vorkommt:
1 X X . X X X . X X X
4 X 1 . X 1 X . X X X
X X X . X X X . X X X
Die Eins in der mittleren Zeile kann nicht die rote sein, wohl aber die grüne.
Ich würde ja verschiedene "Regeln" nach denen sich eine Zahl ergibt programmieren und aus einem vollständigen Feld sukzessive Zahlen löschen, die sich aus den noch vorhandenen nach diesen Regeln schließen lassen.
Du kannst dann sogar den Regeln Schwierigkeitsgrade zuordnen und aus einem gelösten Sudoku durch Einschränkung des Regelsatzes verschieden schwierige Sudokus basteln.
Manche Regeln muß man eventuell miteinander kombinieren. Die einfachste Lautet übrigens: "In jedem Set (Zeile, Spalte, 9x9-Block) kommt jede Ziffer genau einmal vor."
Eine andere könnte lauten: Wenn zur Vervollständigung einer Zeile/Spalte eine Ziffer fehlt, kann die nur in denjenigen an dieser Zeile/Spalte beteiligten 9x9 Blöcken vorkommen, in denen diese Ziffer nicht schon an anderer Stelle vorkommt:
1 X X . X X X . X X X
4 X 1 . X 1 X . X X X
X X X . X X X . X X X
Die Eins in der mittleren Zeile kann nicht die rote sein, wohl aber die grüne.
Entweder ganz primitv zufall oder dann wie dubberle sagt per Regeln. Jedoch stell ich mir das per Regeln doch ein wenig komplexer vor als es sich anhöhrt, ansonsten hat man am ende nur sehr primitve Sudokus. Das mit zufall kann man auch noch verfeinern indem man prüft ob das Sudoku logisch lösbar ist... und damit kann man auch den schwierigkeitsgrad ermitteln.
har genau die regeln interessieren mich; das die nicht geade einfach sind kann ich mir vorstellen. Wenn ich per zufall zahlen auswählen lasse kann es ja passieren das z.b. nur die 1 und 2 gesetzt wird in allen feldern => es gibt keine eindeutige Lösung.
Das sind genau die Regeln die man zum Lösen verwendet. Du suchst dir per Zufall eine Zahl aus und prüfst ob man auf diese Zahl noch schließen kann. Wenn ja weg damit... schau dir einfach mal an wie so ein Sudoku resolver arbeitet.