Problem mit Sudoku ähnlichem Programm

[conran]

Hallo Leute,

ich habe mich vor kurzem hier bei euch im Forum angemeldet,
da wir in der Schule nun angefangen haben, einen Sudoku-Generator zu
programmieren und es bei euch dazu ganz interessante Lösungsansätze
gibt.

Nun... Ich wollte sowas lieber selbst versuchen und hab jetzt mal angefang
meinen persönlichen Lösungsansatz zu programmieren.
Ich will allerdings nicht gleich einen fertigen Sudoku-Generator schreiben,
sondern habe jetzt angefangen, ein 9x9 StringGrid mit Zufallszahlen zu füllen.
Das ist ja fürs erste ganz einfach.
Alls nächstes habe ich es soweit geschafft, dass in einer Zeile keine doppelten Zahlen vorkommen.
Jede Zeile wird also mit den Zahlen 1 bis 9 in zufälliger Reihenfolge gefüllt.
Hierauf dachte ich mir, dass das ja auch ganz einfach zu erweitern wäre für die Spalten,
also das in keiner Spalte eine Zahl doppelt vorkommt. Aber weit gefehlt, das Programm will nicht so
wie ich. Begrenze ich die Zeilenanzahl auf beispielsweise 2 bis 4, läufts noch ohne mucken durch.
Sobald es aber das volle 9x9 StringGrid füllen soll, hängt sich das Programm auf, bzw ich
habe 100% CPU Auslastung und nichts tut sich.

Nun kommt ihr an die Reihe. Ich werde hier unter mal meinen Code anhängen und hoffe,
dass ihr mir Tipps oder Anmerkungen geben könnt, was mein Problem ist, wieso es so nicht funktioniert,
und was man eventuell verbessern könnte.
Mir wär dabei am liebsten, wenn man das im Rahmen meiner Delphi-Kenntnisse lassen könnte. Ihr
werdet sehn das ich nur einfache Befehle verwende.

Ich sag schonmal vielen Dank und hoffe das ihr mir helfen könnt, mich ein bischen vom Fleck zu bewegen.
Schönen Gruß, Leo

Delphi-Quellcode:

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    grid: TStringGrid;
    Button1: TButton;
    Edit1: TEdit;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Zahl: array[0..8, 0..8] of integer;

implementation

{$R *.dfm}

function DelArray(): integer;      // Funktion zum löschen des Arrays
var y,x:integer;
begin
  for y:=0 to 8 do
  begin
    for x:=0 to 8 do
    begin
      Zahl[y,x] := 0;
    end;
  end;
end;

function CheckZeile(value: integer; Spalte: integer; Zeile: integer): integer;
var i,x,y: integer;                        // Funktion überprüft, ob Zahl in
begin                                      // betreffender Zeile schon vorkommt
  result := -1;
  for i:=0 to 8 do
  begin
    if Zahl[i,Zeile]=value then
    begin
      result:=1;
      break;
    end;
  end;
end;

function CheckSpalte(value: integer; Spalte: integer; Zeile: integer): integer;
var i,x,y: integer;                        // Funktion überprüft, ob Zahl in
begin                                      // betreffender Spalte schon vorkommt
  result := -1;
  for i:=0 to 8 do
  begin
    if Zahl[Spalte,i]=value then
    begin
      result:=1;
      break;
    end;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);         // Hauptprozedur
var spalte,zeile,rdzahl,b,zaehler,summe,left,i:integer;
begin
  zaehler := 0;             // Zaehler nullsetzen
  DelArray;                 // Array löschen
  for spalte:=0 to 8 do     // spalte 0 bis 8 nacheinander durchgehen
  begin
    for zeile:=0 to 8 do    // in jeder spalte zeile 0 bis 8 durchgehen
    begin
      summe := 0;
      repeat
        if spalte = 8 then begin   // wenn letzte spalte,
          for i:= 0 to 7 do
          begin
          summe := summe+Zahl[i,Zeile];   // summe der zahlen bisher in zeile
          end;                            // ausrechnen
        left := 45-summe;
        rdzahl := left;                  // und daraus die letzte fehlende zahl
        b := -1;                         // bilden
        end else
        begin                              // wenn nicht letzte spalte
        Randomize;
        rdzahl  :=  random(9)+1;              // zufallszahl erzeugen
        b := CheckZeile(rdzahl,spalte,zeile); // überprüfe ob zahl schon in Zeile
        if b=-1 then begin b:= CheckSpalte(rdzahl,spalte,zeile); end; // wenn das nicht der Fall ist
        zaehler := zaehler+1;                                         // überprüfe pb zahl schon in spalte
        Edit1.Text := inttostr(zaehler);      // Zaehler hochzählen und ausgeben
        end;
      until b=-1;    // wenn b=-1 (Zahl also nicht in spalte oder zeile bisher vorhanden, dann..
      Zahl[Spalte,Zeile]  :=  rdzahl;    // erzeugte zufallszahl array zuweisen
      Form1.grid.Cells[Spalte,Zeile]:=inttostr(Zahl[Spalte,Zeile]);   // und ausgeben im STringGrid
    end;
  end;
end;

end.

[marabu]

Herzlich willkommen in der Delphi-PRAXiS, Leo.

Du solltest Randomize nur einmal aufrufen, weil ansonsten der Pseudo-Zufallsgenerator nicht richtig funktioniert.

Wenn du eine Zeile Schritt für Schritt füllst, dann ist es nicht sehr ökonomisch eine beliebige Zufallszahl zu generieren und deren Vorhandensein zu überprüfen. Die mathematische Bedingung ist viel klarer - etwa wie bei einer Lottoziehung. Eine bereits gezogene Zahl kann nicht nochmal gezogen werden, weil sie ja aus der Ziehungsmenge verschwindet. Das solltest du nachbilden.

Ein Algorithmus für das Befüllen eines 9er Quadrats könnte so aussehen:

Das Kästchen mit der Spalten-Zeilen-Koordinate [0,0] befindet sich links oben.
Wir definieren die Grundmenge G als die Menge der Ziffern 1 bis 9. Sei die Vorratsmenge VD gleich G. Sei s der Spaltenindex und z der Zeilenindex. Für jedes Kästchen [s,z] mit s = z (Diagonale), für steigendes s, entnehmen wir der Vorratsmenge VD ein beliebiges Element und tragen es in das Kästchen [s,z] ein. Nach der Eintragung ist für die Spalte s eine Vorratsmenge VS als die Differenz von Grundmenge G und der Menge der bereits eingetragen Ziffern Ss definiert. Für das schrittweise Auffüllen der noch nicht gefüllten Kästchen [s,z] in der Spalte s wird jetzt jeweils die Vorratsmenge V als Differenz der Menge VS und der Menge Zz für alle z > s gebildet, wobei Zz wieder die Menge der bereits eingetragen Ziffern in der Zeile z darstellt. Analoges gilt für das Auffüllen der Spalte z.

Mit dem Eintragen der letzten Ziffer auf der Diagonalen ist das 9er Quadrat so gefüllt, dass in keiner Spalte oder Zeile doppelte Werte zu finden sind. Leider bist du dann noch nicht fertig, da für ein 9er Sudoku eine weitere Bedingung eingehalten werden muss, aber bereits die korrekte und elegante Implementierung des von mir angegebenen Algorithmus ist ja schon eine schöne Aufgabe.

Mein Algorithmus ist nicht der einzig mögliche. Egal wie du jetzt vorgehen willst - viel Spaß.

Freundliche Grüße vom marabu

[conran]

Hallo Marabu,

danke für deinen Lösungsansatz. Klingt schonmal nicht schlecht.
Vielen Dank für deine Tipps, ich werd mich mal dran versuchen.

Gerne nehme ich natürlich noch weitere Vorschläge/Tipps/etc entgegen.


Schöne Grüße, Leo

[Grishnak]

Ich bin der Meinung, dass durch rein zufälliges Füllen es relativ leicht passiert, dass für eine bestimmte Zelle keine Möglichkeit besteht, diese zu füllen; d.h. es kommen bereits alle Zahlen von 1 bis 9 in der Zeile, Spalte bzw. Unterquadrat vor. Aus diesem Grund bleibt dein Programm wahrscheinlich auch hängen!

Weiterhing bin ich der Meinung, dass ein solches Unterfangen ohne Back-Trac(k)ing überhaupt nicht möglich. Sobald dein (Zufalls-)Algorithmus an eine Stelle kommt, für die keine Zahl mehr möglich ist, muss er einen Schritt zurück (auf die vorherige Zelle) gehen und dort eine andere Zahl eintragen. Sollte es für diese Zelle keine andere mögliche Zahl gehen, muss wiederum ein Schritt zurückgegangen werden usw. Ein solches Vorgehen dürfte aber sehr rechenintensiv und langwierig sein.

Sollte der Algorithmus ein widerspruchsfreies Sudoku gefunden haben, wie geht es dann weiter? Schließlich sind ja alle 9x9 Felder nun gefüllt? Wie willst du von diesem aus zu einem 9x9-Gitter kommen, in dem nur einige Zahlen drinstehen, mittels denen man das Sudoku eindeutig lösen kann (es darf schließlich nur genau eine Lösung existieren!)?

Ich habe mir selbst einen Sudoku-Löser und darauf aufbauend einen Sudoku-Generator geschrieben. Wenn es dich interessiert, kann ich dir gerne genauer erklären, wie ich vorgegangen bin!

[conran]

Hallo Grishnack,

auch vielen Dank für deine Antwort.
Ich bin mir bewusst, dass mit meinem Verfahren noch kein Sudoku Löser oder Generator
möglich ist. Es geht mir in diesem Schritt ersteinmal darum, alle Spalten und Zeilen
mit zufälligen, nicht doppelten, Zahlen zu füllen.
Aber natürlich hast du recht, später ist ein Sudoku Generator und Löser angestrebt.
Ich werde die Tage mal die Lösungsmöglichkeit deines Vorredners ausprobieren.

Dein Angebot, mir deine Vorgehensweise zu erklären, freut mich sehr.
Ich habe mir dein Programm schon kurz angesehen, fühlte mich aber fürs erste
leicht erschlagen. Dein Programm gefällt mir vom Funktiomsumfang und von der Umsetzung
super, allerdings denke ich das ich erst einmal kleinere Kekse backen sollte.
Trotzdem, ich würde natürlich gerne wissen, wie du vorgegangen bist.

Schöne Grüße, Leo

[marabu]

Ich habe in meiner Mittagspause versucht meinen Algorithmus zu implementieren und habe dabei festgestellt, dass erstens ein Fehler drin ist (für die Diagonale kann nicht die gleiche Bedingung wie für Zeile, Spalte und Block gelten) und zweitens schon mein erster Versuch ohne backtracking (hallo grishnak) kurz vor dem Ende abbricht.

Da ich heute nicht viel Zeit hatte habe ich dann ein wenig recherchiert und bin über einen ganzen Garten voller Algorithmen gestolpert. Viele sind stumpfsinnig, aber ein paar Hinweise auf genialere Ansätze kamen mir auch unter. Auf jeden Fall muss man sich wohl etwas näher mit der Materie auseinandersetzen. Ich werde mir wohl erstmal ein framework schaffen, bevor ich einen neuen Anlauf unternehme.

Grüße vom marabu

[Grishnak]

@conran & marabu: Komme erst am Montag Abend wieder an meinen Rechner! Dann mehr...

[Grishnak]

...so, wieder da!

@conran&marabu: Was wollt ihr mit eurem jeweiligen Programm bezwecken? Einfach "nur" ein vollständig ausgefülltes Sudoku erstellen?

Nach meiner Meinung, sollte man erst einen Sudoku-Löser erstellen und dann sich an einem Generator versuchen. Der Generator muss ja schließlich irgendwie nachprüfen, ob sich aus den vorgegebenen Zahlen ein komplettes Sudoku errätseln läßt.

[Corpsman]

Hi Ich habe ja nun schon zwei Sudoku Programme geschrieben.

Unter Sudoku könnt ihr diese auch laden.

Ich bin immer so vorgegangen das ich zuerst ein Vollständiges Sudoku erstelle und dann mit hilfe von Optional einschaltbaren lösungstechnicken Versuche per Zufall Zahlen aus dem Fertigen Sudoku zu entfernen und das teil dann gleich wieder zu lösen.

So lange das gelingt lösche ich immer mehr zahlen.

Es gehört natürlich noch ein wenig mehr dazu aber das Prinzip ist so.

Die Vollständigen Sudoku's erhalte ich immer in dem ich via einer Mischung aus Backtracking und Ständigem Berechnen versuche eine Lösung zu finden.

bei Weiteren Fragen gibts auch gerne weitere Erklärungeen