Sudoku Generator (Anfänge)

[xyss]

Guten Abend

Auch wenn ich noch relativ neu bin, hab ich mir gedacht, ich Versuch mich mal an einem Sudoku Generator. (vor allem, da ich mich selbst sehr viel mit Sudokus beschäftige) Tragischerweise scheiter ich schon in der ersten Etappe des Programms, nämlich dem kompletten Befüllen eines Sudokufeldes.
Es erscheint jedes Mal ein StackOverflow.
Ob mein Programm jetzt funktionieren würde oder nicht, sei mal dahingestellt, aber was mich stört ist, dass ich nicht draufkomm, woher dieser Stack Overflow herkommt. Wäre also super, wenn mir jemand das erklären könnte

Vielen Dank im Vorraus

Die StringGridDrawCell und ButtonClick Prozeduren hab ich jetzt weggelassen, da diese eigendlich funktionieren Der Buttonclick aktiviert die Prozedur mit (StringGrid1,0,0).

Code:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls;

type
  TfrmMain = class(TForm)
    btnExe: TButton;
    btnExit: TButton;
    StringGrid1: TStringGrid;
    procedure StringGrid1DrawCell(Sender: TObject; ACol, ARow: Integer;
      Rect: TRect; State: TGridDrawState);
    procedure btnExitClick(Sender: TObject);
    function TryNumber(SG:TStringGrid; n,ColPos,RowPos:integer):boolean;
    procedure FillUp(SG:TStringGrid;Col,Row:integer);
    procedure btnExeClick(Sender: TObject);
    procedure TestValues(SG:TStringGrid;Col,Row:integer);
    function IsFilled(SG:TStringGrid):boolean;
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  frmMain: TfrmMain;
  Test:boolean;

implementation

{$R *.dfm}

{**************************************************************}

function TfrmMain.TryNumber(SG:TStringGrid; n,ColPos,RowPos:integer):boolean;
var
  i,j,ColPosCon,RowPosCon:integer;
  verif:boolean;
begin
  verif:=true;

  for i:=0 to SG.ColCount-1 do
    if SG.Cells[i,RowPos]=InttoStr(n) then
      verif:=false;

  for i:=0 to SG.RowCount-1 do
    if SG.Cells[ColPos,i]=InttoStr(n) then
      verif:=false;

  case ColPos of
    0: ColPosCon:=0;
    1: ColPosCon:=0;
    2: ColPosCon:=0;
    3: ColPosCon:=3;
    4: ColPosCon:=3;
    5: ColPosCon:=3;
    6: ColPosCon:=6;
    7: ColPosCon:=6;
    8: ColPosCon:=6;
  end;

  case RowPos of
    0: RowPosCon:=0;
    1: RowPosCon:=0;
    2: RowPosCon:=0;
    3: RowPosCon:=3;
    4: RowPosCon:=3;
    5: RowPosCon:=3;
    6: RowPosCon:=6;
    7: RowPosCon:=6;
    8: RowPosCon:=6;
  end;

  for i:=ColPosCon to ColPosCon+2 do
  begin
    for j:=RowPosCon to RowPosCon+2 do
      if SG.Cells[i,j]=InttoStr(n) then
        verif:=false;
  end;
  result:=verif;
end;

procedure TfrmMain.TestValues(SG:TStringGrid;Col,Row:integer);
var
  n:integer;
begin
  Test:=false;
  for n:=1 to 9 do
  begin
    if (TryNumber(SG,n,Col,Row)=true) and (SG.Cells[Col,Row]='') then
    begin
      Test:=true;
      SG.Cells[Col,Row]:=InttoStr(n);
    end;
  end;
end;


function TfrmMain.IsFilled(SG:TStringGrid):boolean;
var
  Row,Col:integer;
begin
  result:=true;
  for Row:=0 to SG.RowCount-1 do
  begin
    for Col:=0 to SG.ColCount-1 do
    begin
      if SG.Cells[Col,Row]='' then
        result:=false;
    end;
  end;
end;

procedure TfrmMain.FillUp(SG:TStringGrid;Col,Row:integer);
var
  n:integer;
begin
  n:=Random(9)+1;

  if (SG.Cells[Col,Row]<>'') then
  begin
    Col:=Col+1;
  end

  else if (TryNumber(SG,n,Col,Row)=true) and (SG.Cells[Col,Row]='') then
  begin
    SG.Cells[Col,Row]:=InttoStr(n);
    Col:=Col+1;
  end

  else if (TryNumber(SG,n,Col,Row)=false) and (SG.Cells[Col,Row]='') then
  begin
    TestValues(SG,Col,Row);
    if not Test then
      Col:=Col-1
    else if Test then
      Col:=Col+1;
  end;


  if Col<0 then
  begin
    Row:=Row-1;
    Col:=8;
    SG.Cells[Col,Row]:='';
  end;

  if Row<0 then
    Row:=0;

  if Col>8 then
  begin
    Row:=Row+1;
    Col:=0;
  end;


  if IsFilled(SG)=false then FillUp(SG,Col,Row);

end;

[Volker Z.]

Hallo,

vielleicht hast Du es ja schon gefunden. Wenn nicht schau Dir mal die procedure TestValues an. Wenn TryNumber erfüllt ist, wie kann dann die entsprechende Zelle leer sein? Demnach ist die Variable Test ab der zweiten Zeile n-te Spalte False und Dein Programm ruf so lange FillUp(SG,Col,Row) bis es scheppert.

Mach mal ein or draus.

Gruß

[xyss]

Die procedure TestValues soll ja an sich nur für eine spezifische Zelle jede Zahl durchprobieren, wenn die random-Zahl nicht reinpasst. Und daher muss die Zelle ja auch leer sein bevor sie eine Zahl einfüllt (dachte ich mir jedenfalls so). Die FillUp procedure wird ja durch die IsFilled procedure wieder aufgerufen (wenn diese False ergibt). Ich habs mal mit der vorgeschlagenen Änderung versucht, aber leider kommt damit ein anderer Fehler auf. Es kommt zwar kein Stackoverflow mehr, aber dafür wird das Resultat falsch (mit einem or füllt er ja dann eine Zahl ein, wenn entweder die Zelle leer ist, oder die Bedingungen erfüllt sind). Aber das mit dem Stack overflow scheint tatsächlich irgendwie daran zu liegen.

Danke schonmal

[Volker Z.]

Hallo,

in Deiner FillUp-Routine füllst Du das Stringgrid von oben nach unten und von links nach rechts. Dabei ermittelst Du zufällige Werte und prüfst, ob das in die Zeile, Spalte bzw. Block passt. Dieses Vorgehen wird wohl nicht zielführend sein. Beispiel:

Code:

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

Da geht jetzt wohl nur noch SG.Cells[8, 1] = 1, aber das fällt bei der Prüfung durch => FillUp ruft sich solange selbst auf bis der Stackoverflow kommt.

Da hilft wohl nur ein anderer Ansatz (das or hilft leider auch nix).

Gruß

[sx2008]

Zitat von Volker Z.:

Da hilft wohl nur ein anderer Ansatz

Komplettes Sudoku Spielfeld mit ALLEN Zahlen füllen und zwar so dass die Sudoku Regeln erfüllt werden.
Danach zufällig einige Ziffern löschen.

Auf diese Weise kann man dem Spieler später auch die Lösung zeigen, falls das Spiel zu schwer sein sollte.

[Volker Z.]

Hallo,

Lesestoff gibt zum Thema Sudokus generieren / lösen es jede Menge (ein kleiner Auszug):

Sudoku
http://www.planet-source-code.com/vb...=1756&lngWId=7
http://www.entwickler-ecke.de/topic_...l_48160,0.html
und natürlich auch bei
http://www.google.de/search?hl=de&so...aeo4GYBw&gbv=2

Gruß

[xyss]

Mittlerweile hab ich den Generator schon wieder etwas mehr verbessert(durchschnittlich ~5 Sekunden für ein Sudoku) aber meine Prozedur, welche die Zahlen aus dem vollständigen Sudoku herausziehen soll, funktioniert nicht wie sie soll...
Ich hab zum Thema Sudoku ein wenig "nachgeforscht", und es hieß, dass mindestens 7 der 9 Ziffern irgendwo in dem fertigen Sudoku vorhanden sein müssen, und es mindestens 17 Ziffern insgesamt sein müssen (ich hab in dem Fall 20 genommen). Ob noch mindestens 8 der 9 Zahlen im Spiel vorhanden sind, soll von der IsValid function überprüft werden. Und counter (der am Ende meiner FillUp prozedur auf 81 gesetzt wird) soll angeben, wieviele Ziffern sich noch im Sudoku-Spiel befinden.

Nun sind mir allerdings 2 Fehler aufgefallen:

1. IsValid scheint nie false zu sein (oder es war bisher nur Zufall), denn bei all meinen Versuchen hat die while-Schleife dadurch aufgehört, dass Counter zu klein ist.

2. Ich habe den Wert von Counter bei mehreren Versuchen überprüft, und mit dem Feld verglichen, und immer das gleiche Ergebnis: Counter ist 19, wobei sich im Feld noch 30-40 Ziffern befinden.

Erbitte Hilfe

Code:

  while ((IsValid(SG)=true) and (Counter>=20)) do
  begin
    Col:=random(9);
    Row:=random(9);

    temp:=SG.Cells[Col,Row];
    SG.Cells[Col,Row]:='';
    SG.Repaint;
    Counter:=Counter-1;
  end;

Code:

function TfrmMain.IsValid(SG:TStringGrid):boolean;
var
  Col,Row,n,CountNumber,Count:integer;
begin
  result:=true;
  Count:=0;

  for n:=1 to 9 do
  begin
    CountNumber:=0;
    for Col:=0 to 8 do
    begin
      for Row:=0 to 8 do
      begin
        if SG.Cells[Col,Row]=InttoStr(n) then
          inc(CountNumber,1);
      end;
    end;
    if CountNumber<>0 then
      inc(Count,1);
  end;
  if Count<=7 then result:=false;
end;

[Volker Z.]

Hallo,

Zitat:

Ich habe den Wert von Counter bei mehreren Versuchen überprüft, und mit dem Feld verglichen, und immer das gleiche Ergebnis: Counter ist 19, wobei sich im Feld noch 30-40 Ziffern befinden.

Vermutlich liegt es daran, dass beim Schleifendurchlauf die zufällig gewählte Zelle bereits bei einem vorherigen Lauf zurückgesetzt wurde. Versuch mal:

Delphi-Quellcode:

while ((IsValid(SG)=true) and (Counter>=20)) do
  begin
    Col:=random(9);
    Row:=random(9);

    temp := SG.Cells[Col,Row];
    if temp = '' then
      Continue;

    SG.Cells[Col,Row]:='';
    SG.Repaint;
    Counter:=Counter-1;
  end;

Vielleicht erledigt sich dann

Zitat:

IsValid scheint nie false zu sein

von selbst.

Gruß

[Bjoerk]

Daß du dem Algo sozusagen verbietest, vorhandene Werte zu überschreiben, macht ihn unnötig langsam. Entspricht ja auch nicht dem Spielverlauf, man kann Werte ja auch wieder ausradieren und korrigieren. Ich hab’s bei mir so drinne (FRows, FCols, FBoxes: array of TIntegerList):

Delphi-Quellcode:

function TSudoku.CanSetValue(Index, Value: integer): boolean;
var
  Row, Col, I: integer;
begin
  Row := IndexToRowCol(Index).X;
  Col := IndexToRowCol(Index).Y;
  I := RowColToBoxRowCol(Row, Col).X;
  Result := (FRows[Row].IndexOf(Value) < 0)
    and (FCols[Col].IndexOf(Value) < 0)
    and (FBoxes[I].IndexOf(Value) < 0);
end;

Ich finde es auch einfacher, die Schleifen von K:= 0..to 80 laufen zu lassen als von für i:= 0..8, j:= 0..8.

Delphi-Quellcode:

Function TSudoku.IndexToRowCol(Index: integer): TPoint;
begin
  Result.X := Index div 9;
  Result.Y := Index - Result.X * 9;
end;

function TSudoku.RowColToBoxRowCol(Row, Col: integer): TPoint;
begin
  Result.X := Row div 3 mod 3 * 3
    + Col div 3 mod 3;
  Result.Y := Row mod 3 * 3 + Col mod 3;
end;

Delphi-Quellcode:

FBoxes:
0.0  0.1  0.2  1.0  1.1  1.2  2.0  2.1  2.2
0.3  0.4  0.5  1.3  1.4  1.5  2.3  2.4  2.5
0.6  0.7  0.8  1.6  1.7  1.8  2.6  2.7  2.8
3.0  3.1  3.2  4.0  4.1  4.2  5.0  5.1  5.2
3.3  3.4  3.5  4.3  4.4  4.5  5.3  5.4  5.5
3.6  3.7  3.8  4.6  4.7  4.8  5.6  5.7  5.8
6.0  6.1  6.2  7.0  7.1  7.2  8.0  8.1  8.2
6.3  6.4  6.5  7.3  7.4  7.5  8.3  8.4  8.5
6.6  6.7  6.8  7.6  7.7  7.8  8.6  8.7  8.8

Ausgehend davon kann man zufällige Werte für den Index und für die Zahl bestimmen und das ganze solange durchführen bis "SudokuFond" (0,1 sec).

[xyss]

Auch hier schonmal ein großes Danke

Volker Z, dein Vorschlag hat auf jeden Fall das Problem mit dem Count gelöst (Jetzt hat die Variable Count den Wert 19 und es befinden sich auch wirklich 19 Ziffern im Feld), jedoch lief es nach wie vor bei meinen Versuchen darauf hinaus, dass es immer nur durch Count=19 geendet hat, und nicht durch IsValid(SG). Aber vielleicht finde ich ja noch den Fehler