Sudoku backtraking – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
16. 2. 2014   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 109.80.85.–
Reklama
Reklama
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 18 hostů

Podobná vlákna

Backtraking funkčnost — založil alpha

Sudoku X — založil Epoxi

VB Sudoku v konzoli — založil Vili

Diagonální sudoku II — založil Epoxi

SuDoku v Jave — založil whatto

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý