Problém osmi dam

           Problém  osmi  dam  se  řadí  mezi  klasické problémy při výuce
     programování.  A proto  nevidím důvod   proč bychom  se u  něj neměli
     pozastavit i my.

     Zadání:  Rozmístěte  po  šachovnici  osm  dam  tak,  aby  se navzájem
     neohrožovali.   Tzn.   každá   bude   v   jiném   řádku,   sloupci  a
     příčce(=šikmice).

     Algoritmus: Začínám  s čistou šachovnicí.  Na první řádek  do prvního
     sloupce  položím dámu.  Jdu na  další řádek.  Otestuju první políčko.
     je-li ohroženo  přesunu se na  další. Když je  dobrý du zas  na další
     řádku atd. Když se dostanu do  posledního sloupce, jdu o řádek vejš a
     tam se posunu o sloupec doprava.....

     Kdo to pochopil  je dobrej (já sem si to  po sobě přečet a nepochopil
     sem ani ň či jiný písmeno). Pro vás ostatní nakreslim diagram.
     (upozorňuju: nejde o normální diagramy,  ale o moje osobní, který sem
     si teď vymyslel)

                                 +---------+
                                 | začátek |
                                 +----+----+
                    +-----------------+-----------------+
                    | aktuální řádek je 1, sloupec taky |
                    +-----------------+-----------------+
               +----------------------+---------------------+
    ++---------+ kontroluju aktuální políčko je-li ohroženo +-----------+
    ||         +------------+--------------------+----------+           |
    ||               +------+------+     +-------+-------+              |
    ||               | je ohroženo |     | není ohroženo |              |
    ||               +------+------+     +-------+-------+              |
    ||   +------------------+--------+ +---------+-------------------+  |
    ||   | posun na vedlejší políčko | | zaznamenám jdu o řádek dolu |  |
    ||   +---+--------------+--------+ |      na první políčko       |  |
    ||+------+-----++-------+--------+ +------+----------------+-----+  |
    ||| je vedlejší||není-li vedlejší|+-------+--------++------+-------+|
    |||   políčko  ||     políčko    ||není další řádek||je další řádek||
    ||+------+-----++-------+--------+| byl jsem na 8  |+------+-------+|
    |+-------+       +------+-------+ +-------+--------+       +--------+
    |                | o řádek výše | +-------+--------+
    |                | a na políčko ++| vypíšu výsledek|
    |                | za dámou     ||+--------+-------+
    |                ++---------+---++---------+
    |            +----+---+ +---+------+
    |            |je řádek| |není řádek|
    |            |  výše  | |  výše    |
    |            +----+---+ +----+-----+
    +-----------------+       +--+--+
                              |KONEC|
                              +-----+

     Realizace:
      Vstup: Neni
      Uložení  dat:  umístění  dam  na  šachovnici  se  sice dá ukládat do
                     dvojrozměrného pole,  ale protože v 1  řádku může být
                     jen  1 dáma  může se  také uložit  do jednorozměrného
                     o  osmi  prvcích,  kde   pořadí  prvku  určuje  řádek
                     a jeho hodnota sloupec.
      Kontrola ohrožení políčka:

       dá se udělat i takhle
       {testuje je-li policko neohrozene}
       function isclear(ar,ac:byte):boolean;
       var c:byte;
       begin
        c:=0;
        while (c<ar) do
        begin
            {  stejny sloupec or stejna uhlopricka}
            if (chbd[c] = ac) or (abs(ac-chbd[c]) = abs(ar-c)) then begin
                            isclear:=false;
                            exit;
            end;
         inc(c);
        end;
        isclear:=true;
       end;
       Výstup: do souboru (viz. přiložený program)
       Rychlost: program testuje 176585 pozic což by člověku testujícímu 1
                 políčko  za sekundu  trvalo něco  málo pod  5 hodin.  Můj
                 počítač to má asi za 300 milisekund
       Počet řešení: 92, kupodivu se shoduje s literaturou.

            A nyní  už předkládám zmíněné  programy. Jsou ve  dvou versích
     jedna končí na  konci a druhá logicky uprostřed.  Druhá verse je sice
     méně elegantní, ale zase o pár milisekund rychlejší.

     Pro Packalisty: verse 1  verse 2
     Pro Céčkaře   : verse 1  verse 2

                                                                      HIPP
     (použitá literatura:T. Ray Nanney  : Computing a problem-solving with
     Fortran 77)


            výheň