{"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_lab2_G01.ipynb","provenance":[],"collapsed_sections":["jOgwiVe6sQZX","48pyUMtKsQZf","8f_nVfr7sQZw","tKFgwwoAsQZ9","_M6J0BS0sQaG"]}},"cells":[{"cell_type":"markdown","metadata":{"id":"6UIjGYX9sQZL"},"source":["# PB016: Artificial intelligence I, lab 2 - State space search\n","\n","Today we'll deal with basic search algorithms. We'll focus namely on:\n","1. __Depth-first search__\n","2. __Breadth-first search__\n","3. __N-queens problem__"]},{"cell_type":"markdown","metadata":{"id":"uX6A5PTXsQZN"},"source":["---\n","\n","## 1. [Depth-First Search](https://en.wikipedia.org/wiki/Depth-first_search) (DFS for short)\n","\n","__Basic facts__\n","- One of the foundational algorithms for performing search in state spaces, which are typically represented as graphs (either explicit, or implicit, as in most actual practical problems).\n","- The algorithm is based on traversing the graph from one root vertex.\n","- It prioritises going as far as possible from the root at first.\n","- Whenever there is nowhere else to go, the algorithm [backtracks](https://en.wikipedia.org/wiki/Backtracking) to the nearest vertex from which the search can continue.\n","\n","__Example__ - the order of visited notes in a sample graph:\n","\n","![dfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/dfs.png)"]},{"cell_type":"markdown","metadata":{"id":"2RDeB70UsQZN"},"source":["### Recursive implementation of DFS\n","- We maintain a list of visited vertices.\n","- We iterate through a list of the current vertex neighbours and continue searching from every vertex that has not been visited before.\n","\n","Notes:\n","- For creating and manipulating the graph, we use the popular [NetworkX](https://networkx.github.io/documentation/stable/index.html) library.\n","- The depth-first principle doesn't necessarily mean there is always only one possible sequence in which a graph may be searched by DFS (as shown in the sample code below where the search sequence depends on the order in which the edges were added to the graph as it was being created)."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"fy9dSFajsQZO","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1632233324532,"user_tz":-120,"elapsed":1331,"user":{"displayName":"Vít Nováček","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"05686630748873346736"}},"outputId":"c8cd437d-1e1a-4a07-c581-20b5b2d9cbe9"},"source":["import networkx as nx\n","\n","# creating the graph from the above example\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","# resursive implementation of DFS\n","\n","def dfs_recursive(graph,vertex,visited):\n","    visited += [vertex] # updating the list of visited vertices\n","\n","    # iterating through the neighbour vertices\n","    for neighbour in graph[vertex]:\n","        if neighbour not in visited: # going deeper, if the vertex hasn't been visited yet\n","            visited = dfs_recursive(graph,neighbour,visited)\n","\n","    return visited\n","\n","# printing out sample search sequences\n","\n","G=nx.Graph()\n","edges = [(1,2), (2,3), (3,4), (3,5), (2,6), (1,7), (1,8), (8,9), (9,10), (9,11), (8,12)]\n","G.add_edges_from(edges)\n","print('Recursive DFS - search sequence from vertex %d: %s' % (1, dfs_recursive(G,1,[])))\n","print('Recursive DFS - search sequence from vertex %d: %s' % (12, dfs_recursive(G,12,[])))\n","G=nx.Graph()\n","reversed_edges = reversed([(1,2), (2,3), (3,4), (3,5), (2,6), (1,7), (1,8), (8,9), (9,10), (9,11), (8,12)])\n","G.add_edges_from(reversed_edges)\n","print('Recursive DFS (reversed edges) - search sequence from vertex %d: %s' % (1, dfs_recursive(G,1,[])))\n","print('Recursive DFS (reversed edges) - search sequence from vertex %d: %s' % (12, dfs_recursive(G,12,[])))"],"execution_count":1,"outputs":[{"output_type":"stream","name":"stdout","text":["Recursive DFS - search sequence from vertex 1: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]\n","Recursive DFS - search sequence from vertex 12: [12, 8, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11]\n","Recursive DFS (reversed edges) - search sequence from vertex 1: [1, 8, 12, 9, 11, 10, 7, 2, 6, 3, 5, 4]\n","Recursive DFS (reversed edges) - search sequence from vertex 12: [12, 8, 9, 11, 10, 1, 7, 2, 6, 3, 5, 4]\n"]}]},{"cell_type":"markdown","metadata":{"id":"FffsRcR7sQZT"},"source":["### __Exercise 1.1: Non-recursive DFS using a stack__\n","- Implement a non-recursive version of DFS using a stack of vertices and their neighbours.\n","- Always take the most recently visited vertex from the stack and search the previously unseen neighbour vertices further, until the stack is empty.\n"," - Note: To implement the stack, use simply a list, adding and removing elements using the `append()` and `pop()` functions, respectively."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"9z9o7CFwsQZU"},"source":["# implementation of DFS with stack\n","\n","def dfs_stack(graph,vertex):\n","    visited = [] # TODO - COMPLETE THE INITIALISATION OF A LIST OF VISITED VERTICES\n","    stack = [] # TODO - COMPLETE THE INITIALISATION OF THE STACK LIST\n","    \n","    # processing the stack until it's empty\n","    while stack:\n","        # TODO - COMPLETE YOURSELVES\n","        break # TODO - remove in the actual implementation\n","    \n","    return visited\n","            \n","# printing out sample search sequences\n","\n","print('DFS with stack - search sequence from vertex %d: %s' % (1, dfs_stack(G,1)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"jOgwiVe6sQZX"},"source":["#### __A possible implementation of non-recursive DFS using a stack__"]},{"cell_type":"code","metadata":{"scrolled":false,"id":"6wPS2aDCsQZY"},"source":["# implementation of DFS with stack\n","\n","def dfs_stack(graph,vertex):\n","    visited = [] # initialisation of the list of visited vertices\n","    stack = [vertex] # initialisation of the stack\n","\n","    # processing the stack until it's empty\n","    while stack:\n","\n","        # getting the vertex to search further from the stack\n","        current = stack.pop()\n","\n","        # adding the unseen neigbour vertices into the stack\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","# printing out sample search sequences\n","\n","G=nx.Graph()\n","edges = [(1,2), (2,3), (3,4), (3,5), (2,6), (1,7), (1,8), (8,9), (9,10), (9,11), (8,12)]\n","G.add_edges_from(edges)\n","print('DFS with stack - search sequence from vertex %d: %s' % (1, dfs_stack(G,1)))\n","print('DFS with stack - search sequence from vertex %d: %s' % (12, dfs_stack(G,12)))\n","G=nx.Graph()\n","reversed_edges = reversed([(1,2), (2,3), (3,4), (3,5), (2,6), (1,7), (1,8), (8,9), (9,10), (9,11), (8,12)])\n","G.add_edges_from(reversed_edges)\n","print('DFS with stack (reverse edges) - search sequence from vertex %d: %s' % (1, dfs_stack(G,1)))\n","print('DFS with stack (reverse edges) - search sequence from vertex %d: %s' % (12, dfs_stack(G,12)))"],"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":["### __Exrercise 1.2: Recursive DFS with a depth limit__\n","- Implement a DFS version where one can stop the recursive search when reaching a given depth (i.e. the distance from the root of the search)."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"JlQ5JHalsQZc"},"source":["# recursive implementation of DFS with a limit (if the limit max_depth==0 then the whole graph is searched)\n","def dfs_recursive_limited(graph,vertex,visited,depth,max_depth=0):\n","    visited += [vertex] # updating the list of visited vertices\n","    \n","    # TODO - COMPLETE YOURSELVES\n","    \n","    return visited\n","\n","# printing out the search sequence from vertex 1\n","\n","print('Recursive DFS - search sequence from vertex %d, max. depth %d: %s' % (1, 2, dfs_recursive_limited(G,1,[],0,max_depth=2)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"48pyUMtKsQZf"},"source":["#### __A possible implementation of recursive DFS with a depth limit__"]},{"cell_type":"code","metadata":{"scrolled":false,"id":"oV2hqIbksQZg"},"source":["# recursive implementation of DFS with a limit (if the limit max_depth==0 then the whole graph is searched)\n","def dfs_recursive_limited(graph,vertex,visited,depth,max_depth=0):\n","    visited += [vertex] # updating the list of visited vertices\n","    depth += 1\n","\n","    if max_depth > 0 and depth == max_depth: # checking the depth limit\n","        return visited\n","\n","    neighbours = sorted(list(graph[vertex]))\n","\n","    # iterating through the neighbour vertices\n","    for neighbour in neighbours: \n","        if neighbour not in visited: # going deeper, if vertex not visited\n","            visited = dfs_recursive_limited(graph,neighbour,visited,depth,max_depth)\n","\n","    return visited\n","\n","# printing out the search sequence from vertex 1\n","\n","print('Recursive DFS - search sequence from vertex %d, max. depth %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. [Breadth-First Search](https://en.wikipedia.org/wiki/Breadth-first_search) (BFS for short)\n","\n","__Basic facts__\n","- Another basic algorithm for searching a state space represented as a graph.\n","- BFS, quite like DFS, is based on searching the graph from one root vertex.\n","- However, it prioritises the list of neighbours of the currently searched vertex before going one level deeper.\n","\n","__Example__ - the order of visited notes in a sample graph:\n","\n","![bfs.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/bfs.png)"]},{"cell_type":"markdown","metadata":{"id":"EglJ1pQbsQZt"},"source":["### __Exercise 2.1: BFS using a queue__\n","- Implement BFS using a queue.\n","- Maintain a queue of vertices to traverse, to which the visited vertices and their neighbours are being added.\n"," - Note: For implementing the queue, a standard list is enough again. The elements can be added using the `append()` function, just like we did for a stack, but they are removed from the head, i.e. the beginning of the list, using `pop(0)`.\n","- Take the next vertex to be traversed from the head of the queue until it's empty."]},{"cell_type":"code","metadata":{"id":"aTtWqagTsQZt"},"source":["# creating the graph from the above example\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 = [] # initialising the list of visited vertices\n","    queue = [] # TODO - COMPLETE THE QUEUE INITIALISATION\n","\n","    # processing the queue until it's empty\n","    while queue:\n","        # TODO - COMPLETE YOURSELVES\n","        break # TODO - remove in the actual implementation\n","                \n","    return visited\n","\n","# printing out the search sequence from vertex 1\n","print('BFS - search sequence from vertex %d: %s' % (1, bfs_queue(G,1)))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"8f_nVfr7sQZw"},"source":["#### __A possible implementation of BFS using queue__"]},{"cell_type":"code","metadata":{"id":"kZg8zjG6sQZx"},"source":["def bfs_queue(graph, vertex):\n","    visited = [] # initialising the list of visited vertices\n","    queue = [vertex] # initialising the queue\n","\n","    # processing the queue until it's empty\n","    while queue:\n","\n","        # getting the next vertex to explore\n","        next_vertex = queue.pop(0)\n","\n","        # adding the so far unseen neighbours to the queue\n","        if next_vertex not in visited: \n","            visited.append(next_vertex)\n","            neighbours = list(graph[next_vertex])\n","            for neighbour in neighbours:\n","                queue.append(neighbour)\n","                \n","    return visited\n","\n","# printing out the search sequence from vertex 1\n","print('BFS - search sequence from vertex %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. N-queens problem (c.f. [Eight Queens Puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle))\n","\n","__Basic facts__\n","- A classic problem in mathematics and programming.\n","- The point is to place N queens on an NxN board so that they don't threaten each other.\n","- Easily defined, yet hard (and thus \"big\") problem.\n","\n","| Board size | Possible positions | Total solutions | Unique solutions |\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","__Example__ - a solution to the 8 queens problem:\n","\n","![8queens.png](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/8queens.png)"]},{"cell_type":"markdown","metadata":{"id":"al6-7zmFsQZ1"},"source":["### A brute-force solution\n","- Generating all possible combinations of queen placements (i.e. positions).\n","- Checking if all queens in the given position are safe. \n","- A technical note:\n"," - The `yield` keyword used in the `generate_all_boards()` function instead of the perhaps more typical `return` effectively makes the function a generator (which can be used exactly in the same way like  an iterator through a Python collection object).\n"," - The advantage in this particular case (and many other similar ones) is that we don't need to generate all possible solutions (i.e. boards) before returning them, but instead generate one at a time and pass it to the higher-level code for further processing.\n"," - This saves a lot of computational overhead and memory."]},{"cell_type":"code","metadata":{"scrolled":true,"id":"2CQ_8BX_sQZ1"},"source":["import itertools as it # will need this for generating the positions\n","\n","# position generator function; 8 queens by default\n","\n","def generate_all_boards(n=8):\n","    # generating a list of all fields on the board\n","    fields = [(i,j) for i in range(n) for j in range(n)]\n","            \n","    # generating all possible placements of the queens onto the board (i.e. lists of N different occupied fields)\n","    for board in it.combinations(fields,n):\n","        yield board\n","        \n","# function for testing the position\n","\n","def safe_board(board,n=8):\n","    # too big or small board, wrong by default\n","    if len(board) != n:\n","        return False\n","    \n","    # checking the threat to the queens one by one in the position list\n","    for i in range(n):\n","        x1, y1 = board[i]\n","\n","        # checking only the remaining ones, the previous ones are OK\n","        for x2, y2 in board[i+1:]:\n","            if x1 == x2: # another queen in the same row\n","                return False\n","            elif y1 == y2: # another queen in the same column\n","                return False\n","            elif x2-x1 == y2-y1: # another queen in the same primary diagonal\n","                return False\n","            elif x2-x1 == y1-y2: # another queen in the same secondary diagonal\n","                return False\n","\n","    # no test has failed, all queens safe\n","    return True\n","\n","# auxiliary function for displaying the queen positions on a board\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","# auxiliary function for printing out all solutions\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('... tested %d possible positions ...' % total)\n","        if safe_board(board,n):\n","            ok += 1\n","            print('Safe position no. %d:' % ok)\n","            print_board(board,n)\n","    print('End of search: tested %d positions in total, found %d solutions' % (total,ok))\n","\n","# printing safe solutions for N=8\n","\n","print('Generating safe positions for 8 queens on a 8x8 board (brute force)')\n","%time print_brute_force_solutions(8) # WARNING - will take a LOT of time"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"QocJAgU_sQZ4"},"source":["### __Exercise 3.1: A less naive solution to the N queens problem using DFS / backtracking__\n","- The naive solution is terribly inefficient.\n","- The state space to be searched can be reduced, though:\n"," - We can recursively place the queens row by row so that any given row and column always contains just one.\n"," - The recursion is over the moment all queens are placed.\n"," - If no queen can be placed in the current row, the algorithm backtracks to the previous one.\n"," - This is equivalent to depth-searching a graph of all possible solutions. However, the graph is only an implicit representation of the problem's structure in this case.\n","- For 8 queens, this strategy reduces the space of candidate positions to 40,320 instead of 4,426,165,368.\n","- Try to implement this solution."]},{"cell_type":"code","metadata":{"id":"5UmL-9IEsQZ5"},"source":["# auxiliary function for testing the safety of the queen position w.r.t. the other queens on the board\n","\n","def restricted(board,position):\n","    # TODO - COMPLETE YOURSELVES (board is a list of (x,y) coordinates, position is a single coordinate tuple)\n","    \n","    return True # condition satisified, position is OK\n","\n","# function for generating possible positions; 8 queens by default\n","\n","def generate_restricted_boards(board,row,n=8):\n","    # TODO - COMPLETE YOURSELVES\n","    \n","    yield board # TODO - remove in the actual implementation\n","\n","# auxiliary function for printing all solutions\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('Safe position no. %d:' % ok)\n","            print_board(board,n)\n","    print('End of search: tested %d positions in total, found %d solutions' % (total,ok))\n","                \n","# printing safe solutions for N=8\n","\n","print('Generating safe positions for 8 queens on a 8x8 board (restricted brute-force search)')\n","%time print_restricted_search_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"tKFgwwoAsQZ9"},"source":["#### __A possible less naive solution to the N queens problem using DFS / backtracking__"]},{"cell_type":"code","metadata":{"id":"mrC8sahpsQZ9"},"source":["# auxiliary function for testing the safety of the queen position w.r.t. the other queens on the board\n","\n","def restricted(board,position):\n","    x1, y1 = position # coordinates of the tested queen position\n","    for x2, y2 in board: # iterating through the coordinates of the placed queens\n","        if x1 == x2 or y1 == y2: # the condition of the free row and column not satisfied\n","            return False\n","    return True # condition satisfied, position is OK\n","\n","# function for generating possible positions; 8 queens by default\n","\n","def generate_restricted_boards(board,row,n=8):\n","    if row == n: # the last row is complete\n","        yield board\n","    else: # generating the next row from all restricted positions in the current one\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","# auxiliary function for printing all solutions\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('Safe position no. %d:' % ok)\n","            print_board(board,n)\n","    print('End of search: tested %d positions in total, found %d solutions' % (total,ok))\n","                \n","# printing safe solutions for N=8\n","\n","print('Generating safe positions for 8 queens on a 8x8 board (restricted brute-force search)')\n","%time print_restricted_search_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"VpEq1esdsQaC"},"source":["### __Exercise 3.2: N queens problem - yet more efficient solution__\n","- Implement a version with still more radical restriction of the state space to be searched:\n"," - We're placing the first queen to the columns in one row (for instance, starting from the \"top left\" corner of the board and going \"right\").\n"," - The queens in the consequent rows are then placed so that they are not threatened by any of the previously placed ones.\n"," - If no such position is available, we're backtracking one row up.\n","\n","A side note - this algorithm efficiently searchs the space of candidate solutions, but it can be done better still (e.g. via [heuristic search](https://en.wikipedia.org/wiki/Heuristic_(computer_science)) or modelling the task as a [constraint satisfaction problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem), which we will discuss in other labs later on)."]},{"cell_type":"code","metadata":{"id":"uosfdhNHsQaC"},"source":["# functions for generating efficient solutions based on placing the first queen in the \"top\" row\n","\n","def generate_solutions(n=8):\n","    # sequential placing of the queen to all positions in the first row\n","    for j in range(n):\n","        initial_board = [(0,j)]\n","        # recursive generation of other positions based on the first queen position\n","        for board in place_queens(initial_board,1,n=n):\n","            yield board\n","\n","# recursive function for placing the other queens to safe positions\n","\n","def place_queens(board,row,n=8):\n","    # TODO - COMPLETE YOURSELVES\n","    yield board # TODO - remove in the actual implementation\n","\n","# auxiliary function for printing all solutions\n","\n","def print_backtracking_solutions(n=8):\n","    ok = 0\n","    for board in generate_solutions(n=n):\n","        ok += 1\n","        print('Safe position no. %d:' % ok)\n","        print_board(board,n)\n","    print('End of search: found %d solutions' % ok)    \n","                    \n","# printing safe solutions for N=8\n","\n","print('Generating safe positions for 8 queens on a 8x8 board (yet more restricted search)')\n","%time print_backtracking_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"_M6J0BS0sQaG"},"source":["#### __A possible yet more efficient solution to the N queens problem__"]},{"cell_type":"code","metadata":{"id":"G9eR5EhLsQaG"},"source":["def place_queens(board,row,n=8):\n","    if row == n: # we're in the last row, all queens placed\n","        yield board\n","    else:\n","        # going through all positions in the current row\n","        for j in range(n):\n","            x2, y2 = row, j # possible coordinates of the queen to be placed\n","            # testing the safety of possible coordinates depending on the queens placed before\n","            safe_position = True\n","            for x1, y1 in board: # going through the coordinates of the already placed queens\n","                same_row    = x1 == x2 # same row (just for the sake of completeness - can't happen)\n","                same_column = y1 == y2 # same column\n","                same_diag1  = x2-x1 == y2-y1 # same main diagonal\n","                same_diag2  = x2-x1 == y1-y2 # same secondary diagonal\n","                # if any condition holds, the position is not safe\n","                if same_row or same_column or same_diag1 or same_diag2:\n","                    safe_position = False\n","                    break\n","            # searching further only from safe positions (significant reduction of the state space)\n","            if safe_position:\n","                for _board in place_queens(board+[(x2,y2)],row+1,n=n):\n","                    yield _board\n","\n","# printing safe solutions for N=8\n","print('Generating safe positions for 8 queens on a 8x8 board (yet more restricted search)')\n","%time print_backtracking_solutions(8)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"collapsed":true,"id":"d5WalZensQaL"},"source":["---\n","\n","#### _Final note_ - some materials used in this notebook are adapted works licensed by their original authors as follows:\n","- DFS figure:\n"," - Author: [Alexander Drichel](http://www.drichel.name/)\n"," - Original source: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Depth-first-tree.svg)\n"," - License: [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","- BFS figure:\n"," - Author: [Alexander Drichel](http://www.drichel.name/)\n"," - Original source: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Breadth-first-tree.svg)\n"," - License: [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","- 8queens figure:\n"," - Author: [Encik Tekateki](https://commons.wikimedia.org/wiki/User:Encik_Tekateki)\n"," - Original source: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Solution_A_for_8_Queen_Puzzles.png)\n"," - License: [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.en)"]}]}