Sudoku

[alzaimar]

Zitat:

Zitat von Grishnak

Ich habe mich ebenfalls an einem (Multi-)Sudoku-Solver versucht. Das Programm errechnet per Backtrac(k)ing alle möglichen Lösungen.

Das ist überflüssig, weil es per definitionem sowieso nur genau eine Lösung für jedes Rätsel gibt.

Nur der Vollständigkeit halber hier meine Version. Es verwendet für jede Spalte, Zeile und 3x3-Quadranten die Menge der möglichen Zahlen.
Sei Z[i] die Menge der möglichen Zahlen, die in Zeile i vorkommen können, S[j] die analoge Menge für die Spalten und Q[i,j] Selbiges für den 3x3 Quadranten, in dem i und j liegt. Dann sind die möglichen Zahlen für Zelle[i,j] die Schnittmenge Z[i]*S[j]*Q[i,j].

Das Programm ermittelt zunächst eine Liste der freien Zellen und initialisiert die eben erwähnten Mengen. Dann prüft es im zweiten Schritt, ob für eine Zelle [i,j] die Schnittmenge aus genau einem Wert besteht--> Die Zelle kann gleich belegt werden. Dieser Schritt ist nicht notwendig, schränkt jedoch die Anzahl der Möglichkeiten u.U. sehr stark ein,

Abschließend wird per Backtracking (wirklich mit 'k') nach der Lösung gesucht. Beginnend mit der linken oberen Zelle werden nacheinander einfach alle Möglichkeiten, die sich aus den Schnittmengen ergeben, durchprobiert. Die SW sucht zwar weiter, nachdem eine Lösugn gefunden wurde, aber wie ich schon sagte, ist das bei echten Sudoku-Rätseln überflüssig.

Das Programm verwendet ein Beispiel-Rätsel und ist nur als Demo gedacht: Eine komfortable GUI ist nicht implementiert.

[Grishnak]

@alzaimar: Es ist mir bekannt, dass ein Sudoku nur eine Lösung haben sollte!

Anbei meine neueste Programm-Version, die auch Sudokus (die eindeutig lösbar sind) generieren kann! Schaut es euch doch bitte mal an!

[sECuRE]

Hi,

@Grishnak: Hübsches Programm, darf ich den Source dazu verwenden, Sudokus für meine Homepage zu generieren?

Danke & cu

[NicNacMan]

soooooo,

nach langem hin und her, hab ich jetzt die neue version fertig.
ich hab wieder mal alles umgestellt, das gitter besteht jetzt nicht mehr aus 81 einzelnen feldern, sondern aus einer komponente, die alles verwaltet, was mit dem eigentlichen lösen des rätsels nichts zu tun hat (rückgängig-/widerrufenfunktionen, usw.).

beim lösen wird jeweils zuerst das feld gesucht, in dem am wenigsten werte möglich sind, die dann nur noch probiert werden müssen.
dadurch läuft das ganze ein ganz kleines bisschen (achtung ironie) schneller, als meine erste version, in der ich ja noch mit strings gearbeitet hab *schäm*.
bei mir (amd 2000+) generiert er 100.000 mögliche lösungen in nur 7,2 sekunden.

würde mich über anregungen, verbesserungsvorschläge, usw. freuen.

mfg nicnacman

[negaH]

@alzaimar:

Deine Lösung ist vom Algorithmus her die effizienteste, und auch exakt das was ich gemacht hätte. Ich sehe, wenn man die Sequenznummer der Lösung benötigt, auch keinen anderen und effizienteren Algorithmus. Besonders gefallen haben mir die effizienten Datenstrukturen. Wenn man aber die sequientell korrekte Sequenznummer der Löung nicht braucht so müsstest du deinen Algo. mit Heuristiken erweitern. D.h. zu jedem möglichen Zug, bezogen auf die Spalten und Zeilen, wird ein Priority Stack angelegt. Dieser enthält sortiert den wahrscheinlichst besten Zug auf Spalten/Zeilen Ebene und wird TopDown abgearbeitet. Das dürfte nochmals die Suchmenge bis zu einer Lösung auf maximal quadratisch reduzieren, -> Wurzel(Kombinationen), oder im bestcase auf linear 9x9 kommen.

@Grishnak:

Dein Ansatz eine Klasse zu schreiben ist der sauberste, allerdings solltest du die Größe des Gitters und das Set der möglichen Ziffern dynamisch machen. Zb. 4x4er Blöcke mit Buchstaben von A..N.

@nicnacman:

Dein Algo. ist fast identisch zu Grishnaks und die grafische Gestaltung und besonders die Bedienung gefällt mir sehr gut. Versuche nun mal zwei neue Klassen zu bauen. 1.) so wie Grishnaks TSoduko mit obigen Verbesserungen und 2.) mit Alzaimars Algorithmus.
Beim TForm solltest du biMaximize aus den Borderstyle nehmen, den Weissen Hintergrund ansprechender mit einer dezenten Grafik hinterlegen (zb. ein transparentes Soduko Zahlen Bild), und deine Buttons in eine Toolbar einbauen.

[edit]
Achso, deine "Mögliche Werte anzeigen" Option könntest du noch erweiteren um eine "Beste Werte Option". Diese würde nun schon ausrechnen welches Feld mit welchem Wert zuerst am besten auszufüllen wäre. So könnte man sehr gut grafisch erkennen können wie die Heuristiken bei Alzaimars Algorithmus arbeiten müssten.
[/edit]

@negah:

Klugscheisser ;)

[edit]
Anbei eine verbesstere Lösung. Sie benötigt wesentlich weniger Durchläufe als die eh schon relativ optimale Version von Alzaimar. Den Algo nun so umzubauen das er ein Soduko erzeugt ist sehr einfach.
[/edit]

Gruß Hagen

[NicNacMan]

ok, danke erstmal,

hab mir grade mal dein programm angeguckt, muss es aber noch verarbeiten... :wink:
fest steht, dass ich unnötig alle möglichkeiten ausprobiere, von denen die meisten garnicht gehen können.
was aber immer noch deutlich schneller geht, als mein erstes programm ...

das mit biMaximize is wohl wahr, hab ich überhaupt nicht bemerkt, thx ^^
n schickes hintergrund bild is auch nicht schlecht, folgt dann später.
aber wie meinst du das mit den klassen? ich hab ja schon das meiste in der extra klasse, die aber in ner eigenen unit sitzt.
oder soll ich eine für das gui und eine für den algo machen? wobei der bei mir ja immo nur aus einer funktion besteht.


thx 'n cu nicnacman

[negaH]

Hi

hier noch mal eine wesentlich bessere Verion, algorithmisch gesehen ;)

Du sollest mal Game 36 laden, das wird sofort nur durch reine Logik gelöst und es muß also keinerlei Trial&Error mehr durchgeführt werden.

Gruß Hagen

[Phoenix]

Boaaah. RESPEKT! :thumb:

Ich werd mich jetzt absichtlich nicht näher mit Euren Lösungen beschäftigen sondern mir selber mal einen Lösungsweg anhand der Textbemerkungen ausarbeiten.

Mit Sudokus hat mich meine Freundin am Wochenende überrascht und sie ist seitdem der absolute-Überlöser und ich erwisch an wichtigen Entscheidungpunkten immer die falsche Zahl und merke das erst nach 3 - 5 weiteren Schritten und mir isses dann zu Blöd die letzten Schritte zurückzuverfolgen um das wirklich zu lösen. Da bietet sich die meta-Lösung als Code deutlich besser an *g*

Auch so einen Generator fände ich dann für meine eigene Homepage auch klasse. Also gleich in .NET schreiben und per ASP auf die HP damit hinterher *gg*

Ich melde mich wieder wenn ich was zum vorzeigen hab.

[negaH]

Schau mal hier http://www.scanraid.com/Sudoku.htm dort stehen alle Tricks um ein Sudoku per Logik zu lösen.

Mein obiger Source benutzt schon Box/Line Reduction, Hidden Pairs, Pointing Pairs, Pairs/Tripples Test.
Bin gestern erst auf Suche gegangen und habe diese Seite gefunden. Interessant fand ich eben den Fakt das es noch mehr logische Möglichkeiten gibt auf die ich selber nicht gekommen bin ;)

Ich habe mal einige Spezial Games auf XWing, Sword-Fish etc. pp. hin überprüft. Unter meinen 95 Testgames waren nur jeweils 1 auf das man diese Techniken anwenden konnte.

Viel interessanter dürfte es nun sein Sudoku Games per Machine zu erzeugen. Dabei aber nicht wie fast alle Programme per Zufall ein Game zu erzeugen und es dann so lange zu reduzieren wie es nur eine Lösung gibt. Sondern eben gezielt schwierige Games zu konstruieren.

Gruß Hagen

[igel457]

Mensch macht ihr das Kompliziert! Ich hab mich einfach drangesetzt, als ich so eine Aufgabe bekommen habe und jetzt läuft es. Unter 300 Zeilen Code! Meins ist vieleicht nicht das schnellste...

Irgend eine Internetseite (bis auf DelphiPraxis :)) habe ich dabei nicht gebraucht!

Das hier ist bei mir rausgekommen.

Igel457