Sudoku Zufallsgenerator mit Anzeige in 9*9 Stringrid

[Delphi-Narr]

Hallo,

da es viel Bedarf nach Sudokugeneratoren gibt, deren Ergebnisse auch in anderen Programmen nutzbar sind, habe ich ein kleines Tool geschrieben, welches ein Sudoku generiert und an ein anderes Programm übergibt.

Die SudokuCreate.Exe in der zip Datei muss nur in das Verzeichnis kopiert werden, in dem sich die aufrufende exe befindet.

Um dann ein Sudoku ins Programm zu laden, muss nur folgender Code eingearbeitet werden:

Delphi-Quellcode:

uses ..., ShellAPI;

//...

type
  TForm1 = class(TForm)
    Button1: TButton;
    StringGrid1: TStringGrid;
    procedure GetSudokuClick(Sender: TObject);
    procedure WMCopyData(var Msg: TWMCopyData); message WM_COPYDATA;  //<- Die Zeile ist wichtig!

//...

var
  Form1: TForm1;
  S:array [0..8] of array [0..8]of integer; 
 {In diesem Array ist später das Sudoku gespeichert, aufgerufen werden die Werte über S[Reihe][Spalte]}

implementation


//Hier werden die empfangenen Daten verarbeitet

procedure TForm1.WMCopyData(var Msg: TWMCopyData);
var x,y,i,j:integer;
    p:string;
begin    
     j:=1;
     p:=string(PChar(Msg.CopyDataStruct.lpData));
     for x:=0 to 8 do
     for y:=0 to 8 do 
     begin
          S[x][y]:=StrToInt(p[j]);
          j:=j+1;
     end;

     for i:=0 to 8 do
         for j:=0 to 8 do
         begin
              Stringgrid1.Cells[j,i]:=IntToStr(S[i][j]);
         end;
end;


procedure TForm1.GetSudokuClick(Sender: TObject);  //Muss aufgerufen werden, wenn man ein Sudoku erstellt haben will
var
  aCopyData: TCopyDataStruct; 
  p: PChar; 
begin
//Falls die Sudokucreate.exe nicht im Programmverzeichnis liegt, muss dies angepasst werden
  winexec(ExtractFilePath(ParamStr(0))+'Sudokucreate.exe', SW_SHOWNORMAL); 

  
  p := PChar('TForm1'); //Der unter type deklarierte Name muss hier eigetragen werden

  with aCopyData do begin
    dwData := 0; 
    cbData := StrLen(p) + 1; 
    lpData := p; 
  end;
 
  // Die Fensterdaten werden an die SudokuCreate.exe übergeben, damit die Daten auch zurückkommen
  SendMessage(FindWindow('TSDokCreate', nil), WM_COPYDATA, Longint(Handle), 
              Longint(@aCopyData)); 

end;

Im Anhang befindet sich sowohl die SudokuCreate.exe alleine (SudokuCreate.zip) und ein Testprogramm, welches den Code zum Aufruf
enthält und anwendet.

Liebe Grüße!

[himitsu]

WinExec

Zitat:

Note This function is provided only for compatibility with 16-bit Windows. Applications should use the CreateProcess function.

(oder eben ShellExecute)

Und noch was zum Code:
Genau für sowas wurden DLLs erfunden.
PS: seit Windows 7 sind messages kein zuverlässiges Kommunikationsmedium, da diese Aufgrund gewisser Sicherheitsmechianismen auch mal verboten/blockiert sein können.

[Delphi-Narr]

Zitat von himitsu:

WinExec

Zitat:

Note This function is provided only for compatibility with 16-bit Windows. Applications should use the CreateProcess function.

(oder eben ShellExecute)

Ich dachte mindestens 16 bit... Bei meinen 32 klappts auch. Aber ich werde dann mal ShellExecute nutzen.
Danke für die Rückmeldung!

[Matze]

Veröffentlichst du noch den Code der Sudokucreate.exe oder wieso ist das in Open-Source?

Open-Source ist es für mich dann, wenn der Code soweit einsehbar ist, dass man theoretisch auch ohne Exe auskommt, sondern den Code direkt im eigenen Programm verwenden kann.

Nachtrag: Habe ich es übersehen oder lässt sich der Schwierigkeitsgrad nicht festlegen? Ohne ist das nicht allzu sinnvoll.

[Delphi-Narr]

Aus einem Sudoku werden eigentlich zufällig Einträge gelöscht.

also dann

Delphi-Quellcode:

var i,x,y:integer;

begin
     randomize; 
     //b ist hier die MAXIMALE Anzahl der gelöschten einträge, da doppelt gelöscht werden kann...
     //S ist ein zweidimensionales Array von integer und beinhaltet das Sudoku
     for i:=0 to b do
     begin
          x:=Random(8);
          y:=Random(8);
          S[x][y]:=0; //Wenn später 0 eingetragen ist, reagieren und das Feld leer lassen...
     end;
end;

Es empfiehlt sich jedoch, vorher eine Kopie von S anzulegen um das Ergebnis hinterger zu prüfen...
Also bei mir gabs bisher keine Probleme, dass Sudoku selbst bei vielen leeren Feldern nicht mehr zu lösen war... Habs bisher immer hingekriegt...

[Tryer]

Zitat von Delphi-Narr:

Also bei mir gabs bisher keine Probleme, dass Sudoku selbst bei vielen leeren Feldern nicht mehr zu lösen war... Habs bisher immer hingekriegt...

Das ist ja garnicht die Frage, selbst (oder gerade wenn) nur eine Zahl eingetragen ist findet man irgendeine Lösung.
Bedingung für ein Sudoku ist aber das es nur eine Lösung gibt.
Wie stellst Du sicher das das generierte Sudoku diese Bedingung erfüllt und es nicht vielleicht zwei Lösungen gibt? Dafür ist vermutlich etwas mehr Analyse notwendig, und in dem Zuge hat man "automatisch" den Schwierigkeitsgrad der sich aus der Komplexität der anzuwendenden Lösungsstrategien ergibt.


Grüsse, Dirk

[Delphi-Narr]

Das von mir erstellte Programm, mit dem ich die Sudokus löse, kann jedoch (bisher) die Sudokus noch nicht so prüfen, dass es die regeln überprüft, sondern vergleicht es nur mit dem generierten.
Ein Sudoku hat bei wenigen Zahlen natürlich mehrere Lösungen. Wenn man irgendwo eine 1 reinschreibt es Billionen von Lösungen. Bei insgesamt
6.670.903.752.021.072.936.960 (also 6,6709 Trilliarden) Möglichkeiten eines 9*9 Sudokus sind Doppellösungen natürlich sehr wahrscheinlich.
Da ich (bisher!) immer auf die "generierte" Lösung hingearbeitet habe, gibt es anscheinend doch nicht so viele verschiedene Möglichkeiten. Denn von Versuch zu Versuch müsste die Wahrscheinlichkeit einer erneuten korrekten/vorgegebenen Lösung rapide (exponential) sinken. Bei je zwei Möglichkeiten hätten wir nach 50 Versuchen eine Wahrscheinlichkeit von 8,8817842 × 10^(-16), also 0,0000000000000088817842 (0,00000000000088817842%), dass alle 50 Versuche auf die vorgegebene Lösung treffen. Und das bei nur je 2 Lösungsmöglichkeiten... Wenn man nicht mehr als bis zu 40 Felder löscht, sollte sich kein Problem ergeben.
Außerdem kommt es doch eigentlich nur darauf an, das Sudoku zu lösen, nicht aber es bestimmt zu lösen...

Zitat:

Die Mindestanzahl vorbelegter Felder zu bestimmen, für die es ein eindeutig lösbares Sudoku gibt, ist ein ungelöstes Problem. Für die Standardvariante ist die kleinste bisher gefundene Anzahl 17.

Liebe Grüße!

[JasonDX]

Zitat von Delphi-Narr:

Wenn man nicht mehr als bis zu 40 Felder löscht, sollte sich kein Problem ergeben.

Ganz im Gegenteil. Als Beispiel ein 2x2-Sudoku:

Code:

xx 34
34 12
43 21
xx 34

Dieses hat bereits 2 verschiedene Lösungen, obwohl fast alle Zahlen eingetragen sind. Natürlich machts für die Lösbarkeit keinen Unterschied (allerhöchstens für die Schwierigkeit), aber zumindest nach eigenem Empfinden ist die Uneindeutigkeit eines Logikpuzzles definitiv spielspaßraubend. Insb. wenn du dann (bisher) nur eine Lösung als richtig anrechnest ist eine solche Situation mindestens suboptimal
Einen effizienten Algorithmus, eindeutige Sudokus zu generieren gibts AFAIK (noch) nicht. Die Holzhammermethode wäre natürlich, alle möglichen Lösungen zu berechnen. Ein anderer Weg wäre, das Sudoku auf Aussagenlogik zurückzuführen und es mit einem Implikationsgraphen zu probieren. Die letzte Möglichkeit die mir einfällt wäre eine Annäherung, d.h. zumindest bestimmte Fälle von mehrfachen Lösungen zu vermeiden. Situationen wie oben im 2x2-Sudoku kann man relativ leicht feststellen und durch hinzufügen einer Zahl lösen. Eine Garantie, dass das Sudoku damit eine eindeutige Lösung hat, ist das definitiv nicht; Aber die für den Spieler (IMO) nervigen Situationen kann man damit eliminieren. (Wenn das Puzzle zwar mehrere Lösungen hat, aber mit einer frühen Entscheidung des Spielers nur eine Lösung möglich ist, merkt der Spieler meist gar nicht, dass es noch andere gäbe).

greetz
Mike