Sudoku

[NicNacMan]

hi,

diese sudoku rätsel aus japan dürften inzwischen bekannt sein
(sonst einfach mal googlen Sudoku).

ich hab mich mal an einem kleinen prog versucht, das diese rätsel lösen soll.
die einfachen schafft es ohne probleme, aber bei den schweren,
wo sich die möglichen wege verzweigen muss man immer noch per hand nachhelfen.
da werde ich mich aber demnächst nochmal dran versuchen.

würde mich über verbesserungsvorschläge zu funktionen,
design, aber auch zum code freuen.

thx nicnacman

[edit]
ich hab nur eine komponente verwendet: RakUndoRedo
für die rückgängig funktion
[/edit]

[faux]

Wow, nicht schlecht!
Ich bin auch grad dabei sowas zu programmieren (seit ein paar Tagen), weil ich dieses Rätselch ziemlich lustig finde...
Was du noch verbesseren könntest wäre, dass man auch mit den Horizontalen Pfeiltasten Navigieren kann.
Was ich besonders cool finde, ist die Funktion "Mögliche Werte anzeigen".

[sECuRE]

Hi,

solche Programme gibt's schon zuhauf. Von Sudoku Solver (nur Lösen) bis zu Simple Sudoku (erstellen, helfen, lösen). Was mich interessieren würde, wäre ein Sourcecode, wie man diese Rätsel selbst generiert. Sowas gibt's zwar bisher, aber nur in VB (börks) und Javascript (ähem..). Denkanstöße sind willkommen .

cu

[NicNacMan]

@faux: thx, die idee mit den cursor tasten ist gut, werds morgen mal versuchen.

@sECuRE: nimm doch n fertiges rätsel, und vertausche dann einzelne zeilen bzw spalten mit anderen, aus dem selben block (1 mit 3, 2 mit 1, 5 mit 6, usw. aber nicht 2 mit 9 oder 3 mit 4, ...).
kannst es auch drehen, oder spiegeln. dann musst du nur noch n paar felder wieder weg machen, wobei dann aber die richtigen stehen bleiben müssen, damit es noch eindeutig zu lösen ist.

[sECuRE]

Hi,

Sinn und Zweck des Programms wäre es, meine Homepage automatisch mit neuen, selbstgenerierten Sudokus zu füllen - da mag ich nicht jeden Tag ein vorhandenes Rätsel einfügen .

cu

[jfheins]

Das benutzerinterface ist gelungen

Aber du solltest das so machen, dass die Pfeiltasten in die jeweilige Richtung navigieren (oben/unten) und nach Eingabe ein Feld nach rechts gegangen wird

Ach, und wenn nur eine Zahl in ein Feld reinkann, warum nicht gleich automatisch einsetzen ?

[negaH]

@NicNacMan:

kannst du deinen Algorithmus zum Lösen solcher Gitter mal genauer beschreiben ?

Was ich bis jetzt an deinem Source erkennen konnte ist das er rein kombinatorisch alle Lösungen versucht durchzutesten. Das dürfte aber in diesem Falle ziemlich ineffizient sein. Man kann nämlich schon von Anfang an bestimmte Ausschlußannahmen treffen.

Desweiteren ist mir aufgefallen das deine Datenstrukturen, sprich dein Datenhandling sehr ineffizient ist. Statt eigene und auf Effizienz getrimmte Datenstrukturen zu benutzen, benutzt du Strings und ständige String Konvertierungen. Diese Funktionen sind enorm langsame Vertreter für solche Probleme.

Als aller erstes solltest du also anfang eigene und effizentieren Datenstrukturen aufzubauen. Zb.

Delphi-Quellcode:

type
  TFieldNumber = (1..9);
  TFieldNumbers = set of TFieldNumber;

  TField = record
    PossibleNumbers: TFieldNumbers;
    ActualNumber: TFieldNumber;
   ... etc. pp.
  end;

Nun kannst du als allererstes vor dem .Solve() das Spielfeld analysieren. Im obigen Link das erst Game hat zb. in Spalte 4 senkrecht die Zahlen 1,3,4,9,2,5 schon gesetzt, also fest. Es verbleiben nur 3 freie Felder in denen die Nummern 6,7,8 reinpassen können. Aber in der Zeile 5 findet man schon die 6 im mittleren 3x3 Kasten, ergo kann dort eben nicht die 6 stehen sondern nur 7 oder 8. Man kann also herausfinden:

1.) mit welcher Zeile/Spalte dein Suchalgorithmus beginnen muß, nämlich mit der Spalte/Zeile die die geringsten Zugmöglichkeiten zulässt.
2.) zu jedem Feld in deinem Brett kannst du wie oben schon angedeutet von Anfang an ermitteln welche Zahlen überhaupt möglich wären und welche sozusagen von vorhinein ausgeschlossen werden müssen. Im obigen Type -> TField.PossibleNumbers würden diese drinnen stehen. Dies Taktik reduziert enorm die Anzahl der möglichen Kombinationen die dein Algo. druchprobieren muß.

So, nun zum Suchalgo. Dieser sollte sozusagen parallel arbeiten. Das bedeutet, statt immer eine komplette Kombination eines Spielanfanges bis zum maximalen Ende durchzutesten geht man Parallel vor. Dabei muß man aber die Möglichkeit haben
1.) eine ganze Reihen von Kombinationsmöglichkeiten als Zugreihenfolge zu speichern
2.) gleiche Kombinations-Wege auszuschließen, also nicht doppelt/mehrfach zu berechnen
3.) jeder Kombinations-Möglichkeit ein Punktezahl zu vergeben die angibt wie wahrscheinlich man ausgehend von dieser Startkombiantion eine gültige Lösung finden kann

Der Suchalgo. initialisiert nun eine bestimmte Anzahl solcher Suchwege, und legt diese als Objekte in einem Priority Stack ab. Die Priorität welche dieser vielen Kobinationen nun einen/oder mehrere Schritte weitergerechnet werden häng von deren Punktezahl ab. Nach diesen par Schritten wird dieser Such-Weg anhand seiner Punktezahl neu im Priority Stack geordnet. Somit erhalten also diejenigen Such-Wege eine höhere CPU-Zeit und ergo Such-Tiefe die mit höherer Wahrscheinlichkeit eine korrekte Lösung finden werden.

Du musst das sogar so machen wenn du zb. kompliziertere Gitter in sehr kurzer zeit lösen möchtest.

Auf alle Fälle mach weiter, such nach besseren Datenstrukturen und Algorithmen, denn zum Erlernen von komplexen Spielmaschinen und eventuell KI's ist dieses Rätsel idel geeignet. Hast du dich schon mal mit genetischen Algorithmen befasst ? Das könnte dir eventuell weiterhelfen.

Gruß Hagen

[Palando]

Nettes Program!

Ich hatte ein kleines Problem:
Wenn ich eine Zahl in ein Feld eingegeben habe, wurde manchmal ein noch nicht definiertes Feld konfliktrot gefärbt, weil ers mit der Lösung vergleichen hat (?), ich hatte die Zahl allerdings noch nicht. Das war auf die schnelle nicht reproduzierbar und scheint auch nur zufällig aufzutreten, also nicht bei speziellen Zahlen oder Feldern, wenn man das Rätsel neu lädt.
Kannst ja mal schauen ob du was findest.

Fallses was hilft: Es is auf dem einfachen Feld passiert, die andern hab ich nicht versucht.

[NicNacMan]

@sECuRE: du brauchst ja nur ein paar verschiedene, dadurch, dass du die zeilen,... verschiebst und andere werte löschst, erhältst du ja jedes mal ein neues rätsel.

@jfheins: die pfeiltasten stehen schon auf meiner list, aber das automatische ausfüllen macht sinn, thx

@negaH: jo, bis jetzt ist er sehr ineffizient , am anfang werden die möglichen werte für jedes feld aktualisiert,
wobei für jedes feld die reihe, spalte und der 3x3 block durchgegangen wird.

und die sache mit den strings ist leider wahr.
ich hatte die felder anfangs als komponenten, die alle schon zur designtime existierten.
da hatte ich schon die idee statt nem string ein array [1..9] of boolean zu nehmen, aber das ging als komponenteneigenschaft nicht.
und auf die idee mit den teilbereichen und mengen bin ich nicht gekommen .
da werde ich mich dann als erstes mal dransetzen, danke.

zum suchalgo: dafür, dass ich das nur so 4fun gemacht hab, ist das ganze ja doch extrem ausbaufähig...
das "logische" durchgehen der zeilen, spalten, blöcke wäre auf jeden fall die bessere wahl,
demnach müsste ich fast alles nochmal überarbeiten, damit nicht mehr jedes der 81 felder überprüft wird.

hab mich grade mal bei wiki durch die genetischen algorithmen gelesen, ... da werde ich n weilchen brauchen um das richtig zu verstehen.
die theorie ist mir inzwischen etwas klarer, aber ich hab absolut 0 ideen wie ich das umsetzen kann.

aber die sache mit dem priority stack hört sich sehr interessant an, wie kann ich sowas am besten realisieren? (gibts da gute tuts?)
da werde ich mich auf jeden fall als nächstes (gleich nach der datenstruktur) dran machen.
DANKE!


@Palando: es werden auch felder rot gefärbt, in denen kein wert mehr drin stehen kann, weil alle möglichen zahlen schon in der spalte, zeile oder in dem 3x3 block enthalten sind.
wenn du die möglichen werte anzeigen lässt, müsste das feld leer sein.
falls nicht, muss ich nochmal nach fehlern suchen.

[negaH]

Ich habe die Nacht nochmal drüber geschlafen und mich gefragt wie ich es anpacken würde.
Nur mal so als Anregungen:

1.) das Gitter besteht aus 9x9 Cardinal's, jeder speichert Bitcodiert die möglichen Zahlen. D.h. die 1 wäre (1 shl 1) die 2 wäre (1 shl 2) usw. bis (1 shl 9). Dies wäre im grunde identisch mit meinem obigen Vorschlag mit Mengen und Sets zu arbeiten, hat aber einen gravierenden Vorteil diesem gegenüber. Mit solchen Cardinals kann man per Boolscher Algebra, sprich AND, XOR, NOT, OR, viel effizienter nun die Mengen der möglichen Zahlen abfragen.

2.) zu jeder Spalte und Zeile wird parallel zum Gitter ebenfalls ein bitcodierter Cardinal gespeichert. Sobald man also eine Zahl in einer Zelle einfügt/löscht werden diese Spalten/Zeilen Werte ebenfalls per AND/OR aktualisiert.
Du hast also mit diesen Werten die exakte Kontrolle welche Zahlen pro Spalte und Zeile noch frei verfügbar und unbenutzt sind.

3.) zu jedem 3x3 Feld wird ebenfalls ein solcher bitcodierter Cardinal geführt. Auch hier die Grundbedingung das er beim Einfügen/Löschen einer Zahl in einer Zelle entsprechend aktualisiert wird.

4.) der kombinatorische Such-Algortihmus sollte nun absolut deterministisch sein, d.h. komplett ohne irgendwelches Random auskommen. Wird nun eine Countervariable der rekursiven Suchtiefe mitgeführt so indentifiziert diese Countervariable absolut exakt eine gefundene Lösung. Der Suchalgo. könnte nun beginnend mit diesem Counter die logisch nächstfolgende Lösung suchen, usw. usw. Mit dieser Methode ist es also möglich nicht nur eine beliebige Lösung zu finden sondern alle möglichen Lösungen zu errechnen, ohne das man eine auslässt.

5.) ändert man diesen algo so ab das er ohne schon fixierte/vorgegebene Zahlen arbeitet so hast du in fact statt eines Rätsel-Lösungs-Algos einen Rätsel-Erzeugungs-Algo. Dieser Algo kann dann succesive mit Hilfe der Countervariablen ein Rätsel nach dem anderen produzieren.

6.) es ist nämlich für deinen Algo. im grunde egal ob er ein schon bestehendes Rätsel lösen soll oder ob er ein neues Rätsel erzeugen soll. Die Suchstrategie unterscheidet sich in keinster Weise, dereinzigste Unterschied besteht nur darin das in einem Rätsel fixierte Zahlen eingetragen wurden.

Gruß Hagen