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 :thumb: :thumb:

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! :thumb:

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 :roll:, 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 :wall:.
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. :gruebel:

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

[NicNacMan]

hi, erstmal danke für die vorschläge.

also, wenn ich das alles richtig verstanden habe, dürfte das auch dann kein problem mehr sein,
verschieden schwere rätsel zu lösen/erstellen (bei denen ja nur verschieden viele zahlen fehlen).
mein problem ist jetzt nur, das rechnen mit den bitcodierten Cardinals.
shl sagt mir zwar was (du hattest das glaube ich auch schon ein paar mal im form erklärt), aber benutzt hab ich das nie :roll:. naja, aber das werde ich dann jetzt mal ändern.

edit: so, hab noch n bisschen rum probiert:

Delphi-Quellcode:

var
  Field   : Array [1..9, 1..9] of TField  // record mit possible(Cardinal) und current(0..9)
  Row, Col: Array [1..9] of Cardinal;
  Block   : Array [1..3, 1..3] of Cardinal;

{...}

procedure OnFieldChange(Sender: TObject);
begin
  with TSudokuField(Sender) do
    begin
      Field[Xpos, Ypos].Current := Value;
      Col[Xpos] := Col[Xpos] and (1 shl oldValue);
      Col[Xpos] := Col[Xpos] or (1 shl Value);

      Row[Ypos] := Row[Ypos] and (1 shl oldValue);
      Row[Ypos] := Row[Ypos] or (1 shl Value);

      {...}
    end;
end;

funktioniert nur noch nicht so richtig: das löschen mit and funzt nicht richtig, obwohl es eigentlich so richtig sein müsste, oder?

naja, morgen gehts weiter...

nicnacman

[negaH]

Delphi-Quellcode:

 Row[Ypos] := Row[Ypos] and [b]not[/b] (1 shl oldValue);

Gruß Hagen

[NicNacMan]

ah thx, :cyclops:
jetzt gehts.

aber was ist, wenn ich aus einer zeile, spalte, einem block einen wert lösche, der dort mehrmals enthalten ist.
dann fehlt er in der variable, ist aber in wirklichkeit noch da.

müsste ich dann bei jeder änderung die felder der betreffenden zeile, spalte, des blocks neu einlesen

Delphi-Quellcode:

Row[y] := 0;
for i := 1 to 9 do
  Row[y] := Row[y] or (1 shl Field[i, y].Current);

oder gibts da noch ne schönere möglichkeit?

nicnacman

[sECuRE]

Hi,

mmh, ihr wisst aber schon, dass gerade schwere Sudokus nicht einfach über das Ausschlussverfahren gelöst werden können?

Kann auch sein, dass ich mich täusche, ich durchschaue den Lösungsansatz, den ihr momentan benutzt, nicht ganz. Vielleicht kann einer ja mal einen kompletten Sourcecode posten?

cu

[NicNacMan]

die schweren rätsel sind ja nur schwer, weil man sich ein paar mal entscheiden muss, welche zahl man nimmt. aber nur ein weg ist richtig.
darum hat mein programm ja auch noch schwierigkeiten damit.
aber bei negahs vorschlag werden alle kombinationsmöglichkeiten gefunden,
da von der jeweiligen ausgangs situation rekursiv alle möglichkeiten durchgegangen werden.
(soweit ich das verstanden habe^^)
werde meinen code auch hier wieder posten, wenn er n bisschen aussagekräftiger ist.
im moment bastel ich aber noch an der rekursiven funktion.

nicnacman

[hflick]

Jesper Högström hat eine Variante entwickelt. Vielleicht kannst Du dort ein paar Dinge "abgucken", falls noch erforderlich :-)

(google besser nach Jesper Hogstrom)

--
Holger

[NicNacMan]

thx, hab auf der suche nach jesper hogstrom auch noch ein paar andere seiten gute gefunden (wen s interessiert):
http://www.scanraid.com/sudoku.htm
http://www.urbanrim.org.uk/sudoku.htm
http://users.pandora.be/vandenberghe...html?how2solve

is natürlich klar, dass sich noch mehr leute damit befasst haben, aber das das sooo viele sind... :roll:
das demotiviert jetzt n bisschen, aber ich werd trotzdem weiter machen :-D
hab ja jetzt einige neue lösungsmethoden (x-wing, swordfish, burma, ...) entdeckt.

ich weiß aber noch nicht, wie ich mit den bitcodierten cardinals schnittmengen rausbekommen kann.
bzw wie ich zählen kann wieviele werte enthalten sind, ohne eine schleife durchlaufen zu lassen.
mit anderen worten ich kann die "boolscher algebra" noch nicht so richtig anwenden (hab aber auch noch nicht danach gesucht).

gn8, nicnacman

[negaH]

Zitat:

ich weiß aber noch nicht, wie ich mit den bitcodierten cardinals schnittmengen rausbekommen kann.

Schnittmenge = A and B; also eine UND Verknüpfung aller Bits, übrig bleiben alle Bits die in allen Werten gesetzt sind. Vergleichbar mit Sets -> [A] * [B] in PASCAL.
Unions, Vereinigungsmenge = A or B; das Resultat enthält alle Bits die in A wie auch B gesetzt sind.

Zitat:

bzw wie ich zählen kann wieviele werte enthalten sind, ohne eine schleife durchlaufen zu lassen.

Bits zählen. Man kann dies per Schleife, per Lookup Tabelle oder per Berechnungenen machen. Suche mal nach BitCount, CountsOfBits(), BitWeigth(), Hamming Distance etc.

Willst du testen ob nur 1 Bit in deinen cardinals gesetzt ist so geht dies mit

Delphi-Quellcode:

if (A <> 0) and (A and (A -1) = 0) then

Willst du das MSB eines Cardinals ermitteln dann mit

Delphi-Quellcode:

 t := A and -A;

Gruß Hagen

[NicNacMan]

sooooo,

erstmal danke für die weiteren tipps.

ich hab in den letzten tagen nochmal komplett von vorne angefangen.
die felder sind jetzt auch schon zur designtime da, und können eigene hintergrundbilder speichern.
ein problem war, dass die 0 (wenn kein wert angegeben ist) im cardinal ja als 1 steht (1 shl 0 = 1)
daraufhin funktioniert das zählen der werte auch nicht.
und das löschen mit "and not" funktioniert auch nicht, wenn ein wert mehrmals in einer zeile/spalte/einem block enthalten ist.
hab mich jetzt so entschieden, dass beim ändern (per hand) alle werte neu eingelesen werden
und geprüft wird, welche werte noch möglich sind, ohne für zeilen/spalten/blöcke variablen anzulegen, die nur aktualisiert werden.
den algortihmus will ich dann so machen, dass zuerst alle werte in eine variable kopiert werden, um damit zu arbeiten, und danach wieder zurück, damit nicht nach jedem schritt alles neu gezeichnet wird.
das kann aber noch ein paar tage (wochen^^) dauern.

hier erstmal der vorläufigen code:

[Grishnak]

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

WICHTIG: bei (fast) leerem Feld nicht auf 'Lösen' drücken, da das Programm dann alle möglichen Sudokus ermitteln wird!

Mit Links-Click werden Zahlen gesetzt, mit Rechts-Click gelöscht.

Nach dem Lösen, kann man sich alle Lösungen über den ScrollBar anzeigen lassen.

Eine Erweiterung zum Sudoku-Generator folgt...

[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

[Flocke]

Zitat:

Zitat von negaH

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.

Da hab' ich auch schon drüber nachgedacht :mrgreen:

Mein Ansatz wäre:
1. Fange an mit einem leeren Brett (Spielnummer = 0, Faktor = 1)
2. Zähle die Anzahl der möglichen Züge (Anzahl)
3. Wähle einen dieser Züge per Zufall und setze die Zahl (Spielnummer = Spielnummer + Faktor * Zug, Faktor = Faktor * Anzahl)
4. Vereinfache die erhaltene Stellung rein logisch (Verfahren je nach gewähltem Schwierigkeitsgrad)
5. Wenn es noch freie Felder gibt, dann fahre fort mit (2)
6. Fertig. Das nach (3) erhaltene Brett ist ein Rätsel mit genau einer Lösung, die vollkommen logisch ermittelt werden kann (hat man ja gerade in (4) getan).

Je nach Schwierigkeitsgrad kann man bei (4) unterschiedlich komplizierte Verfahren einsetzen (Hidden pairs / Pointing pairs / etc.).

Will man ein Spiel aus der Nummer wiederherstellen, dann nimmt man bei (3) einfach keine Zufallszahl sondern (Zug = Spielnummer mod Anzahl, Spielnummer = Spielnummer div Anzahl).

Hatte allerdings noch nicht die Zeit, dass mal in der Realität auszuprobieren.

[negaH]

@Flocke:

das ist mein bisheriger Ansatz und setzt eben auch voraus das man alle bekannten Tricks implementiert hat. Schaut man sich aber alle diese Tricks an so kann man sie in wenige Gruppen einteilen. Die meisten schwierigen Tricks basieren aber immer auf der kombinatorischen Analyse, sprich Entscheidungsketten und deren Beweis per Kontradiktion. Algorithmisch heist das das man per Program einen Entscheidungsbaum benutzt der lange Ketten bildet die sich in den meisten Fällen gegenseitig ausschließen. Das Trial & Error Verfahren ist im Grunde so ein Ding, halt rekursiv und nur auf ein Teilproblem beschränkt.

Klar per Trial & Error kann jeder selbst mit der simpelsten Lösung, so wie igel457, selbst mit einem ziemlich schlechtem Source das Problem lösen, heutige Computer sind eben leistungsstark.

Um aber für den Menschen anspruchsvolle Games zu erzeugen muß der Computer auf logisch lösbaren Kombinationen aufbauen.

Schade das ich keine Zeit habe. Und bisher wüsste ich auch nicht mit welchen Datenstrukturen so ein Entscheidungsbaum aufzubauen wäre. Es gibt aber zb. bei der Entwicklung mit FPGA per VHDL Synthesetools die per mathematischen Verfahren riesige Matrizen von boolschen Formeln auf ein Minimum reduzieren können. Das entstehende Resultat aus logischen Verknüpfungen repräsentiert dann den Source des VHDLs und wird in die FPGA Hardware gepresst. Auf grund meiner Erfahrungen muß ich sagen das diese Sythesetools super Arbeit leisten und oft hochkomplexe boolsche Formeln auf unerwartete Weise reduzieren. Eventuell müsste man sich mal in diese Richtung orientieren.

Gruß Hagen

[Amateurprofi]

Nachdem das Thema Sudoku, so scheint es, in aller Munde ist, möchte ich Euch auch meine Version nicht vorenthalten. Sicherlich nicht perfekt aber ....

[Thanatos81]

//Edit

Bitte löschen, sollte eine PN werden

[JJAnke88]

Hallo, ich habe mich selbst auch einmal an einem Sudoku-Programm versucht

Allerdings habe ich Probleme bei der Überprüfung ob eine Zufallszahl in dem Quadrat
schon vorkommt..

Vielleicht könnt ihr mir ja helfen..

MFG

Edit:

Ich habe einen Kommentar an die Stelle gesetzt wo ich hilfe brauche^^

EDIT 2: KEINER eine Idee?

:coder2:

[Filestricker]

@NicNacMan:
Folgendes Problem bei deinem Progrämmchen. Die internationalen Sudoku-Standards (jaja, gibt es nicht, aber ich kenne sie so, deswegen muss das ja stimmen, oder? ;)) sehen vor, dass die Diagonalen ebenfalls die übliche Vorschrift (jede Zahl von 1-9 genau einmal enthalten) erfüllen müssen. Oder liege ich da falsch? Zumindest die Rätsel, die ich kenne, waren so aufgebaut. Ansonsten :thumb: . Kann mir vielleicht jemand auch ein Programm mit Quellcode geben, das genau das Gegenteil macht, also nicht das Rätsel löst, sondern eins erstellt, das lösbar ist?

Vielen Dank schonmal für eure vielen Antworten... ;)

[Matze]

Hallo JJAnke88, herzlich Willkommen!

Da in dieser Rubrik ein Programm vorgestellt wird, wäre es gut, wenn du Fragen zur eigenen Umsetzung in einer entsprechenden Delphi-Sparte posten würdest (Multimedia). Das Programm aus dem ersten Beitrag ist übrigens Open-Source, evtl. kannst du dort schon eine mögliche Umsetzung für dein Problem finden.

[Christian V.]

@JJAnke88
Ich habe dir die paar Zeilen geschrieben die dir gefehlt haben. Ich habe mir dann deinen restlichen Source noch schnell angeschaut, und bim beim Überprüfen des Quadrates auf Richtigkeit nicht drausgekomen, und habe mir das mal angeschaut. jedefalls enthielt der HilfArray nicht die von dir benötigten Informationen, deshalb habe ich das auch noch umgeschrieben.(Nebenbei noch den Quelltext an dem ich arbeiten usste umformatiert, ich hoffe du kannst ihn so nicht schlechter lesen :wink:, ne echt, an dem musst du arbeiten, das sieht ja schrecklich aus). So müsste die Funktion(pruf) funktionieren.(Ich habe nur die Funktion für die Quadranten angeschaut und umgeschrieben. Ich denke der Rest funktioniert.)
Zudem wäre eine Fehlermeldung hilfreich, die Sagt an welcher Stelle der Fehler liegt. Allerdings musst du dich nun mit einem neuen Problem herumschlagen: Es werden nicht Alle Felder ausgefüllt wenn ich auf NewGame drücke, die hälfte der Felder bleibt leer.

Delphi-Quellcode:

function CHECK(XKORD,YKORD,AZAHL: BYTE): BOOLEAN;
var qx,qy,temp,i,i2: BYTE;
begin
  CHECK := TRUE;
  {REIHE}
  for I:=1 to 9 do begin
    if  I <> XKORD then begin
      if Sudoku[I,Ykord] = AZAHL then begin
        CHECK := FALSE;
        Exit;
      end;
    end;
  end;
{SPALTE}
  for I:= 1 to 9 do begin
    if I <> Ykord then begin
      if Sudoku[Xkord,i] = AZAHL then begin
           CHECK := FALSE;
        EXIT;
      end;
    end;
  end;
{QUADRAT}
  qx:=(xKord-1) div 3 +1;
  qy:=(yKord-1) div 3 +1;
  for i:= 1 to 3 do begin
    for i2:= 1 to 3 do begin
      if Sudoku[(qx-1)*3+i,(qy-1)*3+i2]=AZahl then begin
        check:=false;
        exit;
      end;
    end;
  end;
end;

///////////////////////////////////////////////////////////////
procedure tform1.pruf;
var
    i,j,x,y,z: BYTE;
    rechts,unten,xkord,ykord: BYTE;
    hilfe : ARRAY[1..9] OF BYTE;
    n,m : BYTE;
begin
  // Initalisierung
  dzahl := FALSE;
  xkord := 1;
  ykord := 1;
  z:= 0;
  //REIHE
  for y:= 1 to 9 do begin
    for i:=1 to 9 do begin
      for j:=1 to 9 do begin
        if j<>i then begin
          if Zahl[i,y]=Zahl[j,y] then begin
            dzahl := true;
            doppelt;
            exit;
          end;
        end;
      end;
    end;
  end;
  //SPALTE
  for x:= 1 to 9 do begin
    for i:= 1 to 9 do begin
      for j:= 1 to 9 do begin
        if i<> j then begin
          if Zahl[x,i] = Zahl[x,j] then begin
            dzahl := true;
            doppelt;
            exit;
          end;
        end;
      end;
    end;
  end;
  //Quadrate
  for rechts := 1 to 3 do begin
    for unten := 1 to 3 do begin
      for x:= 1 to 3 do begin
        for y:= 1 to 3 do begin
          case rechts of
            1 : xkord := x;
            2 : xkord := x+3;
            3 : xkord := x+6;
          end;
          case unten of
            1 : ykord := y;
            2 : ykord := y+3;
            3 : ykord := y+6;
          end;
          for m:= 1 to 3 do begin
            for n:= 1 to 3 do begin
              if (m<>x)OR (n<>y) then begin
                if Zahl[xKord,yKord]=Zahl[(rechts-1)*3+m,(unten-1)*3+n] then begin
                  dzahl := true;
                  doppelt;
                  exit;
                end;
              end;
            end;
          end;
        end;
      end;
    end;
  end;
if dzahl = false then showmessage('Ihre Lösung ist richtig');
end;

Und Bitte halte in Zukunft deinen Quelltext Ordentlicher. Dazu gehört ordentlich Einrücken, und die Begins(Ja, ich weiss, die kann man in bestimmten Fällen weglassen, ist ja ne supersache, aber nicht ÜBERALL WOS NUR GEHT. Das macht den Code sehr schwer Nachvollziehbar wenn überall die end's Fehlen bei for-schleifen.)
Das nächste: hast du den Code eigentlich blind eingetippt? Ohne einmal auf den Monitor zu schauen? Sonst wäre dir sicher aufgefallen, dass du CAPSLOCK eingeschaltet hattes. Der Compiler macht sich daraus zwar keinen Unterschied, aber das menschliche Auge schon. Es ist sehr viel angegnehmer wenn man lowercase(ich meine jetzt hier vor allem Sachen wie end for begin, halt alle reserved words) schreibt.

@Filestricker
Schau dir mal meine Unit an die ich in diesem Forum gepostet habe(class TSudoku). Damit kannst du im Prinzip Sudokus erzeugen. Vorgehensweise: Du setzt zu Begin per Zufall ein paar werte so, dass Sie die "Sudoku Regeln" nicht verletzen. Dann rufst du die Backtracking Methode auf. Anschliessend Entfernst du zufällig mehrere Felder so, dass es per Heuristik-Algorithmus noch lösbar ist. Dann hast ud ein "gültiges" Sudoku mit nur einer Lösung.
Ich werde allerdings diese Funktion in nächster Zeit noch hinzufügen, sodass man die Lösungsfunktionen nicht "zweckentfremden"muss.