Wie kann man Sudokus erstellen, die eindeutig lösbar sind?

Question

Ich schreibe ein Computerprogramm, das Sudokus erstellen soll. (Ich weiß, daß es das schon gibt, aber es macht eben mehr Spaß Programme selbst zu schreiben). Im Prinzip ist es auch kein großes Problem, "zufällig" eine Möglichkeit für ein fertig ausgefülltes Sudoku zu erzeugen. Aber ich suche jetzt nach einer Möglichkeit, bestimmte Zahlen zu entfernen, wobei die Lösung natürlich eindeutig bleiben soll.

Gibt es irgendeine bestimmte Vorgehensweise, um das zu erreichen? Besonders bei "schwierigen" Sudokus, wo nur so wenig Zahlen wie möglich stehen bleiben sollen, finde ich es ineffizient, den Computer das Rätsel (ggf. mehrmals) lösen zu lassen und so lange zu probieren, bis man ein Sudoku bekommt, für das nur eine Lösung möglich ist. Wie kann man das besser machen (wobei alle denkbaren Kombinationen auch erhalten bleiben und jeweils eine davon "zufällig" generiert werden soll).

🐟 Fish 🐟 · Accepted Answer

http://mos-page.ch.vu/ Sudoku Generator
oder wenn du selbst einen schreiben willst
http://www.google.de/#hl=de&source=hp&q=algorithmus+sudoku+generieren&aq=1&aqi=g2&aql=&oq=algorithmus+sudoku+&fp=6ec736c950084e81
http://www.delphi-forum.de/viewtopic.php?sid=c90cecef40bbc56b3bacfb5ff2400c3d&t=72883&start=0

Lösungsansatz könnte hier eine Brute Force Strategie sein. Das Problem bei Brute Force ist allerdings das die Anzahl der Vergleiche wxponentiell steigt.
Der Ablauf ist dann der das du einen Baum aller Lösungen erstellst.
Wenn du alle Lösungen bestimmst dann wirst du auf  n^n Vergleiche kommen
Wenn du das weiter optimierst indem nur zulässige Zahlen verglichen werden dann wirdst du die Zugriffe höchstens auf n^n/2 reduzieren können.

Das Problem ist sxchlicht das es keine Eindeutigen Kritereien wie z.B. bei der Sortierung gibt. Wenn du sowas festleben könntest dann könntest du die Vergleichszahlen auf ln(n) reduzieren.

Etwas in dieser Art wird bei MinMax und ß Algorithmus der Schachprogramme gemacht. Allerdings bestimmen diese Algoithmen nicht die gesammte Lösungsmenge.

Eine verblüffenden Lösungsansatz für einen anderes aber ähnlich gelagertes Porblem hat mit mal ein Mathematiker gegeben. Esd ging um die Bestimmung aller Kombinationen der Schreibweise von Umlauten in Texten. >Ich hab diese Problem strait durch eine Rekursion gelöst. Ist aber ziemlich ineffektiv. Die Lösung war dann http://de.wikipedia.org/wiki/Stemming. Du musst es nur schaffen möglichst früh ein Kriterium zur Reduktion zu finden

Guenther · Answer

Lies Dir diesen Beitrag mal durch: http://de.wikipedia.org/wiki/Sudoku. Dort wirst Du einige DenkansÃ¤tze finden,die Dir weiterhelfen kÃ¶nnen.

Wie kann man Sudokus erstellen, die eindeutig lösbar sind?

2 Antworten