====== Osm dam =====

Metoda hledání s návratem, problém osmi dam (skripta 3.4)


Zadání úlohy: http://cs.wikipedia.org/wiki/Probl%C3%A9m_osmi_dam

[[dama_src|Zdrojový text]]


Pocet sloupcu
<code C++>
const int N = 8;
</code>

Jednorozmerne pole pro evidenci dam
<code C++>
int p [N];
</code>
Prvek pole **p [i]** obsahuje informaci o dame v i-tem slopci: obsahuje cislo radky, kde se nachazi dama. \\
Radky a sloupce cisujeme od 0 (stejne jako indexy poli v jazyce C).

Napr. ** p[0] == 0 ** ... dama a8 ... dama v levem hornim rohu (sloupec s indexem 0, radka s indexem 0) \\
** p[1] == 2 **  ... dama b6 ... dama ve sloupci s indexem 1 (druhy sloupec) je na radku s indexem 2 ( treti radka od shora ) \\


Promenna pocitajici reseni ulohy
<code C++>
int cnt = 0;
</code>

Pro poradek vyplnime pole **p** nedovolenymi hodnotami. \\
A potom zpustime fukci ** place (0) **, ktera ma umistit damu na sloupec 0 ( sloupec **a** na obrazku Wikipedie )

<code C++>
int main()
{
    for (int i = 0; i < N; i++) p[i] = -1;
    place(0);
    std::cout << "O.K." << endl; 
}
</code>

===== Rekurzivní funkce umísťující dámy na jednotlivé sloupce ======

Funkce **place** ma jako parametr cislo sloupce **s**, na ktery budeme damu umistovat. \\
V cyklu pro jednotlive radky **r**, zkusime umistit damu. \\

<code C++>
void place (int s) 
{
    for (int r = 0; r < N; r++) 
    {
       /* ... */
    }
}
</code>


===== Testujeme konflikt =====

Promenna **ok** bude oznacovat, zda damu mohu umistit na sloupec **s** a radku **r**, aniz by doslo ke kolizi s damami ve sloupcich vlevo od sloupce **s**. \\
Nejprve **ok** nastavim na ** true**, tj. zatim neni zadny konflikt.

Pokud bych misto dam pouzival **veže**, staci zkontrolovat sloupce 0, 1, ... s-1, zda neobsahuji cislo **r**.

V pripade dam pouziji promennou **v**, ktera bude predstavovat horizontalni vzdalenost zkoumaneho sloupce od osloupce cislo **s**. 
Pujdu s **v** od **1** do **s**. \\
Pro **v == 1 ** zkoumam predchazejici sloupecc (cislo s-1). \\
Pro **v == s ** zkoumam prvni sloupecc (cislo 0). \\

Do promenne **d** ulozim cislo radky, kde se nachazi dama ve sloupci vzdalenem o **v** od naseho sloupce.
<code C++>
     int d = p [s - v];
</code>
 
Pokud **d == r**, dama ve sloupci **s-v** je na stejnem radku, jako dama ve sloupci **s**. \\
Pokud **d == r-v**, dama ve sloupci **s-v** je na stejne (klesajici) diagonale (vlevo nad nasi damou) , jako dama ve sloupci **s**. \\
Pokud **d == r+v**, dama ve sloupci **s-v** je na stejne diagonale (vlevo pod nasi damou), jako dama ve sloupci **s**. \\
<code C++>
            if (d == r || d == r-v || d == r+v) 
               ok = false;
</code>

Cely test:
<code C++>
        bool ok = true;
        for (int v = 1; v <= s && ok; v++) 
        {
            int d = p[s - v];
            if (d == r || d == r-v ||d == r+v) 
               ok = false;
        }
</code>
Pozn.: **&& ok** zastavi cyklus, pokud se objevi konflikt ... neni nezbytne

===== Pokud konflikt nenastane =====

V promenne **ok** mame vysledek testu, zda lze umistit damu ve  sloupci **s** na radek **r**. \\
( Tento test muze skoncit kladne i pro nekolik hodnot **r**. )

Pokud **ok == true**, ulozime pozici damy do pole: ** p[s] = r; **.

Pokud navic jsme na **poslednim sloupci**, mame **jedno reseni cele ulohy** \\
a vytiskneme cisla radek na kterych se nachazeji damy, \\
pridame za dvojtecku cislo reseni a ukoncime tiskovou radku.
<code C++>
    cnt++;
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << " : " << cnt << endl;
</code>

Pokud **nejsme na poslednim sloupci**, rekurzive zavolame dalsi exemplar funkde **place** tentokrat pro sloupec **s+1**. \\
Nove zavolana funkce bude opet zkouset radky 0, 1, ... N-1. \\
A pokud nebude na poslednim sloupci, zavola dalsi exemplar funkce **place**.

<code C++>
            if (s < N - 1)
                place (s + 1);
</code>

Tedy pokud se nam podari umistit damu ve sloupci **s** na radek **r**, \\
zkousime umistit damy v nasledujicich sloupcich nebo mame jedno reseni.

V kazdem pripade pak pokracuje cyklus pro radky **r**, ktery zkousi umistit damu na dalsi radek.

===== Celá funkce place ======

<code C++>
void place (int s) 
{
    for (int r = 0; r < N; r++) 
    {
        bool ok = true;
        for (int v = 1; v <= s && ok; v++) 
        {
            int d = p [s - v];
            if (d == r || d == r-v || d == r+v) 
               ok = false;
        }
        if (ok) 
        {
            p[s] = r;
            if (s < N - 1)
                place(s + 1);
            else 
            {
                cnt++;
                for (int i = 0; i < N; i++) cout << p[i] << " ";
                cout << " : " << cnt << endl;
            }
        }
    }
}
</code>
 

===== Celý program ======

<code C++>
#include <iostream>
 
using namespace std;
 
const int N = 8;
 
int p [N];
int cnt = 0;
 
void place (int s) 
{
   /* ... */
}
 
int main ()
{
    for (int i = 0; i < N; i++) p[i] = -1;
    place (0);
    cout << "O.K." << endl; 
}
</code>






===== Úkoly =====

a) Upravte program, aby řešil úlohu pro osm věží \\
( Stačí napsat jednu řádku. )

b) Kolik v bude v případě veží řešení ? \\
( Odpověď je na pár znaků klávesnice. Nemusíte program spouštět. )

c) Proč nebude podobná úprava fungovat pro střelce ?

d) Použijme náš algoritmus, ale předpokládejme že se dámy neohrožují. \\
( V každém sloupci smí být jedna dáma, ale ve vedlejším sloupci může být i na stejném řádku další. ) \\
Tedy náš algoritmus, ale **ok** bude stále **true**. \\
Kolik bude variant ? \\
( Otázka odpovídá 9-patrovému stromu. Z kažého vrcholu, který není koncovým listem, vede osm větví. )

e) Uvažujme jiný postup: na každém ze 64 políček šachovnice může být umístěna figurka. \\
Figurky jsou jednoho druhu. \\
Máme k dispozici 64 figurek. \\
(Šachovnice může být například zcela prázdná nebo také zcela zaplněná.) \\
Kolik variant přichází v úvahu ? \\
Pokud na počítači stihneme prozkoumat 4 miliardy variant za sekundu ( nebo 2^32 variant za sekundu ), 
jak dlouho by výpočet trval ?





===== Zobrazení pomocí Qt ======

Jen pro ilustraci, náš algoritmus můžeme použít i v programu s grafickým okénkem.

http://kmlinux.fjfi.cvut.cz/~culikzde/zalg/2020/dama-qt.zip

{{dama:creator-configure.png}}

Metoda **umisti** je obdobou nasi funkce **place**.
Strisknete zeleny trojuhelnik.

{{dama:creator-run.png}}

Stisknete tlacitko "Run" a potom pomoci "scrollbaru" nad sachovnici muzete zobrazovat jednotliva reseni.

{{dama:dama.png}}