![]() |
Delphi-Version: 6
Sudoku Generator (Anfänge)
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; |
AW: Sudoku Generator (Anfänge)
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ß |
AW: Sudoku Generator (Anfänge)
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 :) |
AW: Sudoku Generator (Anfänge)
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:
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.
1. Reihe: 6 3 2 4 9 5 7 1 8
2. Reihe: 7 4 5 3 6 8 2 9 Da hilft wohl nur ein anderer Ansatz (das or hilft leider auch nix). Gruß |
AW: Sudoku Generator (Anfänge)
Zitat:
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. |
AW: Sudoku Generator (Anfänge)
Hallo,
Lesestoff gibt zum Thema Sudokus generieren / lösen es jede Menge (ein kleiner Auszug): ![]() ![]() ![]() und natürlich auch bei ![]() Gruß |
AW: Sudoku Generator (Anfänge)
Ich dachte es würde so funktionieren, dass, wenn alle Testwerte "durchfallen", das heißt, wenn das Programm nicht mehr weiterkommt, es um eine Zelle zurückgeht und dort eine neue Ziffer einfügt.
Daher auch dieser Teil hier
Code:
da sollte er doch theoretisch wieder eine Zelle zurückgehen, und die von neuem mit einer Zufallszahl füllen, oder nicht?
if not Test then
Col:=Col-1 |
AW: Sudoku Generator (Anfänge)
Hi,
ohne jetzt den Code näher angeschaut zu haben: Wenn für das vorherige Feld nur eine Wahl möglich war, dann wird er doch wieder gleich wählen und du hast das gleich Problem ein Feld weiter nochmal, oder? Viele Grüße, Frederic |
AW: Sudoku Generator (Anfänge)
Hallo,
Zitat:
In meinem Beispiel Zitat:
Gruß |
AW: Sudoku Generator (Anfänge)
Zitat:
Ich hab jetzt einen Array definiert, aus dem er dann die Zahl "ausstreicht" wenn sie einmal benutzt wurde und es nicht weitergeht, und somit geht er dann in dem Fall ein weiteres Feld zurück und probiert dort. Das ganze ist zwar noch nicht 100%ig effizient (dauert schon ne Weile bis er ein Sudoku ausspuckt), aber es funktioniert schonmal, daher mal ein riiiiiesiges Dankeschön für die Hilfe :) |
AW: Sudoku Generator (Anfänge)
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 :oops:
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; |
AW: Sudoku Generator (Anfänge)
Hallo,
Zitat:
Delphi-Quellcode:
Vielleicht erledigt sich dann
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; Zitat:
Gruß |
AW: Sudoku Generator (Anfänge)
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:
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.
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;
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:
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).
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 |
AW: Sudoku Generator (Anfänge)
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 :) |
AW: Sudoku Generator (Anfänge)
Zitat:
Erst wenn das Sudoku erzeugt ist, wird es auf das StringGrid kopiert.
Delphi-Quellcode:
type
// 0 bedeutet Feld ist leer; 1 - 9 entsprechen den Ziffern TSudokuZiffer = 0..9; // 81 Felder TSudokuField = array[1..9, 1..9] of TSudokuZiffer; var sfeld : TSudokuField; procedure CopyToStringgrid(grid:TStrinGrid); begin // kopiere den Inhalt von array "sfeld" in das Stringrid // das lässt sich mit zwei geschachtelten For-Schleifen erledigen end; |
AW: Sudoku Generator (Anfänge)
Hallo,
ich habe mich bis zum heutigen Tag noch nie mit dem Thema Sudoku näher auseinandergesetzt. Ich weiß nur: Es ist eine Anordnung von neun Ziffern verteilt auf neun Blöcke, so dass pro Block, pro Spalte und pro Zeile jede Ziffer nur einmal vorkommt. Zitat:
Zitat:
Gruß |
AW: Sudoku Generator (Anfänge)
Ja, ein Sudoku wird meines Wissens so aufgebaut, dass man es zuerst komplett (und natürlich auch korrekt) auffüllt, und dann eine gewisse Anzahl an zahlen wieder löscht. Dabei muss allerdings die Bedingung erfüllt sein, dass es eindeutig lösbar bleibt (also dass keine 2 verschiedene Lösungen möglich sind). Damit ein Sudoku überhaupt noch lösbar ist, soll es mindestens 17 Ziffern beinhalten.
(Quelle: Wikipedia. Zitiere: "Die Vermutung, dass 17 die minimale Anzahl an vorbelegten Feldern ist, für die ein eindeutig lösbares Rätsel existiert,[10][11] bewies 2011 ein Forschungsteam um Gary McGuire (University College Dublin) mit Hilfe von Computern. Die von ihm programmierte erschöpfende Suche benötigte sieben Millionen Stunden Rechenzeit parallel auf Hunderten von Prozessoren.") Die Procedure IsValid kontrolliert, ob es noch eindeutig lösbar ist. Die Bedingung dafür ist, dass noch mindestens 8 der 9 Ziffern irgendwo im Spiel vertreten sind. (da wenn nachher 2 Ziffern komplett aus dem Spiel raus sind, gibt es 2 mögliche Lösungen, da man beide "vertauschen" könnte) Da ich die Ziffern per Zufallswert rausziehe, und die while Schleife rund 60 Ziffern ausradiert, sollte es ja theoretisch möglich sein, dass z.B. alle 9 Einser und alle 9 Zweier entfernt wurden, und damit IsValid false zurückgeben müsste. @sx2008 Danke :) Dass das Programm die ganze Zeit in meinem StringGrid rumwuselt (und zwischendurch immer SG.Repaint macht) war am Anfang eher zur "grafischen" Darstellung, damit ich meine Fehler leichter finden konnte. Gar nicht daran gedacht, dass ich mittlerweile einen Array benutzen könnte. :oops: Edit: Schon allein das Entfernen des "SG.Repaint" hat dafür gesorgt, dass es jetzt meistens nur noch weniger als eine Sekunde dauert, bis er ein Sudoku ausspuckt. :) |
AW: Sudoku Generator (Anfänge)
Hallo,
ich las gerade eben nochmals meinen letzten Beitrag, und ich muss zugeben dieser war nun wirklich nicht verständlich formuliert. Es tut mir sehr leid, dadurch vielleicht mehr Verwirrung gestiftet, als zu einer Lösung beigetragen zu haben. Mit: Zitat:
Ich habe mich jetzt zwar nicht näher mit Sudokus – und deren Theorie – auseinander gesetzt, aber mit Deinem Thema in einem komplett gefüllten Sudoku Felder auszublenden und dabei die eindeutige Lösbarkeit zu erhalten. Ich hoffe, dass folgender Quellcode verständlich und nachvollziehbar ist. Wenn Fragen bestehen gerne.
Delphi-Quellcode:
type
TSudokuBounds = 0..8; TSudokuDigit = 0..9; TSudokuBoard = array [TSudokuBounds, TSudokuBounds] of TSudokuDigit; TSudokuField = record Col : Byte; Row : Byte; end;
Delphi-Quellcode:
TForm4 = class(TForm)
private FDigitCounter : Byte; FSudokuBoard : TSudokuBoard; procedure ClearRandomFields; function GetRandomFieldNotEmpty : TSudokuField; function IsDefiniteSolvable : Boolean; end;
Delphi-Quellcode:
Gruß
procedure TForm4.ClearRandomFields;
var v : array [TSudokuBounds, TSudokuBounds] of Boolean; f : TSudokuField; t : 1..9; begin FillChar (v, SizeOf (v), Integer (True)); while FDigitCounter > 21 do begin f := GetRandomFieldNotEmpty; if v [f.Col, f.Row] = False then Continue; t := FSudokuBoard [f.Col, f.Row]; FSudokuBoard [f.Col, f.Row] := 0; if IsDefiniteSolvable then Dec (FDigitCounter) else begin FSudokuBoard [f.Col, f.Row] := t; v [f.Col, f.Row] := False end end end; function TForm4.GetRandomFieldNotEmpty : TSudokuField; begin repeat with Result do begin Col := Random (9); Row := Random (9); if FSudokuBoard [Col, Row] <> 0 then Break end until True end; function TForm4.IsDefiniteSolvable : Boolean; var i, n : Byte; c, r : TSudokuBounds; f : Boolean; begin n := 0; for i := 1 to 9 do begin f := False; c := 0; repeat r := 0; repeat if FSudokuBoard [c, r] = i then begin f := True; Inc (n) end; Inc (r) until f or (r = High (TSudokuBounds) + 1); Inc (c) until f or (c = High (TSudokuBounds) + 1) end; Result := n > 8 end; |
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:47 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz