Sudoku Cocktail 1.5 (löst und generiert Sudoku Rätsel)

jaenicke · Verfasst: Mo 12.09.05 10:25

Hallo!

Die neue Version inklusive Generator (der geht noch nicht gut...):
// EDIT:
Links entfernt, siehe Anhänge ;-)

// EDIT: Der Source ist jetzt sowohl im Setup als auch in der Zip-Datei enthalten.

Jetzt sollten fast alle Sudokus innerhalb von höchstens 5 Sekunden lösbar sein. Da würde mich aber mal interessieren, wie schnell das zweite mitgelieferte Beispiel bei den anderen hier im DF vorgestellten Löseprogrammen funktioniert (bei mir 2 Sekunden, AMD 3800er).
Normalerweise dauerts nur noch einen Bruchteil einer Sekunde.

Die alte Version des Programms inklusive Source gibts hier:
// EDIT: Nicht mehr... ;-)

------ Original-Posting von vorher: -------

Hier im Forum habe ich vor kurzem die Frage gesehen, ob bzw. wie man Sudoku-Rätsel auch mit einem Programm lösen könnte.

Wer Sudoku nicht kennt:
www.wiley-vch.de/dummies/sudoku/

Diese Rätsel kannte ich bis dahin auch nicht, aber sie haben mich sofort interessiert, als ich mir die Regeln angesehen hatte.

Na jedenfalls hab ich mir dann überlegt, wie sowas realisierbar sein könnte, und nach insgesamt ca. 2 1/2 Stunden + 1 Stunde Debugging :-(

war dann dieses Programm fertig!

Die Lösungsweise sollte auch relativ schnell sein, wobei bei der Geschwindigkeit der rekursiven Lösung das Herauisziehen der eindeutigen Werte am Anfang eingentlich gar nicht notwendig wäre (hat aber Spaß gemacht auch das einzubauen...), jedenfalls dauert bei mir (AMD 64 3800er) die Lösung nur einen Bruchteil einer Sekunde...

Bei wenigen vorgegebenen Werten dauerts manchmal lange und manchmal nimmts gar kein Ende, wenn man fast nix angibt (weiß noch nicht warum, d.h. ob er einfach nur alles durchprobuiert und das dauert natürlich oder ob er in einer Endlosschleife ist).

Das Programm stelle ich unter den Bedingungen der LGPL zur Verfügung.

Viel Spaß damit...

Moderiert von Christian S.: Topic aus Open Source Projekte verschoben am So 28.01.2007 um 12:24

Einloggen, um Attachments anzusehen!

Martin1966 · Beiträge: 1068 Win 2000, Win XP Delphi 7, Delphi 2005

Hallo Sebastian!

Da sage ich mal danke. ;-)

Als ich die Frage hier im Forum gelesen habe hat mich das Spiel auch interessiert und ich hatte auch vorgehabt eine Lösung dafür zu programmieren. Aber da warst du ja wohl schneller also ich. ;-)

Ich schaue mir die Sourcen auf jeden Fall mal an.

Lg Martin

BenBE · Verfasst: Mo 12.09.05 19:58

Könntest Du noch einen "Multi-Solver" einbauen, d.h. wenn ein gegebenes Sudoku nicht eindeutig ist, dass er alle Lösungsmöglichkeiten ausspuckt?

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

alzaimar · Verfasst: Mo 12.09.05 22:58

Hier ist meine Lösung...Irgendwie kompakter...und mit Multi-Solver

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Do 15.09.05 16:36

Hallo,

ich bin ganz erstaunt, gibt es nur eine Sudoku Loesung???
ich habe hier genau das gleiche Loesungsfeld meines Vorgaengers alzaimar, auch wenn das Ausgangsfeld sich nur minimal unterscheidet, wobei ich weniger vorgegebene Zahlen habe.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

  Samples : Array [0..8] Of String = (
      'x 6 x 1 x 4 x 5 x',
      'x x 8 3 x 5 6 x x',
      'x x x x x x x x 1', //'2 x x x x x x x 1',
      '8 x x x x 7 x x x', //'8 x x 4 x 7 x x 6',
      'x x 6 x x x 3 x x',
      '7 x x 9 x 1 x x 4',
      '5 x x x x x x x 2',
      'x x x 2 x 6 9 x x', //'x x 7 2 x 6 9 x x',
      'x 4 x 5 x 8 x x x');//'x 4 x 5 x 8 x 7 x'

www.webplain.de/fore...ad.php?1,22871,22910
www.webplain.de/foren/file.php?1,file=1484
Was ein Witz.
Mein Loesungsweg ist komplett anders (siehe den ersten Eintrag)und findet auch nicht alle Loesungen, aber diese.
Meine Loesung testet bei meinem Feld 1863 mal und alzaimar Brute force Methode alzaimar's ruft 69229 solve auf.

Gruss Horst
P.S.:
Villeicht sollte man die freien Plaetze geschickter belegen, indem nur stark belegte Koordinaten bevorzugt.

alzaimar · Verfasst: Do 15.09.05 17:36

Der Witz von Sudoku ist, das es jeweils nur eine Lösung gibt. Deshalb ist es lustiger, ein Programm zu schreiben, das Sudoku-Rätsel erzeugt, und nicht die Lösung (was ja trivial ist, wie wir rausbekommen haben).

Die Lösung von mir ist aber nicht "brute force", sondern "backtracking".

Ich habe mir deinen Code nur rudimentär angeschaut, aber es führen i.A. unterschiedliche Wege nach Rom... Zwei oder drei Möglichkeiten sind sogar im Wiki vorgeschlagen worden.

Ich fand meine Lösung so schön klein. Sie ist zwar nicht optimal umgesetzt, das ist mir jetzt aber egal. Erstaunlich ist, das Dein Ansatz so viel weniger Versuche benötigt. Cool!

Horst_H · Verfasst: Fr 16.09.05 09:06

Hallo,

Meine Loesung sucht wie Jaenicke's Loesung einfach alle schon eindeutigen Belegungen von Feldern.
Also fuer ein Feld fehlen in der Spalte[3,5,6] in der Zeile[1,3,6,8] und im Carree[2,5,6,8] dann ist die Schnittmenge daraus einelementig und enthaelt nur [6]. ALso kann nur [6] an diese Position.
Durch eintragen dieser 6 , werden in der betroffenen Spalte,Zeile,Carree die Moeglichkeiten der anderen Spielfelder eingeschraenkter.
Also wird das komplette Spielfeld solange nach eindeutigen Spielfeldern untersucht, bis keine mehr gefunden werden.
Dies fuehrt schon oft zu einer Loesung. und wie mir auffaellt koennt man das auch mittels Backtracking alle Loenungen finden lassen.

Zu deiner Frage gibt es auch schon etwas, aber ich bin mir nicht sicher, ob es schon richtig funktioniert.
www.softgames.de/for....php?p=656426#656426

Gruss Horst

jaenicke · Verfasst: Fr 16.09.05 11:16

alzaimar hat folgendes geschrieben:

Der Witz von Sudoku ist, das es jeweils nur eine Lösung gibt. Deshalb ist es lustiger, ein Programm zu schreiben, das Sudoku-Rätsel erzeugt, und nicht die Lösung (was ja trivial ist, wie wir rausbekommen haben).

Genau, und da bin ich gerade dabei...

alzaimar · Verfasst: Fr 16.09.05 18:45

Horst_H hat folgendes geschrieben:

Meine Loesung sucht wie Jaenicke's Loesung einfach alle schon eindeutigen Belegungen von Feldern....

Genau, das mach ich auch, nur das ich die Felder nicht vorbelege.

Ehemaliges Mitglied Erhaltene Danke: 1

Irgendwie ist das Geflacker von der Fortschrittsanzeige etwas unnütz.

Horst_H · Verfasst: Sa 17.09.05 13:25

Hallo,

@alzaimar:
Du suchst nur nach einzelnen Wert:
siehe bei jaenecke:
function FindSingleValue: Boolean;
aber nicht so:
siehe bei jaenecke
function SolveSingleOccurrences: Boolean;
oder bei mir
function SpielFeldBewertZeil:boolean;{Nach Spalte hat nicht einmal einen Wert eingefuegt}

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

For Spalte := low(tIndex) to High(tIndex) do
  begin
  TestMenge := [];
  For i :=low(tIndex) to High(tIndex) do
    if i <> Spalte then
      TestMenge := TestMenge + SpFdBewert[Zeile,i].Belegt;
  TestMenge := SpFdBewert[Zeile,Spalte].Belegt-Testmenge;
  Wert := EinzelnerWertAusMenge(TestMenge);//0 oder einzelner Wert
  If Wert <> 0 then
     begin
     WertEinf(Zeile,Spalte,Wert);
     result := false;
     end; {If Wert}
  end;// For Spalte

In der >Zeile< einer Zelle wird die Vereinigungsmengen (Testmenge) der schon belegten Zahlen der aller >Spalten<nachbarn(also dieselbe Zeile) gebildet und die Differenz zur schon belegten Werten der Zelle selbst.
Wenn in dieser Menge nur ein Wert ist-> Bingo dieser muss dann in die gerade untersuchte Zelle eingetragen werden.

Deshalb kommt das Programm in vielen Faellen zur Loesung auch ohne Rekursion und im Beispiel nach 23 kompletten Spielfeld untersuchungen (1863=23* 9*9)

Gruss Horst

Moderiert von raziel: Code- durch Delphi-Tags ersetzt.

F34r0fTh3D4rk · Verfasst: Sa 17.09.05 13:43

alzaimar hat folgendes geschrieben:

Der Witz von Sudoku ist, das es jeweils nur eine Lösung gibt. Deshalb ist es lustiger, ein Programm zu schreiben, das Sudoku-Rätsel erzeugt, und nicht die Lösung (was ja trivial ist, wie wir rausbekommen haben).

Die Lösung von mir ist aber nicht "brute force", sondern "backtracking".

Ich habe mir deinen Code nur rudimentär angeschaut, aber es führen i.A. unterschiedliche Wege nach Rom... Zwei oder drei Möglichkeiten sind sogar im Wiki vorgeschlagen worden.

Ich fand meine Lösung so schön klein. Sie ist zwar nicht optimal umgesetzt, das ist mir jetzt aber egal. Erstaunlich ist, das Dein Ansatz so viel weniger Versuche benötigt. Cool!

jetzt mal meine Frage, heißt es nun Backtracking oder Backtracing ? ich habe anfangs auch immer gedacht es sei Backtracking, aber inzwischen glaube ich auch, dass es Backtracing sein muss, bei meinem mini-backtracing beispiel ist das auch so: seth2000.se.funpic.d...p;um=show&fid=12

alzaimar · Verfasst: Sa 17.09.05 16:44

Eindeutig Backtracking. Der Begriff ist älter als ich.
Es gibt vielleicht auch ein back tracing geben, allein dict.leo.org kennt das nicht. Ich meine, da hat jemand keine Ahnung vom Englischen.

Jetzt, am Wochenende, hab ich die Vorbelegung der eindeutigen Zellen mal eingebaut und siehe da, anstatt 1590 Versuche benötigt die Version nur noch 292 (für das Beispielrätsel).

Einloggen, um Attachments anzusehen!

F34r0fTh3D4rk · Verfasst: Sa 17.09.05 16:46

Backtracing macht aber auch sinn, das heiß ja soviel vie zurückverfolgen, backtracking aber grob übersetzt auch

isja auch egal

Horst_H · Verfasst: Sa 17.09.05 18:01

Hallo,

@alzaimar: Setze mal meine oben gepostetes samples ein, dann braucht es immer noch 39000 Versuche.

Aber egal, die Loesung wird gefunden. fehlt nur ein toller Sudoku-Generator, scheinbar etwas nicht Oeffentliches

www.google.de/search...mp;start=10&sa=N

Gruss Hort

alzaimar · Verfasst: Sa 17.09.05 19:01

Theoretsich könnte man doch einfach einen Sudoku-Generator so schreiben:
1.Finde irgendeine Lösung.
2.Nimm solange irgendwelche Zahlen weg, solange die Lösung (-->der schnellste unserer Sudoku-Solver, also nicht meiner) des resultierenden Sudoku-Rätsels eindeutig ist.
3.Akzeptiere nur Lösungen, die weniger als X besetzte Zellen haben.

Gut, das Teil rechnet ewig, aber so gehts trotzdem.

Bei 2. gibt es Strategien, die schneller zum Ziel führen...

Grishnak · Beiträge: 221 Windows XP Home Delphi 7 PE, Delphi 2005 PE

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...

Einloggen, um Attachments anzusehen!

_________________
Mach' etwas idiotensicher und irgendjemand erfindet einen besseren Idioten!

Horst_H · Verfasst: So 18.09.05 23:17

Hallo,

ich habe mal aus Gag aus Jaenike's BeispielSukuko in der Zeile 6 immer mehr fehlen lassen,
bis keine Loesung mehr moeglich war.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

  0  3  0  0  0  9  0  1  2
  0  8  0  0  0  0  0  0  0
  6  2  0  0  8  0  0  0  4
  8  5  0  3  0  2  7  0  0
  0  0  0  0  0  0  0  0  0
  0  0  2  0  0  1  0  0  0// 0,0,2, 9,0,1, 0,6,8, im Original
  7  0  0  0  9  0  0  2  3
  0  0  0  0  0  0  0  8  0
  4  6  0  1  0  0  0  5  0

Wann wird denn das Programm fertig ? Und laeuft und laeuft und laeuft (15 min bei 1800 Mhz)...

Ich komme ohne Rekursion bis hierhin (1,9s fuer 10000 Durchlaeufe):
Es sind offensichtlich zwei Loesungen einmal
8,9 oder 9,8 in Spalte 4,9 und umgekehrt.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

Freie Stellen 4
  5  3  7  6  4  9  8  1  2
  9  8  4  2  1  3  6  7  5
  6  2  1  7  8  5  3  9  4
  8  5  9  3  6  2  7  4  1
  1  7  6  0  5  4  2  3  0
  3  4  2  0  7  1  5  6  0
  7  1  8  5  9  6  4  2  3
  2  9  5  4  3  7  1  8  6
  4  6  3  1  2  8  9  5  7

Da funktioniert solver 0.3 wesentlich besser.

Gruss Horst

Grishnak · Beiträge: 221 Windows XP Home Delphi 7 PE, Delphi 2005 PE

Horst_H hat folgendes geschrieben:

Da funktioniert solver 0.3 wesentlich besser.

Ich weiß jetzt nicht, ob du mein Programm meinst :?:

, aber das braucht für dieses Problem nur einen Sekundenbruchteil (AMD 2400+) :wink:

.

_________________
Mach' etwas idiotensicher und irgendjemand erfindet einen besseren Idioten!

Horst_H · Verfasst: Mo 19.09.05 08:05

Hallo,

uups, der Schock nach dieser merkwuerdigen Wahlentscheidung war wohl zu gross.
Nun gut:"Im liberalem Sinne ist liberal nicht nur liberal"<Loriot>

Dein Programm v0.3 , Grishnak, funktioniert ja tadellos.
Aber ich habe es zuerst mit Jaeneke's sudoku_solver probiert, da es ja dort das Beispiel ist und nur Geflacker gesehen.

Ich gruebele noch darueber, wieso eine zusaetzliche Spalten, Caareebewertung analog zu meinem Post vom Sa 17.09.05 13:25 , nur Zeit koste aber nur sehr selten eine neue Zahl eintraegt.
Vielleicht sind die Beispiele auch zeilenlastig.

Gruss Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme