Chaos im array - ich seh den Wald vor lauter Bäumen nimmer

area6 · Verfasst: Fr 09.09.05 21:34

Hallo ihr Lieben!!!

Sooo, nachdem ich für ein paar Jahre nicht da war bin ich erneut vom delphi-Fieber gepackt worden und hab mir direkt mal was vorgenommen, das zu programmieren scheinbar ganz leicht war, jedoch kommt mir das alles etwas spanisch vor, was ich da fabriziert habe ...

Ziel ist eine Anwendung, die ein sudoku (dürfte ja heutzutage gemeinhin bekannt sein) generiert. Auch wenn die entsprechenden Elemente schon vorhanden sind, geht es im folgenden code-Abschnitt ausschliesslich um das Generieren eines vollständigen sudokus, nicht um einen solver oder eine procedure zur Ermittlung eines Minimums an gegebenen Ziffern, die aus dem generierten sudoku ein lösbares Rätsel machen sollen.

Also, NUR das Generieren eines großen Quadranten von 9 kleinen Quadranten a 9 ungleichen Ziffern von 1 bis 9, in dem jede Zeile und jede Spalte 9 ungleiche Ziffern von 1 bis 9 enthält.

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:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:

var

  Form1: TForm1;
  randomx, zaehler, k, zufallsz: integer;
  matrix: array [1..9,1..9,1..9] of integer;
  exist: boolean;


implementation


{$R *.dfm}


procedure TForm1.FormCreate(Sender: TObject);
begin
  randomize;
end;


procedure kzuweisung (i, j: integer);

  begin
    if ((i=1) or (i=4) or (i=7))
      then
        begin
          if ((j=1) or (j=4) or (j=7)) then k:= 1;
          if ((j=2) or (j=5) or (j=8)) then k:= 2;
          if ((j=3) or (j=6) or (j=9)) then k:= 3;
        end
      else if ((i=2) or (i=5) or (i=8))
        then
          begin
            if ((j=1) or (j=4) or (j=7)) then k:= 4;
            if ((j=2) or (j=5) or (j=8)) then k:= 5;
            if ((j=3) or (j=6) or (j=9)) then k:= 6;
          end
        else if ((i=3) or (i=5) or (i=9))
          then
            begin
              if ((j=1) or (j=4) or (j=7)) then k:= 7;
              if ((j=2) or (j=5) or (j=8)) then k:= 8;
              if ((j=3) or (j=6) or (j=9)) then k:= 9;
            end
  end;


procedure existenzpruefung (i, j, zufallsz: integer);

var m, n, o: integer;

  begin
    m:= i;
    n:= j;
    o:= k;
    for m:=1 to 9 do
      begin
        for n:=1 to 9 do
      begin
         for o:=1 to 9 do
      begin
        if matrix[i,j,k]=zufallsz
                    then
      begin
        exist:=true;
        break;

      end
                    else
      exist:=false;
      end;
      end;
  end;
  end;



procedure zufallswert (i, j: integer);

  begin
    exist:= true;
    repeat
  randomx:= 9- zaehler;
  zufallsz:= random(randomx)+1;
  existenzpruefung(i, j, zufallsz);
    if exist=true
    then
      begin
      repeat
          if zufallsz > 9
          then zufallsz:=1
          else
            begin
            zufallsz:= zufallsz + 1;
            exit;
            end;
        until
          exist=false;
        end;          
    until
      exist=false;
  end;


procedure TForm1.Button1Click(Sender: TObject);

var i, j: integer;

  begin
    zaehler:= 0;
    for i:= 1 to 9 do
      begin
        for j:=1 to 9 do
          begin
    (kzuweisung (i, j));
    (zufallswert (i, j));
    matrix[i,j,k]:= zufallsz;
    zaehler:= zaehler + 1;
    if zaehler=9 then zaehler:= 0;
Edit1.Text:= inttostr (matrix[1,1,1]);
          end;
      end;
  end;

Die Ausgabe der Werte in Felder ist noch unvollständig, aber das ist im Moment auch uninteressant und ja auch gar nicht das Problem

Denn eigentlich ist das Problem nun, daß ich teilweise Nullen ausgegeben bekomme, die wohl aus der k-Zuweisung stammen, denn bei der Ausgabe des array muss ich ja relativ umständlich die Position angeben, umständlich im Sinne von "mir fällt keine geeignete Routine ein". Wobei ich mir allerdings inzwischen nicht mehr so sicher bin woher die Nullen überhaupt kommen. Hat jemand eine Idee, wo da der Haken sein könnte, bzw. ob ich vielleicht einfach irgendwas völlig falsch gemacht habe!?!

Liebe Grüße, Sandra.

Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.

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

Nur um dich richtig zu verstehen:

Du willst 9 kleine Quadranten, die jeweils 9x9 Felder groß sind. In jedem dieser kleinen Quadranten stehen die Zahlen 1..9 so, dass in jeder Zeile/Spalte nur eine Zahl steht.

Einer dieser kleinen Quadranten könnte also so aussehen:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

+---+---+---+---+---+---+---+---+---+
|   |   | 1 |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | 7 |   |   |
+---+---+---+---+---+---+---+---+---+
|   | 4 |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   | 9 |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   | 3 |   |   |   |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   | 6 |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | 8 |   |
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   | 2 |   |   |   |
+---+---+---+---+---+---+---+---+---+

Davon brauchst du dann neun verschiedene!?

area6 · Verfasst: Fr 09.09.05 22:17

Öh nö

Sorry, ich meinte einen großen Quadranten (9x9 Felder), der 9 kleine Quadranten enthält (3x3 Felder), so eine Art Dürer-Quadrat, nur ohne die 15-14 und stattdessen mit Ziffern von 1 bis 9.

Am besten ist es wohl so etwas zu besichtigen:

www.websudoku.com

... ich bin einfach nicht gut im beschreiben ...

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

Also brauchst du ein 9x9 Integer-Array, das jeweils Werte von 1 bis 9 annehmen darf:

markieren

Delphi-Quelltext

1:
2:

type
TSudoku = array[1..9, 1..9] of 1..9;

Darin sollen nun einige zufällige Start-Zahlen eingefügt werden?

area6 · Verfasst: Fr 09.09.05 22:36

OK, schonwieder blöd ausgedrückt.

Nein, ich möchte ein komplettes sudoku schreiben, alle 81 Ziffern generieren. Also eine Ziffer zwischen 1 und 9 zufällig generieren und prüfen, ob sie entweder bereits in der jeweiligen Zeile (i), der jeweiligen Spalte (j) oder in dem jeweiligen "Subquadranten" (k) enthalten ist. Und das step by step für alle 81 Ziffern ... dürfte m.W. den geringsten Rechenaufwand ergeben, jedenfalls weniger, als 81 Ziffern zu generieren und dann erst zu prüfen, ob es gleiche in Zeile, Spalte oder Subquadranten gibt. Dass das array 3d ist, liegt nur daran, daß ich mit einem array arbeiten wollte, also jedenfalls nicht mit sets und auf Existenz in 3 Mengen prüfen muss.

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

Eine Frage und ein Problem!

Frage: Du benötigts doch nur 81 Zahlen (= 9x9) und nicht 729 Zahlen (= 9x9x9)!?

Problem: Ich denke, du kannst nicht einfach nacheinander für alle 81 Zellen, die Zahlen von 1 bis 9 prüfen, denn es könnte doch passieren, dass das - bis dahin unfertige - sudoku überhaupt nicht lösbar ist! Das Programm müsste dann "einen Schritt zurück gehen" und eine andere Möglichkeit probieren!

PS: "array[1..9, 1..9] of 1..9" ist kein Set! Mann kann auch "array[1..9, 1..9] of integer" schreiben, dann könnte das Array aber auch Zahlen beinhalten, die kleiner als 1 bzw. größer als 9 wären.

area6 · Verfasst: Fr 09.09.05 23:03

Ich hab doch nicht behauptet, daß es ein set sei

war nur schonmal vorweggenommen, daß ich dies nicht anzuwenden gedenke, unabhängig davon, wie vorteilhaft es sein möge.

Ich brauche ein array [1..9,1..9,1..9] um die Zeile, die Spalte und den Subquadranten zu prüfen, in der Erzeugung (siehe code) wird dem array an der Stelle k=k nie ein Wert zugewiesen. Dieses 3. dient ausschliesslich der Prüfung, ob die betreffende, soeben generierte Zahl bereits in dem Subquadranten ist, in dem eine Zahl erzeugt wurde, was sich ja nicht innerhalb eines 2d array prüfen lässt ... zumindest nicht ohne viel Schreibarbeit ... die Idee des 3d array ist doch grundsätzlich richtig (???), mir scheint nur irgendwas mit der Zuweisung der einzlenen Werte in die jeweilige array-Position nicht zu stimmen --- Nur was?

Ähm, die kleinen Fehler, wie beispielsweise der Tatsache, daß ich mit dem falschen Zähler auch 10er erzeuge bitte ich vorübergehend zu ignorieren ...

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

Für das prüfen - u.a. des Subquadranten - kann ich dir folgendes anbieten (ungetestet!):

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:

var
  Feld: array[1..9][1..9] of integer;

...

procedure Leeren;
var
  ze, sp: integer;
begin
  for ze:=1 to 9 do
    for sp:=1 to 9 do
      Feld[ze, sp]:=0; // 0 bedeutet, dass die Zelle leer ist!
end;

...

function Teste(Zeile, Spalte, Wert): boolean
var
  ze, sp: integer;
begin
  // erst mal vom Schlimmsten ausgehen
  Result:=false;

  // Zeile prüfen
  for sp:=1 to 9 do
    if Feld[Zeile, sp] = Wert then Exit; // Der Wert steht bereits in der Zeile

  // Spalte prüfen
  for ze:=1 to 9 do
    if Feld[ze, Spalte] = Wert then Exit; // Der Wert steht bereits in der Spalte

  // Subquadranten prüfen
  for ze:=3*(Zeile div 3)+1 to 3*(Zeile div 3)+3 do
    for sp:=3*(Spalte div 3)+1 to 3*(Spalte div 3)+3 do
      if Feld[ze, sp] = Wert then Exit;

  // wenn wir hier ankommen, passt der Wert
  Result:=true;
end;

area6 · Verfasst: Fr 09.09.05 23:53

Dann lass mich halt mal so dumm fragen, ob ich sowas nicht eigentlich schon habe ... ?

Hab jetzt mal meinen vorhandenen source um ein paar Fehler erleichtert und bin grade am kommentieren, werds gleich mal posten ...

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

Ich habe nebenbei selbst ein bischen rumprogrammiert und denke, eine Lösung gefunden zu haben!

Ach ja! Kleine Berichtigung:

markieren

Delphi-Quelltext

1:
2:
3:
4:

  // Subquadranten prüfen
  for ze:=3*((Zeile-1) div 3)+1 to 3*((Zeile-1) div 3)+3 do
    for sp:=3*((Spalte-1) div 3)+1 to 3*((Spalte-1) div 3)+3 do
      if Feld[ze, sp] = Wert then Exit;

area6 · Verfasst: Sa 10.09.05 00:19

Joah, scheint mir das einfachste und soweit läuft es auch fehlerfrei

Bei mir wirds irgendwie nach jeder Berichtigung nur noch schlimmer :wink:

... werd wohl noch ein paar Stündchen basteln gehn ...

Danke!

Bye & Gute Nacht!

Jetstream · Beiträge: 222

du rechnest dann also mit 9-stelligen integern ? wieso ?
mach doch einfach ein 9x9 array aus strings.

markieren

Delphi-Quelltext

1:	EinSolveGrid = array[0..8,0..8] of string;

dann gibts noch eine Funktion um aus einem Feld eine Zahl zu löschen.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

function deleteNumber(s:string,t:char):string;
var a:integer;
begin
  for a:=0 to length(s) do if copy(s,a,1)=t then delete(s,a,1);
  deleteNumber:=s;
end;

und jetzt noch prüfen ob eine Zahl im Feld ist

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

function gotNumber(s:string,t:char):boolean;
var a:integer;
begin
  gotNumber:=false;
  for a:=0 to length(s) do if copy(s,a,1)=t then gotNumber:=true;
end;

Damit müsstest du recht weit kommen.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme