Staonův svět - Rozestavení dam na šachovnici

Dneska jsem úspěšně dokončil první zkouškové období na Matfyzu :) Napsal jsem zápočtový test z Programování.

Osobně jsem si vytáhl celkem jednoduchou úlohu, převod permutace na její index v lexikograficky seřazeném seznamu permutací. Ostatní měli většinou složitější příklady, ale stejně mě celkem dost překvapilo, jak s tím někdy měli problémy. Takže jsem si večer doma zkusil jednu z těch složitějších úloh udělat a zde nabízím své řešení.

Zadáním je rozmístit n dam na šachovnici o rozměrech n x n tak, aby se navzájem neohrožovaly.

  1. const
  2.   MAX_N = 20;
  3.  
  4. type
  5.   OPozice = record
  6.     x, y: integer;
  7.   end;
  8.  
  9.   ODamy = array[0..MAX_N - 1] of integer;
  10.  
  11. var
  12.   { -- priznaky pouziti sloupcu, radek a diagonal }
  13.   radky, sloupce: array[0..MAX_N - 1] of boolean;
  14.   ldiag, rdiag: array[0..MAX_N * 2 - 1] of boolean;
  15.  
  16.   pocet: integer;
  17.  
  18. procedure initFlags(n: integer);
  19. var
  20.   i: integer;
  21. begin
  22.   for i := 0 to n - 1 do
  23.   begin
  24.     radky[i] := FALSE; sloupce[i] := FALSE;
  25.     ldiag[i] := FALSE; rdiag[i] := FALSE;
  26.   end;
  27.   for i := n to n * 2 - 1 do
  28.   begin
  29.     ldiag[i] := FALSE; rdiag[i] := FALSE;
  30.   end;
  31. end;
  32.  
  33. procedure setFlags(x, y, n: integer; value: boolean);
  34. begin
  35.   radky[y] := value; sloupce[x] := value;
  36.   ldiag[x + y] := value; rdiag[(n - 1 - x) + y] := value;
  37. end;
  38.  
  39. function checkFlags(x, y, n: integer): boolean;
  40. begin
  41.   checkFlags := radky[y] or sloupce[x] or ldiag[x + y] or rdiag[(n - 1 - x) + y];
  42. end;
  43.  
  44. procedure printState(var damy: ODamy; n: integer);
  45. var
  46.   x, y: integer;
  47. begin
  48.   for y := 0 to n - 1 do
  49.   begin
  50.     for x := 0 to damy[y] - 1 do write('*');
  51.     write('O');
  52.     for x := damy[y] + 1 to n - 1 do write('*');
  53.     writeln;
  54.   end;
  55.   writeln('=====================');
  56. end;
  57.  
  58. procedure backtrackStep(var damy: ODamy; radka, n: integer);
  59. var
  60.   x: integer;
  61. begin
  62.   if radka >= n then
  63.   begin
  64.     printState(damy, n);
  65.     inc(pocet);
  66.   end
  67.   else
  68.   begin
  69.     for x := 0 to n - 1 do
  70.     begin
  71.       if not checkFlags(x, radka, n) then
  72.       begin
  73.         setFlags(x, radka, n, TRUE);
  74.         damy[radka] := x;
  75.         backtrackStep(damy, radka + 1, n);
  76.         setFlags(x, radka, n, FALSE);
  77.       end;
  78.     end;
  79.   end;
  80. end;
  81.  
  82. procedure main;
  83. var
  84.   damy: ODamy;
  85.   n: integer;
  86. begin
  87.   { -- nactu velikost sachovnice }
  88.   readln(n);
  89.  
  90.   { -- zinicializuji priznaky }
  91.   initFlags(n);
  92.   pocet := 0;
  93.  
  94.   { -- vyvolam backtrack }
  95.   backtrackStep(damy, 0, n);
  96.  
  97.   writeln('Celkem ', pocet, ' moznosti.');
  98. end;
  99.  
  100. begin
  101.   main;
  102. end.

Tak to by bylo vše. Očísloval jsem si řádky, sloupce a oba druhy diagonál. Pro všechny čtyři potom mám čtyři boolská pole, do kterých vyplňuji, zda už jsou ohrožená nějakou dámou, nebo ne. Odpadá tím tak nějaké „vybarvování“ šachovnice. Backtracking dělám po řádkách, aby se mi pak dobře tisknul výstup. Program najde všechny možnosti, jak mohou být dámy rozestavěné.

Pokud by se v tom náhodou někdo šťoural a našel chybu, nechť se ozve. Moc času jsem tomu nevěnoval.

Staon | 6.2.2006 Po 20:47 | <<< trvalý odkaz >>> | tisk | 3 komentáře

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
Jimi mejl web 6.2.2006 Po 21:03

Clovece, zacinam si cim dalej tym viac mysliet, ze ty na tento svet prosto nepatris. Vsade sami flakaci a ludia, co sa snazia zo vsetkych povinnosti co najjednoduchsie vyvliect (pricom ja by som smelo mohol byt ich vodcom :D ) a ty si robis pracu navyse. Nezostava mi nic ine, len ti gratulovat ;-) Sam dobre viem, ze prekonat lenivost je nielen ze tym najtazsim co od seba mozem pozadovat, ale zostava to aj mojim nikdy nesplnenym zelanim. Len tak dalej ;-)

[2] reaguj
miira web 6.2.2006 Po 21:51

Myslím, že Jimi to řekl velice pěkně a výstižně :]

[3] reaguj
Staon mejl web 6.2.2006 Po 22:39

No, na vás dva jsem čekal! Já mám takovou radost, že se občas dokopu k nějaké činnosti a vy dva mi to ještě vyčtete… :-D

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Matfyz je sbírka čeho?
Odpověd: naprostých cvoků malých červených kulatých kostiček

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).