Sudoku backtraking – Pascal – Fórum – Programujte.com

Zdravim a prosím o radu. Dělám program, který by měl vygenerovat kompletní sudoku (neřeší zadané, ale do prázdného pole 9x9 nahází podle pravidel sudoku čísla).

Důležitou pomůcku tvoří seznam povolených hodnot pro konkrétní políčko, čísla 1..9
Chtěl bych to řešit rekurzí, volá se po políčkách:

1. Zkontroluju jestli zbývá nějaká povolená hodnota. Pokud ano : goto 2. Jinak: dopolním povolené hodnoty na 1..9 a vrátím se o políčko zpět.
2. Náhodně vyberu číslo ze seznamu potenciálních hodnot.
3. Zkontroluju jestli tato hodnota na tomto políčku netvoří kolizi s pravidly. Netvoří kolizi : goto 4, jinak goto5
4. Je-li vše v pořádku, hodnotu použiju a vyškrtnu ji ze seznamu povolených hodnot pro toto políčko. Zavolám fci znova pro další políčko
5. Tvoří-li kolizi, políčko vyškrtnu ze seznamu povolených hodnot a goto 1.

To je tedy hlavní myšlenka, které jsem se snažil držet při tvoření následujícího kódu. Po prvním zpuštění, mi opravdu vytvořil pole čísel 9x9, které odpovídalo pravidlům sudoku. Z mně nepochopitelných důvodů - asi jsem musel něco omylem změnit - při každém dalším pokusu většinou vplní pouze pár řádků/sloupců a ve zbytku zůstanou nuly. Nejsem schopen najít chybu, zvláště když už mám opravdu jedno řešení hotové...

program generujsudoku;

uses Crt;

var
   radek,sloupec,k,e,i,j,q,s,x1c,x2c,y1c,y2c: integer; {x - radek, y - sloupec}
   sudoku : array [1..9,1..9] of 1..9;
   kandidatipolicko : array [1..10] of 0..9;
   znova,hotovo,backtrack : boolean;
   reseni : text;

function muzes(x,y,s : integer): boolean;
begin
     muzes := true;
     {kotrola sloupce}
     for radek := 1 to 9 do
     begin
          if s = sudoku[radek,y] then
          begin
               muzes := false;
          end;
     end;
     for sloupec := 1 to 9 do
     begin
          if s = sudoku[x,sloupec] then
          begin
               muzes := false;
          end;
     end;
     {kontrola ctverecku}
     case x of
     1..3 : begin x1c := 1; x2c := 3; end;
     4..6 : begin x1c := 4; x2c := 6; end;
     7..9 : begin x1c := 7; x2c := 9; end;
     end;
     case y of
     1,2,3 : begin y1c := 1; y2c := 3; end;
     4,5,6 : begin y1c := 4; y2c := 6; end;
     7,8,9 : begin y1c := 7; y2c := 9; end;
     end;
     for radek := x1c to x2c do
     begin
          for sloupec := y1c to y2c do
          begin
               if s = sudoku[radek,sloupec] then
               begin
                    muzes := false;
                    {break;}
               end;
          end;
     end;
end;

function generujcislo(x,y,maxi:integer): integer;
begin
     if maxi> 1 then
     begin
          e := 0;
          while (e = 0) do e := random(maxi+1);
          generujcislo := kandidatipolicko[e];
     end else generujcislo := kandidatipolicko[1];

end;

procedure generuj(x,y : integer);
var
   kanpol : array [1..10] of 0..9;
begin
     for i := 1 to 9 do begin kanpol[i] := i; end;
     kanpol[10] := 9;
     znova := true;
     while znova do
     begin
          if kanpol[1] <> 0 then {dosli kandidati?}
          begin {ne}
               for i := 1 to 10 do begin kandidatipolicko[i] := kanpol[i]; end;
               s := generujcislo(x,y,kandidatipolicko[10]);
               if muzes(x,y,s) then
               begin
                    sudoku[x,y] := s;
                    for k := e to kanpol[10]-1 do   {zakaz policko}
                    begin
                         kanpol[k] := kanpol[k+1];
                    end;
                    kanpol[kanpol[10]] := 0; {zbytek 0}
                    kanpol[10] := kanpol[10]-1; {pocet moznych se snizi}
                    znova := false;
                    if x < 9 then
                         generuj(x+1,y)
                    else                   {jinak je konec radku}
                    begin
                         if y < 9 then generuj(1,y+1);
                    end;
               end else
               begin
                    for k := e to kanpol[10]-1 do   {zakaz policko}
                    begin
                         kanpol[k] := kanpol[k+1];
                    end;
                    kanpol[kanpol[10]] := 0; {zbytek 0}
                    kanpol[10] := kanpol[10]-1; {pocet moznych se snizi}
                    znova := true;
               end;

          end else znova := false;
     end;
     if (sudoku[9,9] <> 0) then
     begin
     assign(reseni,'reseni.txt');
     rewrite(reseni);
     for radek := 1 to 9 do
     begin
          for sloupec := 1 to 9 do
          begin
               write(reseni,sudoku[radek,sloupec],' ');
          end;
          writeln(reseni);
     end;
     close(reseni);
     end;
end;

begin
     randomize;
     generuj(1,1);
end.