Entwickler-Ecke :: Thema anzeigen - Sudoku Cocktail 1.5 (löst und generiert Sudoku Rätsel)

jaenicke - Mo 12.09.05 10:25
Titel: Sudoku Cocktail 1.5 (löst und generiert Sudoku Rätsel)

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:
http://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

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

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'

http://www.webplain.de/foren/read.php?1,22871,22910
http://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 - 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 - 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.
http://www.softgames.de/forum/viewtopic.php?p=656426#656426

Gruss Horst

Horst_H - 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}

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 - Sa 17.09.05 13:43

alzaimar hat folgendes geschrieben:

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: http://seth2000.se.funpic.de/?m=downloads&um=show&fid=12

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

alzaimar - 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 - So 18.09.05 02:20

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

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

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.

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

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

Luzzifus - Sa 29.10.05 14:49

Horst_H hat folgendes geschrieben:

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.

Ich habe diese Idee durch eine weitere Heuristik erweitert, so dass ausnahmslos alle eindeutig lösbaren Sudokus auch gelöst werden können: Zusätzlich überprüfe ich nämlich ob eine Zahl die in einem Feld stehen kann, NUR in diesem Feld der entsprechenden Zeile/Spalte oder des Blockes stehen kann. Zusammen mit diesem Verfahren löst mein Algorithmus ein eindeutig lösbares Sudoku in weniger als einer Millisekunde bei ca. 2-5 kompletten (9x9-) Feld-Betrachtungen. Source ist allerdings weder kurz noch trivial, deswegen nur auf Anfrage.

Jetstream - Di 10.01.06 13:03

Hmmm ich bastel auch grade an nem Solver :)

Der arbeitet nicht mit Bruteforce oder Random-Walk, sondern nur mit Logik.
Das Ganze ist recht schnell (Bruchteil einer Sekunde für jedes Rätsel),
nur mit nem halben MB etwas größer (Quelltext artet etwas aus).

Prinzipiell ist er eher gedacht um beim Rätseln zu assistieren, da er in ein Label alle seine
Schritte nacheinander begründet reinschreibt.

Und die etwas komplexeren Moves lassen sich per Checkbox abschalten, damit man nicht so durcheinanderkommt.
(Es sind noch nicht alle komplexen Moves enthalten die ich umzusetzen gedenke, aber das kommt noch)

http://www.fabiman.de.vu/SudokuSolv.exe

mfg Jetstream

jaenicke - Di 10.01.06 13:17

@Jetstream:
Tja, aber anders als mein Solver löst er eben nicht jedes Rätsel, sondern trägt nur ein, was wo möglich ist. Und nur bei den einfachen Rätslen reicht das schon zum Lösen.
Das ist also ähnlich zu meiner alten Version.

Meine neue Version kann jetzt die meisten Rätsel lösen. Ich hab 4 ausprobiert, die hat dein Programm alle nicht gelöst, und bei mir gehen die in wenigen Millisekunden...

Luzzifus - Di 10.01.06 21:07

jaenicke hat folgendes geschrieben:

@Jetstream:
Tja, aber anders als mein Solver löst er eben nicht jedes Rätsel, sondern trägt nur ein, was wo möglich ist. Und nur bei den einfachen Rätslen reicht das schon zum Lösen.

Das ist also ähnlich zu meiner alten Version.
Meine neue Version kann jetzt die meisten Rätsel lösen. Ich hab 4 ausprobiert, die hat dein Programm alle nicht gelöst, und bei mir gehen die in wenigen Millisekunden...

man kann sehr wohl alle eindeutig lösbaren sudokus nur mit logik lösen. das macht mein programm auch, und zwar in < 1 ms. wenn es eine eindeutige lösung gibt, wird diese auch gefunden. nicht eindeutig lösbare sudokus (also mit mehreren lösungen) spielen praktisch auch keine rolle, da niemand freiwillig sowas von hand löst.

nochmal explizit: ich will eigentlich nur sagen dass nicht nur EINFACHE sudokus mit purer logik lösbar sind, sondern alle die exakt eine lösung besitzen.

für mein programm guckst du mal hier:
http://www.delphi-forum.de/viewtopic.php?p=322573#322573

jaenicke hat folgendes geschrieben:

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

dein programm braucht dafür bei mir mehr als 8 sekunden (athlon XP 2600+). ausserdem ist dieses sudoku eben nicht eindeutig lösbar. die zeit die ein brute force algo braucht sollte maßgeblich von der zahl der unbestimmten felder abhängen bzw. von der anzahl der möglichen lösungen.

jaenicke - Mi 11.01.06 11:43

Also meiner Meinung nach IST dieses Sudoku eindeutig lösbar! Ich konnte keine Möglichkeit finden, eine weitere Lösung zu erzeugen (weder per PC noch per Hand)!

Luzzifus hat folgendes geschrieben:

Bitte??? Dein Programm kann keines (der von mir getesteten jedenfalls) der schweren Sudokus der Zeit (zeit.de/sudoku) oder von anderen Internetseiten lösen!
Die haben aber doch nicht alle mehrere Lösungen. Die Anforderung an ein Sudoku geht ja auch dahin, dass es eine eindeutige Lösung haben muss. Und egal wo ich im Internet nachgesehen habe, überall gibt es Sudokus, die dein Programm nicht löst.

Luzzifus - Mi 11.01.06 14:35

jaenicke hat folgendes geschrieben:

hm ich habe lange zeit sudokus aus zeitschriften und sudoku büchern getestet und bisher konnte mein programm alle lösen. da ich nun aber kein zeit-leser bin werde ich mir das wohl doch nochmal genauer anschauen müssen. ^^ empirie reicht eben doch nicht immer :D

Jack Falworth - Di 29.08.06 20:20

Hallo,
da mich das Thema interessiert und auch gerade einen Solver am Schreiben bin, hab ich mir das ein oder andere Programm mal angeschaut.

Spontan habe ich bei dem Cocktail Programm (v1.5) zwei Sudokus gefunden, bei dem das Programm abschmiert (nur Unsinn ausgibt).
Erstes Sudoku: alle Felder sind leer
Zweites S.:

200000030
070000020
080000000
000000060
306000809
000000000
700000000
820000010
010000040

Das Sudoku hat keine Lösung.

Mein Programm ist zwar noch nicht das schnellste (braucht für das File im Anhang mit 100 solchen Sudokus) noch 5,5 Sekunden, aber es basiert noch ausschließlich auf dem Backtrack-Prinzip (mit mehreren Heuristiken).

Wenn ich demnächst das Setzen eindeutiger Felder über das Schnittmengenproblem einbaue und erst wenn nichts mehr geht auf Backtrack umsteige, sollte das Ganze nochmals deutlich schneller sein.
Halte euch auf dem Laufenden.

PS: Mich würde mal interessieren, wessen Programm das 100er File lösen kann und wie lange gebraucht wird (Tipp: 4 Sudokus davon haben keine Lösung)

Gruß

JackF

Jack Falworth - Do 31.08.06 13:16

Ich glaube so eine Meldung ist gekommen. Aber wieso? Das ist ein Computerprogramm, wieso sollte es solche Sudokus nicht lösen können? Dafür ist ein Solver ja da. Dein Programm kann irgendwie die selbst erzeugten Sudokus nicht lösen? Ist das noch ein Bug oder ist das nur bei mir so (Schwierigkeit war egal)?

In dem 100er File sind noch einige weitere Sudokus drin, die von den verschiedenen Programmen hier nicht gelöst werden können.
Das liegt daran, dass eure Algorithmen (allen Anschein nach) ausschließlich auf der Schnittmengen-Heuristik beruhen.
Damit kann man zwar die meisten Sudokus komplett lösen, andere aber nur teilweise oder gar nicht.

Edit: So habe mein Programm nun noch verbessert und u.a. die Schnittmengen-Heuristik hinzugefügt. Dadurch kann ich nun das
100er-File in stolzen 406 ms lösen :)

jaenicke - Fr 01.09.06 12:57

Die Meldung sollte nur bei sehr wenigen Eingabewerten kommen. (Ich meinte das in Bezug auf ein leeres Sudoku)

Und mein Programm versucht durchaus auch auszuprobieren (mittels Backtracking). Dass ein selbst erzeugtes Sudoku ncith lösbar ist, kann eigentlich gar nicht sein, denn der generator erkennt an der Lösbarkeit durch den eigenen Algorithmus die Gültigkeit (ich versuche schon serit Monaten ein besseres mathematisches Verfahren zu finden, aber bis jetzt haben mich meine Überlegungen nicht sehr weit gebracht, nur mit Hilfe von Permutationen scheint sich eine Lösung abzuzeichnen...)

Aber ich seh mir das nochmal an...

Gravitar - So 22.10.06 18:39

Horst_H hat folgendes geschrieben:

Hallo,

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

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

Hallo Horst,

dieses Problem wird in 801 Rekursionen und 16 Millisec. gelöst.

Gruß, Andreas

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!