Sudoku-Algorithmus

MrMister · Hält's aus hier Beiträge: 12

Hi liebe Forengemeinde,

ich muss für ein Schulprojekt momentan an einem Sudoku arbeiten und habe noch einige kleinere Probleme mit meinem Algorithmus.
Beim erstellen eines neuen Sudokus werden erst einmal alle Felder mit einer immer festen Zahlenfolge gefüllt, so dass ein komplett richtiges und vollständig ausgefülltes Sudoku entsteht. Von da an soll dann über das Tauschen von Zeilen und Spalten ein wenig Zufall in das Spielfeld eingebracht werden, was an sich auch fehlerfrei funktioniert, nur ist die zufälligkeit im Spiel noch absolut ungenügend, da Zahlen in den einzelnen Spalten immer nah aneinander liegen, da sich nicht ordentlich vermischt werden können.
Das Problem: Wie bekomme ich da mehr Zufall rein? Gibts noch andere erlaubte Operationen außer Spalten und Zeilen innerhalb der 9er-Felder zu tauschen?

Hier mal mein bisheriger (primitiver, aber funktionierender) Algorithmus:

Erstellen der immer gleichen Anfangsform:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:

procedure TFormSudoku.fuellen();
var
i, j, k, a : integer;
begin
Randomize;
a:=0;

  FOR i:=0 TO 2 DO
  begin
  inc(a);
  K:=1+(a*3);
    FOR j:=0 TO 8 DO
    begin
      IF K > 9 THEN K:=1;
      StringGrid1.Cells[i,j]:=IntToStr(k);
      inc(k)
    end;
  end;

a:=-1;

  FOR i:=3 TO 5 DO
  begin
  inc(a);
  K:=2+(a*3);
    FOR j:=0 TO 8 DO
    begin
      IF K > 9 THEN K:=1;
      StringGrid1.Cells[i,j]:=IntToStr(k);
      inc(k)
    end;
  end;

a:=-1;

  FOR i:=6 TO 8 DO
  begin
  inc(a);
  K:=3+(a*3);
    FOR j:=0 TO 8 DO
    begin
      IF K > 9 THEN K:=1;
      StringGrid1.Cells[i,j]:=IntToStr(k);
      inc(k)
    end;
  end;
mischen();
end;

Tauschen der Zeilen und Spalten:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:

procedure TFormSudoku.mischen();
var r, t, l, s1, s2, z1, z2, M, p, q : integer;
begin

s1:=0;
s2:=0;
t:=0;
p:=0;

r:=Random(11)+5; //Zwischen 5 und 15 Vertauschungen

While t<r DO
begin
//ShowMessage(IntToStr(t));

  FOR L:=0 TO 2 DO
  begin

    IF L=0 THEN
    begin
    s1:=Random(3);
      Case s1 of
      0: s2:=2;
      1: s2:=2;
      2: s2:=0;
      end; //of case
    end;

    IF L=1 THEN
    begin
    s1:=Random(3)+3;
      Case s1 of
      3: s2:=5;
      4: s2:=3;
      5: s2:=3;
      end; //of case
    end;

    IF L=2 THEN
    begin
    s1:=Random(3)+6;
      Case s1 of
      6: s2:=8;
      7: s2:=8;
      8: s2:=6;
      end; //of case
    end;

    FOR M:=0 TO 8 DO
    begin
      StringGrid2.Cells[0,M]:=StringGrid1.Cells[s1,M];
      StringGrid2.Cells[1,M]:=StringGrid1.Cells[s2,M];
      StringGrid1.Cells[s1,M]:=StringGrid2.Cells[1,M];
      StringGrid1.Cells[s2,M]:=StringGrid2.Cells[0,M];
    end;

  end;

  FOR L:=0 TO 2 DO
  begin

    IF L=0 THEN
    begin
    z1:=Random(3);
      Case z1 of
      0: z2:=2;
      1: z2:=2;
      2: z2:=0;
      end; //of case
    end;

    IF L=1 THEN
    begin
    z1:=Random(3)+3;
      Case z1 of
      3: z2:=5;
      4: z2:=3;
      5: z2:=3;
      end; //of case
    end;

    IF L=2 THEN
    begin
    z1:=Random(3)+6;
      Case z1 of
      6: z2:=8;
      7: z2:=8;
      8: z2:=6;
      end; //of case
    end;

    FOR M:=0 TO 8 DO
    begin
      StringGrid3.Cells[M,0]:=StringGrid1.Cells[M,z1];
      StringGrid3.Cells[M,1]:=StringGrid1.Cells[M,z2];
      StringGrid1.Cells[M,z1]:=StringGrid3.Cells[M,1];
      StringGrid1.Cells[M,z2]:=StringGrid3.Cells[M,0];
    end;
  end;
inc(t);
end;
end;

Ich weiß, dass das ganze alles andere als effektiv und gut ist, aber es ist für meinen Kenntnisstand verständlich, es funktioniert und ich hab es mir als Anfänger selbst erarbeitet.

Ich weiß, dass Sudokus hier schon 1000x durchgekaut wurden, aber die anderen Threads waren bei dieser speziellen Frage nicht wirklich hilfreich, vielleicht erbarmt sich ja jemand und gibt mir nen kleinen Tipp

Anbei noch die aktuelle EXE-Datei, damit man das Problem selbst nachvollziehen kann.

Ist das Ding noch zu retten mit irgendeinem weiteren Kniff oder kann ich damit nochmal von vorne anfangen? Und ist es überhaupt möglich, dass ich aus einem lösbaren Sudoku Zahlen entferne und es trotzdem lösbar bleibt?

Liebe Grüße mit der Bitte um Hilfe,
MrMister

Link zur EXE: mrmister88.mr.funpic.de/sudoku.rar

Horst_H · Verfasst: Fr 18.05.07 09:52

Hallo,

Deine Idee hatte ich auch mal verfolgt, aber das brachte nicht viel
www.softgames.de/for...amp;highlight=sudoku
Es waren nur 18432 Varianten durch Zeilen, Spalten und Carree-Tausch.
Dabei werden viele Möglichkeiten unterschlagen:

Zitat:

P.S.:
es gibt noch so viele ganz andere Varianten
Haben in 3 Zeilen oder Spalten- Carree's drei Zeilen oder Spalten mit gleichen Zahlen besetzt:
1XX X2X X3X
2XX X3X X1X
3xx X1X X2X
Kann man die die Spalten gleichphasig permutieren also 6 Moeglichkeiten ohne die anderen Zahlen in der Position zu aendern

Sind nur zwei Spaltenzahlen nur umgekehrt in den gleichen Zeilen: einer
1XX X2X XXX
XXX XXX XXX
2xx X1X XXX
kann man diese auch tauschen.
Man sollte mal alle moeglichkeiten fuer ein 3x9 Feld testen, das sind ja wohl nicht zu viele.(29 Mio??)

Gruß Horst

MrMister · Hält's aus hier Beiträge: 12

Ok, also muss ich mir was neues einfallen lassen. Ich fand den Vorschlag von Banana-Joe ganz gut und werde wohl versuchen, den mal umzusetzen:

Hallo,
ich habe jetzt eine Methode herausgefunden, mit der man Sudokus erstellen kann.

Zitat:

Der Trick ist ganz einfach:
(Block = 9x9 Felder)
Der Block oben links, der in der Mitte und der unten rechts werden
erstmal rein zufällig mit Zahlen gefüllt.
Da diese sich nicht gegenseitig beeinflussen klappt das problemlos.

So, nun liste ich für jedes freie Feld die möglichen Zahlen auf.
Dann picke ich mir ein Feld mit den wenigsten möglichen Zahlen raus
und stopfe da eine der möglichen Zahlen rein.
Dann aktualisiere ich die möglichen Zahlen bei den anderen Feldern
und suche nach dem nächsten freien Feld.

Das ganze funktioniert (fast) vollkommen einwandfrei.
Ungefähr bei 1 von 5 Versuchen kommt ein fehlerhaftes Sudoku raus.
Dann starte ich einfach den Generator neu und dann ist meist richtig.
Insgesamt brauch der 166MHz-Rechner in meinem Zimmer nie mehr als 3 Sekunden
um ein gültiges Sudoku zu erstellen.
Das neustarten des Generators wäre nicht nötig, wenn ich genau überprüfen würde
wo es sinnvoll wäre welche Zahl zu platzieren.
War mir jetzt aber zu kompliziert und ich habe es einfach so gelassen.
Der Geschwindigkeitsunterschied ist ja auch nur sehr gering.

Nun frage ich mich aber noch, woher weiß ich, welche Zahlen für den Spieler sichtbar sein müssen?
Bei einem 08/15 Sudoku gibt es in einem Block nie weniger als 3 Zahlen.
Und pro Zeile und Spalte gibt es mindestens eine sichtbare Zahl.

Hat irgendeiner eine Idee?

MfG Bananen-Joe

Die Geschwindigkeit ist bei mir zweitrangig, hauptsache es kommt was gescheites bei raus, deswegen dürfte das für mich die beste Wahl sein, oder hat noch jemand einen anderen Vorschlag?

Liebe Grüße,
MrMister

Horst_H · Verfasst: Fr 18.05.07 19:08

Hallo,

das ist doch ein einfacher und ausreichend schneller Weg, uups habe ich ja auch so gemacht.
Also lieber mal anders:Schau Dir aber mal bei Grishnak V0.9.3 die Erstellung des Sudoku's an
www.delphi-forum.de/...rder=asc&start=0

Gruß Horst

MrMister · Hält's aus hier Beiträge: 12

Sorry, bin mir nicht ganz sicher, wie ich deine Antwort deuten soll... Du meinst, ich soll den Vorschlag, den ich da eben zitiert habe, in die Tonne treten?
Hab mir eben mal das Programm von Grishnak angeschaut und werd noch ne Weile brauchen, bis ich da durchgestiegen bin, ich hab bisher noch nie fremden Quellcode analysiert.

Horst_H · Verfasst: Sa 19.05.07 13:55

Hallo,

Grishnak's Version sollte Dir nur eine andere Vorgehensweise zeigen.
Die Du vorgeschlagen hast funktioniert doch auch, aber manchmal hat man ein Brett vorm Kopf und kann die Ideen anderer ( mit dem entsprechendem Aha-Erlebnis)dann nutzen.

Gruß Horst

MrMister · Hält's aus hier Beiträge: 12

Ah, ok, sorry für das kleine Missverständnis

Habe mir den Quellcode angeschaut und auch einiges verstanden, aber vieles ist einfach noch über meinem Niveau und mir fehlt leider die Zeit, mich komplett damit auseinanderzusetzen, weil ich ein wenig unter Zeitdruck stehe (Schulprojekt halt -.-). Aber ich werde mir das Ding auf jeden Fall komplett anschauen, sobald ich die Zeit habe und versuchen so viel wie möglich daraus zu lernen

Danke schonmal für deinen Rat, ich hoffe ich kriege jetzt die Bananen-Joe-Version irgendwie zusammengebastelt

Liebe Grüße,
MrMister

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme