Sudoku Generator ohne Solerver möglich?

[Brainiac]

Ich versuche mich gerade an einem Sudoku Generator.

Die suche im Internet war nicht sehr ergiebig. Daher auch mehr eine Grundsatzfrage.

Ist es möglich einen Generator ohne einen Solver zu schreiben?

 

[Redfrettchen]

Hi,
ich denke mal, das hängt von der Definition von Generator ab. Du könntest dir natürlich eine immer gültige Stellung von Zahlen heraussuchen und bloß immer die Zahlen auswechseln, dann bräuchtest du keinen Solver. Aber ich denke, dass ist nicht im Sinne des Erfinders. Also ja, man braucht einen Solver, oder zumindest einen Validator, der überprüft, ob das Zahlenfeld noch den Regeln entspricht (wobei ein Solver natürlich auch als Validator gebrauchte weden kann). Aber inwiefern jetzt ein Validator Vorteile - wenn er sich denn überhaupt von einem Solver unterscheidet - bietet, weiß ich auch nicht.

 

[millinär]

gibts eigentlich nen vertiges source zu nem guten solver?
und am besten noch generator



was soll das bringen generator ohne solver?
mit solver ist es doch recht einfach und schnell

 

[Redfrettchen]

Bestimmt, gibt es "fertigen" Quellcode für Solver, aber wo bleibt da der Spaß, das ganze selbst zu schreiben? Soooo schwer ist es nun auch nicht (leichter als ein AVL-Baum behaupte ich mal, und wer ganz toll ist, findet selbst AVL-Bäume einfach (ich zähle mich nicht dazu btw)).

 

[millinär]

ich hab keine lust das selber zu machen ich hab schon ne gute idee um den solver um den factor 100 zu verschnellern aber keine lust jetzt auch noch den solver zuschreiben

 

[byte]

Pardon: Den Algorithmus kennst Du nicht, aber Du weisst trotzdem schon, wie Du ihn um den Faktor 100 schneller machen kannst?? Das Geheimnis musst Du mir mal verraten.

 

[foobar]

ich hab keine lust das selber zu machen ich hab schon ne gute idee um den solver um den factor 100 zu verschnellern aber keine lust jetzt auch noch den solver zuschreiben

Hörst du dir eigentlich manchmal selber zu? Du kannst keine 2 Sätze geradeaus schreiben, aber willst die Softwareentwicklung revolutionieren.

 

[millinär]

ich bin schon längst auf die Topic eingegangen
hier ist zum beispiel ein sodoku solver mit 2 verschiedenen geschwindigkeiten http://www.sudokusolver.co.uk/

also natürlich kann ich nicht behaupten jeden solver zu verschnellern aber den 0815 solver kann man sicher
optimieren wie dieser link zeigt

 

[Redfrettchen]

lol

In der Zeit, in der du sinnlo - ähm, ich meine schwer verständliche Sachen geschrieben hast, hättest du schon längst einen Solver programmieren können. Den kannst du dann online stellen, damit deine Nachfolger es nicht so schwer haben. Deal or no deal?

btw: SourceForge.net hast du bestimmt schon in Betracht gezogen, oder?

 

[millinär]

ich blick das mit sourceforge nicht da kriegt man dann immer riesen pakete wo ich nicht weis wo hinten und vorne ist

 

[foobar]

ich blick das mit sourceforge nicht da kriegt man dann immer riesen pakete wo ich nicht weis wo hinten und vorne ist

Wo liegt das Problem? tar xvzf myApp.tar.gz und dann das jar oder shell-Script starten.

 

[Brainiac]

aber den 0815 solver kann man sicher
optimieren wie dieser link zeigt

Wie sieht denn der 0815 Solver aus? Es gibt so viele Möglichkeiten einen Solver für Sudokus zu basteln da ist nix mit 0815. Nur mal ein paar Ideen:
- Brute Force
- Dancing Links
- Human Solver
- Logik vereinfachungen
- ...

und jede beliebige Kombination daraus. Also ganz so trivial wie Du das hinstellst ist das sicher nicht.

 

[Kola]

Ich habe mal einen Sodokugenerator auf einem Taschencomputer geschrieben.
-Ich habe 3 von mir gelöste Sudokus fertig eingegeben, davon wurde eins zufällig ausgewählt.
-Dann wurde ein Array aus den Zahlen 1-9 zufällig angeordnet (die Zahlen im Sudoku sind ann Indices des Arrays, es werden praktisch die Zahlen des Sudokus vertauscht).
-Zu guter Letzt wurden die Feldspalten untereinander vertauscht (Feldspalten sind je 3 Spalten).
Damit hat man aus den 3 Ausgangssudokus "zufällige" gemacht.
-Der benutzer mußte die Schwierigkeit eingeben (=Anzahl der Felder, die gestrichen werden)
-Dann wurden aus jeder Zeile Zahlen gestrichen.
-Darüberhinaus nochmal zufällig einzelne Felder gestrichen

Das ganze hat recht gut funktioniert, nur waren die Teile manchmal nicht eindeutig lösbar (Am Ende hast du dann Felder, bei denen du dir es aussuchen kannst, welche Zahl du reinschreibst). Dafür bräuchtest du dann einen Solver...

 

[millinär]

aber den 0815 solver kann man sicher
optimieren wie dieser link zeigt

Wie sieht denn der 0815 Solver aus? Es gibt so viele Möglichkeiten einen Solver für Sudokus zu basteln da ist nix mit 0815. Nur mal ein paar Ideen:
- Brute Force

mit 0815 habe ich natürlich BruteForce gemeint ist jawohl der einfachste oder?
und was ist an "Human" bitte 0815

 

[muckelzwerg]

1)
Ich raff nix.
Was ist denn der "Brute Force" Solver für Sudoku ?
Welches Verfahren meinst Du, und wie ist es Deiner Meinung
nach programmiert ?

2)
Was soll daran optimiert werden ?
Willst Du eine bessere Implementation finden, oder den Algorithmus abändern ?
Ist es dann noch der "Brute Force" Solver, oder ist es dann evtl ein Anderer,
den es vermutlich auch bereits längst gibt ?

3)
[edit=[color=blue]Fehler beim Aussagenzuordnen von meiner Seite[/color]]
Du "versuchst Dich daran einen GENERATOR zu schreiben", und suchst
nach Hilfen im Netz.
Du fragst, ob Du auf den Solver verzichten kannst,[/edit]

und ob es fertige
im Netz gibt.
Gleichzeitig bist Du angeblich tief in die Optimierung eines Solvers eingetaucht.
Dennoch kannst/willst Du den Solver, den Du sicher optimieren zu können glaubst, nicht selbst schreiben. :autsch:
Bis Dus schaffst, das aufzuklären, würde ich vorschlagen :
Fang mal ganz vorne an, bei :
http://de.wikipedia.org/wiki/Sudoku

mfG

-- -- muckelzwerg

 

[Brainiac]

@Muckelzwerg auf wen beziehst Du dich.

ich also Brainiac (ersteller des Thread) hab mich mit dem Thema Solver schon recht intensiv beschäftigt und schreibe auch gerade einen. Um einen Solver zu testen braucht man halt neue Sudokus (daher wäre ein Generator nicht schlecht). Da ich den später auch noch brauche meine Eingangsfrage ob Generator ohne Solver möglich. Mittlerweile bin ich aber zu der Erkenntnis gekommen, geht nicht wirklich. Also erst mal den Solver schreiben.

Mit Brute Force meine ich natürlich, alle noch zu lösenden Felder druchprobieren (als Backtracking implementiert).

Meine Kommentare bezüglich der Solver bezogen sich auf die etwas unqualifizierten Aussagen von Milinär. Wollte nur zeigen das es da keine Standardlösung gibt, und jeder verbesserung (bzw. Optimierung) macht meißt schon einen anderen Solver draus.

 

[muckelzwerg]

*volldolllol*
Ich hab den Thread von hinten nach vorn gelesen und Deinen ersten
Post versehentlich millinär zugeschrieben.
Sorry.
Mein Post bezog sich auf "millinär",
um noch mehr Mißverständnisse zu vermeiden, lasse ich das mal so stehen.

Generator ohne "Solver" ist möglich.
Was Du aber brauchst ist ein "Validator".
So groß ist der Unterschied nur halt nicht, das kommt wohl stark
auf den Generator an.
Die Bedingungen, die Du beim Generieren testest, verwendest Du auch beim Lösen.
Beim Backtracking dürfte es SEHR nahe beieinanderliegen.
Du machst ja sozusagen beim Lösen, wie beim Erzeugen das Gleiche, nur beginnt der Generator mit einem leeren Sudoku und hört mit einem nicht vollen auf,
der Solver beginnt mit einem nicht leeren Sudoku und hört (hoffentlich) mit einem Vollen auf.
Sudoku ist ja so ein Spiel, bei dem es nur einen "Arbeitsgang" gibt.
Nämlich die Zahlen, nach den Regeln anordnen.
Das "Rätsel" entsteht, weil ein Part den Anfang macht, bis nur noch ein Weg zulässig ist, und dann ein andere Part den Rest machen soll.

-- -- muckelzwerg

 

[Gast]

Ich denke keiner wird seinen Solver so einfach rausgeben, da doch recht gut gezahlt wird für

Viele Website und Zeitschrifenbetreiber reissen sich gerade um Sudokugeneratoren.

 

[Lim_Dul]

Ich denke keiner wird seinen Solver so einfach rausgeben, da doch recht gut gezahlt wird für

Viele Website und Zeitschrifenbetreiber reissen sich gerade um Sudokugeneratoren.

Solver != Generator.

Solver sind eigentlich recht einfach zu schreiben. Damit sie in vernünftiger Zeit fertig werden, wird es etwas schwieriger, aber immernoch mit etwas Gehirnschmalz zu lösen.

Vernünftige Generatoren sind da schon ein viel größeres Problem. Die Anforderungen, die an die gestellt werden, sind deutlich komplexer:

• Es soll nur eine eindeutige Lösung geben
• Man soll möglichst wenig raten müssen

Und das zu schaffen erfordert deutlich mehr Aufwand.

 

[muckelzwerg]

Hm,
"eindeutige Lösung" ist doch eigentlich die Grundbedingung ?
Und das mit wenig "raten" versteh ich grad nicht ganz.
Wirklich raten gibt es bei einem eindeutigen Sudoku ja eben nicht.
Was es gibt, ist mehrere Alternativen vorwärts durchgehen zu müssen um Wege
auszuschließen. Die Tiefe die ich in den Baum der möglichen Züge hineingehen muss,
um ein Feld festlegen zu können, macht die Schwierigkeit aus.
Das ist auch nichts anderes, als Backtracking.

-- -- muckelzwerg

 

[Apo]

an sudoku habe ich mich auch schon mal als Belegaufgabe probiert.
Klick mich
Den Solver habe ich schnell mit Backtracking geschrieben und so erstelle ich auch die neuen Levels ... bloss achte ich nicht explizit auf eindeutige Lösungen.
Habe es nochmal probiert, aber irgendwann aufgegeben weil es zu lange gedauert hat bzw ich nicht alles umsetzten konnte wie ich es wollte.
Hatte mir überlegt alle Logiküberlegungen per Algorithmus umzusetzten und somit müsste ja nur 1 zahl immer eintragbar sein, damit es eindeutig ist. Das Problem ist bloss sie konsitent umzusetzten. Hier sieht man die Regeln, die ich umsetzten wollte sehr gut. Vielleicht schaffst du es ja oder ich, wenn ich mal wieder Zeit und Muse dafür finde.