{"nbformat":4,"nbformat_minor":0,"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.6.1"},"colab":{"name":"PB016_cvi2_G02.ipynb","provenance":[],"collapsed_sections":["jOgwiVe6sQZX","8f_nVfr7sQZw","tKFgwwoAsQZ9","_M6J0BS0sQaG"]}},"cells":[{"cell_type":"markdown","metadata":{"id":"6UIjGYX9sQZL"},"source":["# PB016: Umělá inteligence I, cvičení 2 - Prohledávání stavového prostoru\n","\n","Dnešní téma jsou základní prohledávací algoritmy. Soustředit se budeme zejména na:\n","1. __Prohledávání do hloubky__\n","2. __Prohledávání do šířky__\n","3. __Problém N dam__"]},{"cell_type":"markdown","metadata":{"id":"uX6A5PTXsQZN"},"source":["---\n","\n","## 1. Prohledávání do hloubky ([Depth-First Search](https://en.wikipedia.org/wiki/Depth-first_search), zkráceně DFS)\n","\n","__Základní fakta__\n","- Jeden ze základních algoritmů prohledávání stavového prostoru, zpravidla reprezentovaného jako graf (ať už explicitně či implicitně, jako je tomu v případě většiny realistických problémů).\n","- Algoritmus je založen na procházení grafu z jednoho kořenového uzlu.\n","- Prioritně navštěvuje co nejvzdálenější uzly od \"kořene\".\n","- Když není kam jít, vrací se zpět do nejbližšího možného uzlu, z nějž lze prohledávat dále ([backtracking](https://en.wikipedia.org/wiki/Backtracking)).\n","\n","__Pro ilustraci__ - pořadí navštívených uzlů v ukázkovém grafu:\n","\n","![dfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/dfs.png)"]},{"cell_type":"markdown","metadata":{"id":"2RDeB70UsQZN"},"source":["### DFS rekurzivně\n","- Udržujeme seznam navštívených uzlů.\n","- Procházíme seznam sousedů aktálního uzlu a každý nenavštívený rekurzivně prohledáváme dále.\n","\n","Poznámka bokem - pro vytvoření a manipulaci grafu je použita populární knihovna [NetworkX](https://networkx.github.io/documentation/stable/index.html)."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"fy9dSFajsQZO"},"source":["import networkx as nx\n","\n","# vytvoreni grafu z vyse zmineneho prikladu\n","\n","G=nx.Graph()\n","G.add_edges_from([(1,2), (2,3), (3,4), (3,5), (2,6), (1,7), (1,8), (8,9), (9,10), (9,11), (8,12)])\n","\n","# rekurzivni implementace DFS\n","\n","def dfs_recursive(graph,vertex,visited):\n","    visited += [vertex] # aktualizace seznamu navstivenych uzlu\n","\n","    # prochazeni sousednich uzlu (tj. \"potomku\")\n","    for neighbour in graph[vertex]:\n","        if neighbour not in visited: # jdeme hloubeji, pokud uzel jeste nebyl navstiven\n","            visited = dfs_recursive(graph,neighbour,visited)\n","\n","    return visited\n","\n","# vypis prohledavaci cesty z uzlu 1\n","\n","print('DFS rekurzivne - prohledavaci posloupnost z uzlu %d: %s' % (1, dfs_recursive(G,1,[])))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"FffsRcR7sQZT"},"source":["### __Příklad 1.1: Nerekurzivní DFS pomocí zásobníku__\n","- Implementujte nerekurzivní verzi DFS pomocí zásobníku uzlů a jejich sousedů.\n","- Ze zásobníku bereme vždy posledně navštívený uzel a dále prohledáváme jeho dosud nenavštívené sousedy, dokud není zásobník prázdný.\n"," - Pozn.: K implementaci zásobníku stačí prostě seznam, v rámci nějž přidáváme a odebíráme prvky pomocí funkcí `append()`, respektive `pop()`."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"9z9o7CFwsQZU"},"source":["# implementace DFS se zasobnikem\n","\n","def dfs_stack(graph,vertex):\n","    visited = [] # TODO - SAMI DOPLNIT INICIALIZACI ZASOBNIKU SEZNAMU NAVSTIVENYCH UZLU\n","    stack = [] # TODO - SAMI DOPLNIT INICIALIZACI ZASOBNIKU\n","    \n","    # manipulace zasobnikem, dokud neni prazdny\n","    while stack:\n","        # TODO - DOPLNIT SAMI\n","        break # TODO - odstranit ve skutecne implementaci\n","    \n","    return visited\n","            \n","# vypis prohledavaci cesty z uzlu 1\n","\n","print('DFS se zasobnikem - prohledavaci posloupnost z uzlu %d: %s' % (1, dfs_stack(G,1)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"jOgwiVe6sQZX"},"source":["#### __Možné řešení nerekurzivního DFS pomocí zásobníku__"]},{"cell_type":"code","metadata":{"scrolled":false,"id":"6wPS2aDCsQZY"},"source":["# implementace DFS se zasobnikem\n","\n","def dfs_stack(graph,vertex):\n","    visited = [] # inicializace seznamu navstivenych uzlu\n","    stack = [vertex] # inicializace zasobniku\n","\n","    # manipulace zasobnikem, dokud neni prazdny\n","    while stack:\n","\n","        # vyhozeni aktualniho uzlu ze zasobniku\n","        current = stack.pop()\n","\n","        # zarazeni sousednich uzlu, ktere jeste nebyly navstivene, do zasobniku\n","        if current not in visited:\n","            visited.append(current)\n","            for neighbour in graph[current]:\n","                stack.append(neighbour)\n","\n","    return visited\n","            \n","# vypis prohledavaci cesty z uzlu 1\n","\n","print('DFS se zasobnikem - prohledavaci posloupnost z uzlu %d: %s' % (1, dfs_stack(G,1)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"rsiyBNuj-kYr"},"source":["![dfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/dfs.png)"]},{"cell_type":"markdown","metadata":{"id":"6ZsOFRX_sQZb"},"source":["### __Příklad 1.2: Rekurzivní DFS s limitem hloubky__\n","- Implementujte verzi DFS, kde je možno přerušit rekurzivní prohledávání dalších uzlů v dané hloubce (tj. vzdálenosti od kořene vyhledávání)."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"JlQ5JHalsQZc"},"source":["# rekurzivni implementace DFS s limitem (pokud je max_depth==0, prohleda cely graf)\n","\n","def dfs_recursive_limited(graph,vertex,visited,depth,max_depth=0):\n","    visited += [vertex] # aktualizace seznamu navstivenych uzlu\n","    \n","    # TODO - DOPLNIT SAMI\n","    \n","    return visited\n","\n","# vypis prohledavaci cesty z uzlu 1\n","\n","print('DFS rekurzivne - prohledavaci posloupnost z uzlu %d, max. hloubka %d: %s' % (1, 2, dfs_recursive_limited(G,1,[],0,max_depth=2)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"48pyUMtKsQZf"},"source":["#### __Možné řešení rekurzivního DFS s limitem hloubky__"]},{"cell_type":"code","metadata":{"scrolled":false,"id":"oV2hqIbksQZg"},"source":["# rekurzivni implementace DFS s limitem (pokud je max_depth==0, prohleda cely graf)\n","\n","def dfs_recursive_limited(graph,vertex,visited,depth,max_depth=0):\n","    visited += [vertex] # aktualizace seznamu navstivenych uzlu\n","    depth += 1\n","\n","    if max_depth > 0 and depth == max_depth: # kontrola limitu hloubky\n","        return visited\n","\n","    # prochazeni sousednich uzlu (tj. \"potomku\")\n","    for neighbour in graph[vertex]: \n","        if neighbour not in visited: # jdeme hloubeji, pokud uzel jeste nebyl navstiven\n","            visited = dfs_recursive_limited(graph,neighbour,visited,depth,max_depth)\n","\n","    return visited\n","\n","# vypis prohledavaci cesty z uzlu 1\n","\n","print('DFS rekurzivne - prohledavaci posloupnost z uzlu %d, max. hloubka %d: %s' % (1, 2, dfs_recursive_limited(G,1,[],0,max_depth=2)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"Elt8zdvaAC6y"},"source":["![dfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/dfs.png)"]},{"cell_type":"markdown","metadata":{"id":"XZbowTXBsQZs"},"source":["---\n","\n","## 2. Prohledávání do šířky ([Breadth-First Search](https://en.wikipedia.org/wiki/Breadth-first_search), zkráceně BFS)\n","\n","__Základní fakta__\n","- Další ze základních algoritmů prohledávání stavového prostoru reprezentovaného jako graf.\n","- BFS je podobně jako DFS založen na procházení grafu z jednoho kořenového uzlu.\n","- Prioritně ovšem navštěvuje seznam sousedů právě prohledávaného uzlu před přechodem o úroveň níže.\n","\n","__Pro ilustraci__ - pořadí navštívených uzlů v ukázkovém grafu:\n","\n","![bfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/bfs.png)"]},{"cell_type":"markdown","metadata":{"id":"EglJ1pQbsQZt"},"source":["### __Příklad 2.1: BFS - prohledávání do šířky (pomocí fronty)__\n","- Implementujte BFS pomocí fronty.\n","- Udržujte frontu uzlů k prohledání, do níž postupně přidáváte navštívené uzly a jejich sousedy.\n"," - Pozn.: K implementaci obyčejné fronty opět stačí prostý seznam. Prvky přidáváme pomocí funkce `append()` jak u zásobníku, ale odebíráme je tentokrát z čela, tj. začátku seznamu, pomocí `pop(0)`.\n","- Další uzel k prohledání berte z čela fronty, dokud není prázdná."]},{"cell_type":"code","metadata":{"id":"aTtWqagTsQZt"},"source":["# vytvoreni grafu z vyse zmineneho prikladu\n","G=nx.Graph()\n","G.add_edges_from([(1,2), (2,5), (5,9), (5,10), (2,6), (1,3), (1,4), (4,7), (4,8), (7,11), (7,12)])\n","\n","def bfs_queue(graph,vertex):\n","    visited = [] # inicializace seznamu navstivenych uzlu\n","    queue = [] # TODO - SAMI DOPLNIT INICIALIZACI FRONTY\n","\n","    # manipulace frontou dokud neni prazdna\n","    while queue:\n","        # TODO - DOPLNIT SAMI\n","        break # TODO - odstranit ve skutecne implementaci\n","                \n","    return visited\n","\n","# vypis prohledavaci cesty z uzlu 1\n","\n","print('BFS - prohledavaci posloupnost z uzlu %d: %s' % (1, bfs_queue(G,1)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"8f_nVfr7sQZw"},"source":["#### __Možné řešení prohledávání do šířky (pomocí fronty)__"]},{"cell_type":"code","metadata":{"id":"kZg8zjG6sQZx"},"source":["def bfs_queue(graph, vertex):\n","    visited = [] # inicializace seznamu navstivenych uzlu\n","    queue = [vertex] # inicializace fronty\n","\n","    # manipulace frontou dokud neni prazdna\n","    while queue:\n","\n","        # vyhozeni dalsiho uzlu k prozkoumani\n","        next_vertex = queue.pop(0)\n","\n","        # pridani dosud neprozkoumanych sousednich uzlu do fronty\n","        if next_vertex not in visited: \n","            visited.append(next_vertex)\n","            for neighbour in graph[next_vertex]:\n","                queue.append(neighbour)\n","                \n","    return visited\n","\n","# vypis prohledavaci cesty z uzlu 1\n","print('BFS - prohledavaci posloupnost z uzlu %d: %s' % (1, bfs_queue(G,1)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"shmbyQS4G1vF"},"source":["![bfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/bfs.png)"]},{"cell_type":"markdown","metadata":{"id":"zXPg7C9zsQZ0"},"source":["---\n","\n","## 3. Problém N dam (viz. [Eight Queens Puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle))\n","\n","__Základní fakta__\n","- Jeden z klasických problémů v matematice a programování.\n","- Jde o to, rozestavět N dam na NxN šachovnici tak, aby se navzájem neohrožovaly.\n","- Jednoduše definovaný, ale zároveň složitý (tj. \"velký\") problém.\n","\n","| Velikost šachovnice | Počet rozestavění | Celkový počet řešení | Počet unikátních řešení |\n","| ------------------- | ----------------- | -------------------- | ----------------------- |\n","| 1 x 1 \t          | 1                 | 1 \t                 | 1                       |\n","| 2 x 2 \t          | 6                 | 0                    | 0                       |\n","| 3 x 3 \t          | 84                | 0                    | 0                       |\n","| 4 x 4 \t          | 1,820             | 2                    | 1                       |\n","| 5 x 5 \t          | 53,130            | 10                   | 2                       |\n","| 6 x 6 \t          | 1,947,792         | 4                    | 1                       |\n","| 7 x 7 \t          | 85,900,584        | 40                   | 6                       |\n","| 8 x 8 \t          | 4,426,165,368     | 92                   | 12                      |\n","| ...   \t          | ...               | ...                  | ...                     |\n","\n","__Pro ilustraci__ - příklad jednoho z řešení problému 8 dam:\n","\n","![8queens.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/8queens.png)"]},{"cell_type":"markdown","metadata":{"id":"al6-7zmFsQZ1"},"source":["### Naivní \"brute force\" řešení\n","- Generujeme všechny možné kombinace rozestavění dam na šachovnici (pozice).\n","- Kontrolujeme, zda jsou všechny dámy v daném rozestavění v bezpečí. "]},{"cell_type":"code","metadata":{"scrolled":true,"id":"2CQ_8BX_sQZ1"},"source":["import itertools as it # budeme potrebovat pro generovani kombinaci reseni\n","\n","# funkce pro generovani rozestaveni; implicitne se resi problem 8 dam\n","\n","def generate_all_boards(n=8):\n","    # vygenerovani seznamu vsech poli na sachovnici\n","    fields = [(i,j) for i in range(n) for j in range(n)]\n","            \n","    # postupne generovani moznych obsazeni sachovnice damami (tj. seznamy N ruznych obsazenych poli)\n","    for board in it.combinations(fields,n):\n","        yield board\n","        \n","# funkce pro testovani rozestaveni\n","\n","def safe_board(board,n=8):\n","    # prilis mala ci velka sachovnice, automaticky spatne\n","    if len(board) != n:\n","        return False\n","    \n","    # overeni ohrozeni jedne damy po druhe v seznamu pozic\n","    for i in range(n):\n","        x1, y1 = board[i]\n","\n","        # test ohrozeni pouze dalsimi damami v seznamu (predchozi jsou jiz OK)\n","        for x2, y2 in board[i+1:]:\n","            if x1 == x2: # dalsi kralovna ve stejne rade\n","                return False\n","            elif y1 == y2: # dalsi kralovna ve stejnem sloupci\n","                return False\n","            elif x2-x1 == y2-y1: # dalsi kralovna ve stejne primarni diagonale\n","                return False\n","            elif x2-x1 == y1-y2: # dalsi kralovna ve stejne sekundarni diagonale\n","                return False\n","\n","    # zadny test neselhal, damy jsou v bezpeci\n","    return True\n","\n","# pomocna funkce pro zobrazeni pozic dam na sachovnici\n","\n","def print_board(board,n=8):\n","    rows = []\n","    for i in range(n):\n","        column = []\n","        for j in range(n):\n","            if (i,j) in board:\n","                column.append('Q')\n","            else:\n","                column.append('-')\n","        rows.append(' '.join(column))\n","    print('\\n'.join(rows))\n","\n","# pomocna funkce pro vypis vsech reseni\n","\n","def print_brute_force_solutions(n=8):\n","    ok, total, shoutout_step = 0, 0, 10000000\n","    for board in generate_all_boards(n=n):\n","        total += 1\n","        if total % shoutout_step == 0:\n","            print('... otestovano %d moznych rozestaveni ...' % total)\n","        if safe_board(board,n):\n","            ok += 1\n","            print('Bezpecne rozestaveni cislo %d:' % ok)\n","            print_board(board,n)\n","    print('Konec prohledavani: otestovano celkem %d postaveni, nalezeno %d reseni' % (total,ok))\n","\n","# vypis bezpecnych reseni pro N=8\n","\n","print('Generovani bezpecnych rozestaveni 8 dam na sachovnici 8x8 (brute force)')\n","%time print_brute_force_solutions(8) # POZOR - zabere opravdu HODNE casu"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"QocJAgU_sQZ4"},"source":["### __Příklad 3.1: Problém N dam - méně naivní řešení pomocí prohledávání do hloubky, resp. backtrackingu__\n","- Naivní řešení je velice neefektivní.\n","- Nabízí se možné omezení stavového prostoru k prohledání:\n"," - Rekurzivně umisťujeme dámy řadu po řadě tak, aby v každé řadě a v každém sloupci byla jen jedna.\n"," - Rekurze je ukončena v momentě, kdy jsou umístěny všechny dámy.\n"," - Pokud nelze umístit dámu v dané řadě, algoritmus se vrací o řadu výše (backtracking).\n"," - Toto je ekvivalentní procházení grafu možných řešení do hloubky, graf je ovšem v tomto případě jen implicitní, odpovídající struktuře problému.\n","- Pro 8 dam tato strategie redukuje prostor možných řešení na 40,320 rozestavění namísto 4,426,165,368.\n","- Zkuste si toto řešení implementovat."]},{"cell_type":"code","metadata":{"id":"5UmL-9IEsQZ5"},"source":["# pomocna funkce pro otestovani bezpecnosti nove mozne pozice damy vzhledem k ostatnim damam na sachovnici\n","\n","def restricted(board,position):\n","    # TODO - DOPLNIT SAMI (pozn.: board je seznam (x,y) souradnic, position je jedina dvojice, tj. souradnice)\n","    \n","    return True # podminka neporusena, pozice je OK\n","\n","# funkce pro generovani moznych rozestaveni; implicitne se resi problem 8 dam\n","\n","def generate_restricted_boards(board,row,n=8):\n","    # TODO - DOPLNIT SAMI\n","    \n","    yield board # TODO - odstranit ve skutecne implementaci\n","\n","# pomocna funkce pro vypis vsech reseni\n","\n","def print_restricted_search_solutions(n=8):\n","    ok, total = 0, 0\n","    for board in generate_restricted_boards([],0,n=n):\n","        total += 1\n","        if safe_board(board,n):\n","            ok += 1\n","            print('Bezpecne rozestaveni cislo %d:' % ok)\n","            print_board(board,n)\n","    print('Konec prohledavani: otestovano celkem %d postaveni, nalezeno %d reseni' % (total,ok))    \n","                \n","# vypis bezpecnych reseni pro N=8\n","\n","print('Generovani bezpecnych rozestaveni 8 dam na sachovnici 8x8 (omezeni brute-force prohledavani)')\n","%time print_restricted_search_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"tKFgwwoAsQZ9"},"source":["#### __Možné méně naivní řešení problému N dam pomocí prohledávání do hloubky, resp. backtrackingu__"]},{"cell_type":"code","metadata":{"id":"mrC8sahpsQZ9"},"source":["# pomocna funkce pro otestovani platnosti restrikce nove mozne pozice damy vzhledem k ostatnim damam na sachovnici\n","\n","def restricted(board,position):\n","    x1, y1 = position # souradnice testovane pozice damy\n","    for x2, y2 in board: # prochazime souradnice umistenych dam\n","        if x1 == x2 or y1 == y2: # podminka volne rady a sloupce porusena\n","            return False\n","    return True # podminka neporusena, pozice je OK\n","\n","# funkce pro generovani moznych rozestaveni; implicitne se resi problem 8 dam\n","\n","def generate_restricted_boards(board,row,n=8):\n","    if row == n: # posledni rada je kompletni\n","        yield board\n","    else: # generujeme dalsi radu ze vsech omezenych pozic v rade\n","        restricted_positions = [(row,j) for j in range(n) if restricted(board,(row,j))]\n","        for position in restricted_positions:\n","            for _board in generate_restricted_boards(board+[position],row+1,n=n):\n","                yield _board\n","\n","# pomocna funkce pro vypis vsech reseni\n","\n","def print_restricted_search_solutions(n=8):\n","    ok, total = 0, 0\n","    for board in generate_restricted_boards([],0,n=n):\n","        total += 1\n","        if safe_board(board,n):\n","            ok += 1\n","            print('Bezpecne rozestaveni cislo %d:' % ok)\n","            print_board(board,n)\n","    print('Konec prohledavani: otestovano celkem %d postaveni, nalezeno %d reseni' % (total,ok))    \n","                \n","# vypis bezpecnych reseni pro N=8\n","\n","print('Generovani bezpecnych rozestaveni 8 dam na sachovnici 8x8 (omezeni brute-force prohledavani)')\n","%time print_restricted_search_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"VpEq1esdsQaC"},"source":["### __Příklad 3.2: Problém N dam - ještě efektivnější řešení__\n","- Implementujte verzi s ještě výraznějším omezením stavového prostoru k prohledání:\n"," - Postupně umísťujeme první dámu do po sobě jdoucích sloupců v jedné řadě (např. od pozice \"úplně vlevo nahoře\" dále \"doprava\").\n"," - Dámy v dalších řadách umísťujeme tak, aby nebyly ohroženy žádnou již umístěnou dámou.\n"," - Není-li žádná taková pozice k dispozici, vracíme se o řadu výše.\n","\n","Poznámka bokem - tento algoritmus efektivně prohledá prostor všech řešení, ale stále se dá vylepšit (např. [heuristickým vyhledáváním](https://en.wikipedia.org/wiki/Heuristic_(computer_science)) nebo modelováním úlohy jako [problému s omezujícími podmínkami](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem), které budeme probírat v dalších cvičeních)."]},{"cell_type":"code","metadata":{"id":"uosfdhNHsQaC"},"source":["# funkce pro generovani efektivnich reseni pro postupne umistovani prvni damy v \"horni\" rade\n","\n","def generate_solutions(n=8):\n","    # postupne umistovani damy do vsech moznych pozic v prvni rade\n","    for j in range(n):\n","        initial_board = [(0,j)]\n","        # rekurzivni generovani moznych pozic dle pozice prvni damy\n","        for board in place_queens(initial_board,1,n=n):\n","            yield board\n","\n","# rekurzivni funkce pro umisteni damy do bezpecny pozice v dalsich radach\n","\n","def place_queens(board,row,n=8):\n","    # TODO - DOPLNIT SAMI\n","    yield board # TODO - odstranit ve skutecne implementaci\n","\n","# pomocna funkce pro vypis vsech reseni\n","\n","def print_backtracking_solutions(n=8):\n","    ok = 0\n","    for board in generate_solutions(n=n):\n","        ok += 1\n","        print('Bezpecne rozestaveni cislo %d:' % ok)\n","        print_board(board,n)\n","    print('Konec prohledavani: nalezeno %d reseni' % ok)    \n","                    \n","# vypis bezpecnych reseni pro N=8\n","\n","print('Generovani bezpecnych rozestaveni 8 dam na sachovnici 8x8 (DFS/backtracking)')\n","%time print_backtracking_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"_M6J0BS0sQaG"},"source":["#### __Možné ještě efektivnější řešení problému N dam__"]},{"cell_type":"code","metadata":{"id":"G9eR5EhLsQaG"},"source":["def place_queens(board,row,n=8):\n","    if row == n: # jsme v posledni rade, vsechny damy umisteny\n","        yield board\n","    else:\n","        # prochazime mozne pozice v aktualni rade\n","        for j in range(n):\n","            x2, y2 = row, j # mozne souradnice umistovane damy\n","            # testovani bezpecnosti moznych souradnic v zavislosti na jiz umistenych damach\n","            safe_position = True\n","            for x1, y1 in board: # prochazime souradnice jiz umistenych dam\n","                same_row    = x1 == x2 # stejne rada (jen pro uplnost - nemuze nastat)\n","                same_column = y1 == y2 # stejny sloupec\n","                same_diag1  = x2-x1 == y2-y1 # stejne hlavni diagonala\n","                same_diag2  = x2-x1 == y1-y2 # stejna vedlejsi diagonala\n","                # plati-li nektera podminka, neni pozice bezpecna\n","                if same_row or same_column or same_diag1 or same_diag2:\n","                    safe_position = False\n","                    break\n","            # prohledavame dale pouze z bezpecnych pozic (vyrazne omezeni stavoveho prostoru)\n","            if safe_position:\n","                for _board in place_queens(board+[(x2,y2)],row+1,n=n):\n","                    yield _board\n","\n","# vypis bezpecnych reseni pro N=8\n","\n","print('Generovani bezpecnych rozestaveni 8 dam na sachovnici 8x8 (DFS/backtracking)')\n","%time print_backtracking_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"collapsed":true,"id":"d5WalZensQaL"},"source":["---\n","\n","#### _Poznámka na závěr_ - materiály použité v tomto notebooku jsou převzatá originální díla licencovaná původními autory následujícím způsobem:\n","- Obrázek DFS:\n"," - Autor: [Alexander Drichel](http://www.drichel.name/)\n"," - Původní zdroj: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Depth-first-tree.svg)\n"," - Licence: [GFDL](https://en.wikipedia.org/wiki/GNU_Free_Documentation_License), v1.2+, [CC BY 3.0](https://creativecommons.org/licenses/by/3.0/deed.en)\n","- Obrázek BFS:\n"," - Autor: [Alexander Drichel](http://www.drichel.name/)\n"," - Původní zdroj: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Breadth-first-tree.svg)\n"," - Licence: [GFDL](https://en.wikipedia.org/wiki/GNU_Free_Documentation_License), v1.2+, [CC BY 3.0](https://creativecommons.org/licenses/by/3.0/deed.en)\n","- Obrázek 8queens:\n"," - Autor: [Encik Tekateki](https://commons.wikimedia.org/wiki/User:Encik_Tekateki)\n"," - Původní zdroj: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Solution_A_for_8_Queen_Puzzles.png)\n"," - Licence: [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.en)"]}]}