Warum geht mein Backtracking für 9x9 aber nicht für 16x16 oder 25x25?

[alfware17]

Hallo, wie immer steckt der Teufel im Detail und ich konnte außer Delphi installieren und 2 Beispiele anschauen (die auch laufen), noch nicht viel anfangen mit dem GUI. Weil mich mein Konsolenprogramm noch ärgert. Kurz zur Erklärung, es ist mal entstanden als Programm in C, C++, Fortran und Ada, einfach nur um MingW zu spielen.
In C habe ich es dann erweitert auf 16x16 und 25x25 - leider scheint da eine Macke im Algorithmus. Mein PC wird ja wohl genug Rechenleistung haben. I
Zwischenzeitlich hatte ich es nach Java portiert, nur zangsweise und schlampig etwas OO, weil meine Moduleinteilung aus C so nicht durch ging (wechselweise Imports). Aus dem Java dann wieder zurück nach Pascal, also bitte nicht meckern über OO oder Stil, es ist nur ein Testprogramm auf dem Weg zum GUI

Hier mein Berechnungscode, in der Anlage das komplette Projekt:

Code: Alles auswählen

unit Strategie;

interface

uses Standard;

function SolveSudokuBackTracking(var Grid: TGrid; Debug: Boolean): Boolean;
function IsValidGrid(var Grid: TGrid; Debug: Boolean): Boolean;
function IsSafe(var Grid: TGrid; Row, Col: Integer; Symbol: Char;  Debug: Boolean): Boolean;

implementation

const analyse = false;

function IsValidGrid(var Grid: TGrid; Debug: Boolean): Boolean;
var
   Row, Col: Integer;
   Symbol: Char;
begin
   for Row := 0 to SIZE-1 do begin
      for Col := 0 to SIZE-1 do begin
         Symbol := Grid[Row, Col];
         if Symbol <> LEER then begin
            Grid[Row, Col] := LEER;
            if not IsSafe(Grid, Row, Col, Symbol, Debug) then begin
               Grid[Row, Col] := Symbol;
               IsValidGrid := False;
               Exit;
            end;
            Grid[Row, Col] := Symbol;
         end;
      end;
   end;
   IsValidGrid := True;
end;

function IsSafe(var Grid: TGrid; Row, Col: Integer; Symbol: Char;  Debug: Boolean): Boolean;
var 
   StartRow, StartCol, x, i, j: Integer;
begin
   for x := 0 to SIZE-1 do begin
      if Grid[Row, x] = Symbol then begin
         if Debug then
            Writeln('Symbol ', Symbol, ' found in Col (', Row, ',', x, ')');
         IsSafe := False;
         Exit;
      end;
      if Grid[x, Col] = Symbol then begin
         if Debug then
            Writeln('Symbol ', Symbol, ' found in Row (', x, ',', Col, ')');
         IsSafe := False;
         Exit;
      end;
   end;
   StartRow := Row - (Row  mod  Grid345); StartCol := Col - (Col  mod Grid345);
   for i:= 0 to Grid345-1 do begin
      for j:=0 to Grid345-1 do begin
          if Grid[i + StartRow, j + StartCol] = Symbol then begin
             if Debug then
                Writeln('Symbol ', Symbol, ' found in ', Grid345, 'x', Grid345, ' (', i + StartRow, ',', j + StartCol, ')');
             IsSafe := False;
             Exit;
          end;
      end;
   end;
   IsSafe := True;
end;

function SolveSudokuBackTracking(var Grid: TGrid; Debug: Boolean): Boolean;
var
   Row, Col, Valid, i: Integer;
   Symbol: Char;
   IsEmpty: Boolean;
begin
   IsEmpty := True;
   Valid := HasValidInGrid(Grid);
   if Valid > MaxValid then begin
      MaxValid := Valid;
      if Debug then
         PrintGrid(Grid, True, False);
   end;
   
   for Row := 0 to SIZE-1 do begin
      for Col := 0 to SIZE-1 do begin
         if Grid[Row, Col] = LEER then begin
            IsEmpty := False;
            Break;
         end;
      end;
      if not IsEmpty then
         Break;
   end;

   if IsEmpty then begin
      SolveSudokuBackTracking := True;
      Exit;
   end;

   for i := 1 to Length(allowedSymbols) do begin
      Symbol := allowedSymbols[i];
      if IsSafe(Grid, Row, Col, Symbol, False) then begin
         Grid[Row, Col] := Symbol;
         if Analyse then begin
            Writeln('Try ', Symbol, ' on Position (', Row, ',', Col, ')');
            PrintGrid(Grid, True, False);
         end;
 
         if SolveSudokuBackTracking(Grid, Debug) then begin
            SolveSudokuBackTracking := True;
            Exit;
         end;
         
         Grid[Row, Col] := LEER;
         if Analyse then begin
            Writeln('BackTracking ', Symbol, ' on Position (', Row, ',', Col, ')');
            PrintGrid(Grid, True, False);
         end;
      end;
   end;

   SolveSudokuBackTracking := False;
end;

end.

Ein Aufruf für 9x9 wäre zB
sudoku sudoku9a.txt loesung.txt 9 x

Ein Aufruf für 16x16 wäre zB
sudoku sudoku16a.txt loesung.txt 16 x

Das 9x9 wird gelöst, das 16x16 bleibt leider bei ca 240/256 "hängen" vermutlich hat sich das Backtracking festgelaufen. So schwierig wird das doch nicht sein oder? Ich habe extra welche mit Lösungen von einer solchen
Sudoku-Seite genommen.

[kralle]

Moin,

liegt der Fehler vielleicht nicht im obigen Teil, sondern in der Interpretation der Aufrufparameter?
Interpretierst Du vielleicht nur eine Stelle vor und nach dem 'x',
So daß aus 16x16 ein 1xx wird und aus dem 25x25, ein 2xx?

Nur so eine Idee?

Gruß kralle

[alfware17]

die 16 ist als SIZE schon angekommen, das Brett wird ja auch ausgegeben. Nur frißt sich der Backtracking Algorithmus fest. Übrigens auch bei anderen Testdaten. Nun ist die Aufgabe bei 16x16 zwar etwas schwerer als bei 9x9 wo es in ms geht, aber nicht sooooo viel schwerer oder doch?

[martin_frb]

Mal schauen... Ich hab den Kode nur oberflächlich gelesen, aber wenn ich richtig liege, probierst Du alle Kombinationen.... Bis zu einem Treffer.

Im schlimmsten Fall, wenn der Treffer die letzte Kombi ist:

81 Felder: 9 Werte im erstem, multipliziert mit 9 Werte im 2ten, .... => 9 hoch 81 = 1.96e77

Für 16 256 hoch 16 = 1.79e308
Das ist 9.1e320 mal mehr....

Das kann dauern, wenn der erste Treffer nicht sofort kommt.