hallo leutz,

erstmal: für die, die nicht wissen, was sudoku ist, eine beschreibung: www.wiley-vch.de/dummies/sudoku/


ich habe eine wette angenommen und muss jetzt mit delphi 5 ein sudoku-programm schreiben, bei dem eine unbestimmte anzahl an zahlen vom user vorgegeben wird und das prog soll dann die übrigen zahlen ausrechnen.

ich habe nur dummerweise keine idee, wie ich das machen könnte. hat jemand den glorreichen tipp für mich oder gar ein ganzes prog?

Bitte rettet mich!

MfG Felix


Moderiert von UGrohne: Topic aus Sonstiges verschoben am So 11.09.2005 um 00:39

Hallo!

Als begeisterter Sudoku-Spieler (immer auf der Webseite der Zeit ) habe ich mir auch schon solche Gedanken gemacht.

Grundsätzlich prüfst du jedes freie Feld, ob eine Zahl dort eindeutig zugewiesen werden kann und fügst diese Zahl, wenn gefunden, ein. Das wiederholst du solange, bis keine freien Felder mehr vorhanden sind.

Das basiert aber auf der Annahme, daß es grundsätzlich durch Eindeutigkeiten auf der ersten Ebene lösbar ist. Wenn es zu Nichteindeutigkeiten für alle verbliebenen freien Felder kommen kann (wo ich mir nicht sicher bin, ob das bei Sudoku der Fall ist), muß dieser Algo rekursiv angewendet werden (also dann mit einer möglichen Zahl in einem Feld ausprobieren und o.g. Vorgehen anwenden).

Cu,
Udontknow

super idee... nur die frage ist, wie gehe ich dann wieder rückwärts? ich mach mir logischerweise ja ein stringgrid mit 9*9 feldern. und dann lass ich die mit 2 for-schleifen ablaufen. aber wie komme ich wieder zurück, wenn eine zahl nicht passt und ich eine vorherige zahl ändern muss?

Da schnappst du dir dann am besten ein Tutorial über Rekursion ...

Cu,
Udontknow

vielleicht wärs einfacher erstmal nen programm zu entwickeln welches die erstellt. dann ist der weg zu lösung kürzer.

Hi,
ich hab, auf grund dass meine Mutter jetzt auch daran interesse hat, mich mal umgesehen und einen Lösungsvorschlag für dein Problem bietet dir sogar wikipedia

Hi Lord-Shakir,

Da mich das auch interessiert habe ich mal ein wenig gesucht und folgendes gefunden: blogs.borland.com/je...2005/06/13/8273.aspx
Das ist eine mehrteilige Beschreibung, die erklärt wie man ein Sudoku-Programm in Delphi schreiben kann. Es geht zwar um Delphi.NET, aber es ist ja schonmal ein Anfang.

Moderiert von UGrohne: Kommentar entfernt

Hallo!

Ich kannte diese Rätsel noch gar nicht, habs mir aber kurz angesehen. Das war dann interessant genug, dass ich mich sofort hingesetzt habe und ein entsprechendes Programm geschrieben habe.
Und nach 3 1/2 Stunden wars dann fertig.

Steht inklusive Source unter den Bedingungen der LGPL zur Verfügung, siehe hier:
www.delphi-forum.de/....php?p=291436#291436

Leider mit wenige Kommentaren, aber ich denke die Methodennamen und die vorhandenen Kommentare sollten ausreichen.

Sollte unter Delphi 4, 5, 6, 7 und 2005 kompilierbar sein...

Viel Spaß...

Ich freu mich jede woche auf die BamS, da ja da Sudoku drin ist.
Ich hatte gestern das Spiel ohne einen Fehler und ohne Hilfe gelöst .

Außerdem hab ich auch schon überlegt, wie man das proggen könnte.
Aber nicht ein Prog zum Lösen, sondern zum Rätseln.
Ist ja mit deinem Prog auch möglich.

Ich habe da eine bessere Idee:
Für jede Zeile und für jede Spalte werden die Zahlen aufgeschrieben, die in der Zeile/Spalte noch möglich sind.
Sei Z[i] die Menge von Zahlen, die in Zeile #i noch möglich sind und S[j] analoges für die Spalte #j.
Wenn in einer Zeile die Zahlen 1,5,7 und 9 stehen, dann können in dieser Zeile noch die Zahlen 2,3,4,6 und 8 stehen.

Zusätzlich wird das noch für die 9 Quadranten gemacht, q[k] ist dann die Menge der zulässigen Zahlen im Quadrant q.
Seit Q(i,j) der Quadrant der Zeile i und Spalte j.

Die möglichen Zahlen einer Zelle [i,j] bekommt man durch die Schnittmenge von Z[i]*S[j]*q [Q(i,j)].

So. Nun erstelle ich mir eine Liste der freien Zellen 'Cells'. Cells[k].Row ist die Zeile, Cells[k].Col die Spalte der freien Zelle.
Und jetzt würde ich nur noch klassisches Backtracking einsetzen:

Meine hängenden End's sind gewöhnungsbedürft, also nich meckern.

Die hier informell angegebenen Datentypen sind so definiert:


Also:
Erst S, Z und q erzeugen.
Dann die freien Zellen in die 'Zellliste' (ist nicht nötig, aber wesentlich schneller, als jedesmal im Spielfeld nach der nächsten freien Zelle zu suchen).
So, nun einfach Solve (aCells, 0, S, Z, q) aufrufen und warten.

Das geht auch noch einfacher, ohne Rekursion....

Hier die rekursive Lösung:

Hallo erstmal.

Als ich am Freitag inner Fernsehzeitung bei Muttern sowas zum ersten Mal sah, wo man 200 M€use gewinnen kann, wollte ich das für mich auch haben und hab mich an die Lösung gemacht. Weil das ganze schön logisch geht, und mir das 2. Rätsel zu schwer schien, hab ich noch abends mit einem Turbo-Pascal Prog begonnen (ohne schon mal das Web zu bemühen). Das nutzt jedoch kein Backtracking - sondern eine boolesche 27x9er Matrix, in der für jede der 9 Ziffern entweder False oder True (wenn Zahl vergeben) steht. Und das eben für jede der 9 Zeilen, Spalten und 3x3-Felder (Triples). Es geht das 9x9 Feld der Reihe nach durch (ganz simpel als eindimensionales von 0-80 definiert), und wenn keine Zahl (0) drin steht, schaut es sich die Matrix für dessen Nachbarfelder z,s,t an, gibt es mehr als eine Ziffer mit drei Falses, prüft es noch für die freien Felder seiner Reihe, Spalte und auch Nachbar-Triples, ob eine der Ziffern dort nicht mehr stehen darf und setzt diese dann ein. So brauche ich keine Rekursion, damit fast keinen Stack, und in 2 bis 5 Durchläufen des 81er Feldes ist jedes Sudoku mit genau einer Lösung geknackt. Selbst auf einem 2 MHz-KC dürfte es in Basic max. 1 Sek. benötigen, für geschätzte 500 For-Next-Durchläufe. (Schgönnte ja mal 'n Zähler einbauen) Macht sogar Spaß, per ReadKey zuzuschauen, wie die einzelnen Zahlen der Reihe nach eingesetzt werden, wo man im ersten Moment denkt - wie kommt er jetzt drauf, aber dann aha, da liegt die Begründung.

Nebenbei, Rekursion ist, wie die anderen vor mir schon schreiben, etwas für die Knobel-Sudokus mit mehreren Lösungen.

Den Quelltext gibts auf Wunsch, per Mail. (Mein Programmcode hat nur 9 kB/mit 7 kB Quelltext *gg*)

GERRiTsoft hat folgendes geschrieben:

Nebenbei, Rekursion ist, wie die anderen vor mir schon schreiben, etwas für die Knobel-Sudokus mit mehreren Lösungen.

Ein Sudoku sollte IMMER nur eine Lösung haben. Und es reicht, wenn es mehrere Möglichkeiten an einer Stelle gibt, die man nicht sofort auflösen kann, und schon geht es so einfach nicht mehr.
Dennoch gibt es aber normalerweise nur eine Lösung, weil die anderen Möglichkeiten in eine Sackgasse führen.

Und genau an dieser Eindeutigkeit knabbere ich jetzt mit meinem Sudoku-Generator, den ich zu dem Löser geschrieben habe.

Hier der Link zur Homepage des Programms. Es sollte jetzt praktisch JEDES Sudoku innerhalb von wenigen Sekunden lösen. (auch die schwersten...) Den Quelltext dazu veröffentliche ich allerdings nicht mehr (da gibts nur meinen ersten Versuch weiterhin)...
Aber das überlege ich mir vielleicht auch noch wieder anders. (Aber erstmal soll der Generator besser funktionieren.)
www.buchmanager-berl...ts/sudoku/index.html

Da meine Mutter auch gerne Sodokus macht, hab ich mir vorgenommen auch ein Programm dafür zu schreiben.

Meine Ideen dazu waren:

1. Ein Vierdimensionales Array SODUKU[1..3,1..3,1..3,1..3]
So kann jedem Feld eine Koordiante zugeortnet werden.

wobei die ersten beiden Variablen die 9-er Gruppe bestimmen und die anderen die Position des Feldes in der 9-er Gruppe.
[x1,y1,x2,y2] im allgemeinen.

[1,1,1,1] würde dann heißen : In der ersten 9-er gruppe das erste Feld.

Das array ist von einem Selbstdeklrierten typ TZelle

Tzelle = record
Anzeige : Char;
Zahl : Integer;
fixed :boolean ; //ob die Zahl vom Rätsel vorgegeben war;
LMenge: set of intger (1,2,3,4,5,6,7,8,9) ;// Mögliche Lösungen für das feld


[...]
end;

im lösungsalgorithmus wird das feld 81- Anzahl der freien Felder durchlaufen und mit entsprechenden for schleifen getestet, ob für das feld eine Zahl ausgeschlossen werden kann. (Stichwort : Mengendifferenz).

Ist leider noch net fertig.
ich werde es dann aber sehr wahrscheinlich zur verfügung Stellen.

P.S.: In der FH Wedel ist die Programmierung eines Sodoku programms mit allem drum und dran teil eines Vordiploms.

(Googlestichwörter : Delphi , Sodoku, Programme)
auf gut Glück


Vielen Dank für die Aufmerksamkeit.