Namenlosnameless - Sa 25.12.10 15:23
Titel: Sudoku Creator

---

Hallo!

Mein erster Post im Algo-Forum :D

Wie durch ein Wunder hab ich ein bisschen Programmieren gelernt ^^ und wollte mal meinen ersten Veruch zu programmieren, in die Tat umsetzen!
Das wäre ein Programm, dass Sudokus erstellt.

Bevor jetzt ein Aufschrei kommt gleich mal vorweg, das Grundprogramm steht (so ziemlich), es hat nur einen großen Fehler!
nämlich: Es kommen unlösbare Sudokus raus.

Ich habe alle Regeln zum setzen von Zahlen implementiert (also: pro Reihe und 3x3-Quadrat jede Zahl nur einmal).
Die für jedes Feld möglichen Zahlen werden per Zufallsgenerator reingeschrieben. Leider gibt es dann irgendwann das Problem, dass für gewisse Felder keine Zahlen mehr möglich sind, und diese können, selbst bei halb gefüllen Spielfeldern, das Sudoku rein theoretisch nicht lösbar machen!

Die Bilder sind im Anhang zu finden!


Bild1: (das Sudoku wird ganz gefüllt! Alle Felder die leer sind haben keine mögliche Zahl
Bild2: Das mittlere Quadrat ist nicht lösbar, da der 2er in die Mitte-Unten muss und dann für einen 9er kein Platz mehr ist. Diese Fehler werden, durch Felder ohne mögliche Zahl verursacht.

um zu verhindern, dass ich Felder ohne Kandiaten hab, brauche ich eine ungefähre Anleitung, für einen Algo. (Es hilft auch nichts meinen bestehenden Algo x-mal laufen zu lassen es ist immer ein Fehler drinnen).


Falls ich irgendwas im Post vergessen haben sollte, bitte sagen :D


mfg Namenlosnameless

Kha - Sa 25.12.10 17:15

---

Glaubt man dem Blog [http://sudokublog.typepad.com/sudokublog/2005/08/where_do_sudoko.html], denn ich mal schnell für dich ergoogelt habe ;) , solltest du lieber erst durch Backtracking ein vollständiges Spielfeld erzeugen und dann zufällige Zahlen entfernen, solange die Lösung eindeutig bleibt.

Namenlosnameless - Sa 25.12.10 17:25

---

das tue ich!!

Leider bekomme ich kein vollständiges Spielfeld ;D

platzwart - Sa 25.12.10 17:32

---

Na dann tust du es wohl nicht!

Nutzt du denn bereits Backtracking -> scheinbar nein, das solltest du erst mal ändern, dann klappts auch ;)

Namenlosnameless - Sa 25.12.10 18:39

---

ich versuche es zu benutzen! Also ich generiere ein volles Feld und entferne daraus!

Nur das Feld wird nicht ganz voll, da an manchen Stellen, einfach Felder auftreten, für die es keine gültige Zahl gibt. (Also wird das Feld nicht ganz voll)

platzwart - Sa 25.12.10 20:01

---

Ich glaube, du verstehst nicht, was Backtracking bedeutet? Das bedeutet NICHT, alle Felder ausfüllen und dann ein paar Stück löschen. Sondern es ist ein Algorithmus, der genau an der Stelle aufhört, wo keine Lösung möglich ist, den letzten Schritt rückgängig macht und mit es mit einer anderen Zahl oder Platz probiert. Das ganze kann man sich in einer Baumstruktur vorstellen. Der Algorithmus macht solange Schritte rückgängig, bis eine neue gültige Lösung entsteht. Am Ende von Backtracking sind alle Felder ausgefüllt. Das Leeren von manchen Feldern musst du dann wieder gesondert programmieren. Einfach mal nach 'Backtracking' googlen.

Namenlosnameless - Sa 25.12.10 21:17

---

Ohhh :D

Es würde sinn ergeben die letzten Worte ins Kha's Post zu lesen :D

Okay so werde ich das mal probieren :)

Namenlosnameless - Fr 31.12.10 03:20

---

wuhu!!!

Ein Hoch auf Backtracking :D


hab mir die letzten 7 stunden zum Debuggen um die Ohren geschlagen! jetzt ist es 2:15 und ich habs vollendet :)

Ein herzliches DANKE an alle die mir geholfen haben!