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

Zdrojový text

Pocet sloupcu

const int N = 8;

Jednorozmerne pole pro evidenci dam

int p [N];

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

int cnt = 0;

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 )

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

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

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

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.

     int d = p [s - v];

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.

            if (d == r || d == r-v || d == r+v) 
               ok = false;

Cely test:

        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;
        }

Pozn.: && ok zastavi cyklus, pokud se objevi konflikt … neni nezbytne

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.

    cnt++;
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << " : " << cnt << endl;

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.

            if (s < N - 1)
                place (s + 1);

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.

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;
            }
        }
    }
}

#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; 
}

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 ?

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

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

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