Sudoku Generator (Anfänge)

[sx2008]

Zitat von xyss:

Mittlerweile hab ich den Generator schon wieder etwas mehr verbessert(durchschnittlich ~5 Sekunden für ein Sudoku)

Wenn du ein 9 * 9 Array verwenden würdest, wäre der Code bestimmt 10 Mal schneller als wenn du immer auf dem StringGrid rumreitest.
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;

[Volker Z.]

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:

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

Wenn ich das recht verstehen, dann hast Du also als Ausgangspunkt ein "gültiges Sudoku Spielfeld"!. In Deiner while-Schleife prüfst Du, ob ein gültiges Spielfeld noch immer gültig ist(?) und "radierst" (in Anlehnung in Bjoerg) ein Feld aus; das machst Du solange bis nur mehr 19 Ziffern in einem gültigem Sudoku über bleiben.

Zitat:

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).

Wie soll jetzt ein gültiges Sudoku-Spielfeld plötzlich ungültig werden, wenn mindestens 19 - statt der geforderten 17 - Einträge im Spiel sind?

Gruß

[xyss]

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.

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.

[Volker Z.]

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:

In Deiner while-Schleife prüfst Du, ob ein gültiges Spielfeld noch immer gültig ist(?)

und dem nachfolgenden bezog ich mich auf das, meiner Meinung nach falsche Prüfen der Bedingung IsValid(SG) in der Schleifenbedingung. Und das geht aus meinem Beitrag nun wirklich nicht hervor; sorry dafür.

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:

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;

Gruß