{"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":{"provenance":[],"collapsed_sections":["OWiy-9Xbwhs6","FioIHsEFwht3"]}},"cells":[{"cell_type":"markdown","metadata":{"id":"W4R6L_rcwhsz"},"source":["# PB016: Artificial Intelligence I, lab 3 - Heuristic search\n","\n","Today we'll deal with heuristic algorithms for state space search. We'll focus namely on:\n","1. __Best-first search__\n","2. __A* search__\n","3. __A* search applied to a game (8-puzzle)__"]},{"cell_type":"markdown","metadata":{"id":"X9Au1BAxwhs0"},"source":["---\n","\n","## 1. [Best-First Search](https://en.wikipedia.org/wiki/Best-first_search)\n","\n","__Basic facts__\n","- A search algorithm that preferentially visits the most \"promising\" vertices while searching for the goal vertex.\n","- The promise of a vertex is usually defined by a heuristic rule (i.e. heuristic) that depends on the nature of the problem.\n","- Slightly more formally - a heuristic for estimating the promise of a vertex $n$ is a function $h(n)$, which generally depends on one or more of the following:\n"," - the properties of the vertex $n$,\n"," - the properties of the goal vertex,\n"," - information gained during the search so far,\n"," - any other information related to the problem that is being solved.\n","- Many instances exist, e.g. [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), [B\\* search](https://en.wikipedia.org/wiki/B*) or [A\\* search](https://en.wikipedia.org/wiki/A*_search_algorithm) (covered below)."]},{"cell_type":"markdown","metadata":{"id":"2hkszmXbwhs1"},"source":["### Problem definition for purely heuristic search\n","\n","\n","- Finding a path between Arad to Bucharest on a simplified map of Romania (for the sake of simplicity, we won't bother about cycles, etc., here or in any of the following exercises).\n","- At first we represent the map as a graph."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"4kHk1E1dwhs2"},"source":["# creating a simplified map of Romania\n","\n","import networkx as nx\n","\n","# creating a graph representing the map\n","romania_map = nx.Graph()\n","\n","# filling the graph with edges representing direct connections (i.e. roads)\n","# between the towns and their length\n","\n","romania_map.add_edge('Arad', 'Zerind', cost=75)\n","romania_map.add_edge('Arad', 'Sibiu', cost=140)\n","romania_map.add_edge('Arad', 'Timisoara', cost=118)\n","romania_map.add_edge('Bucharest', 'Urziceni', cost=85)\n","romania_map.add_edge('Bucharest', 'Pitesti', cost=101)\n","romania_map.add_edge('Bucharest', 'Giurgiu', cost=90)\n","romania_map.add_edge('Bucharest', 'Fagaras', cost=211)\n","romania_map.add_edge('Craiova', 'Drobeta', cost=120)\n","romania_map.add_edge('Craiova', 'Rimnicu', cost=146)\n","romania_map.add_edge('Craiova', 'Pitesti', cost=138)\n","romania_map.add_edge('Drobeta', 'Mehadia', cost=75)\n","romania_map.add_edge('Eforie', 'Hirsova', cost=86)\n","romania_map.add_edge('Fagaras', 'Sibiu', cost=99)\n","romania_map.add_edge('Hirsova', 'Urziceni', cost=98)\n","romania_map.add_edge('Iasi', 'Vaslui', cost=92)\n","romania_map.add_edge('Iasi', 'Neamt', cost=87)\n","romania_map.add_edge('Lugoj', 'Timisoara', cost=111)\n","romania_map.add_edge('Lugoj', 'Mehadia', cost=70)\n","romania_map.add_edge('Oradea', 'Zerind', cost=71)\n","romania_map.add_edge('Oradea', 'Sibiu', cost=151)\n","romania_map.add_edge('Pitesti', 'Rimnicu', cost=97)\n","romania_map.add_edge('Rimnicu', 'Sibiu', cost=80)\n","romania_map.add_edge('Urziceni', 'Vaslui', cost=142)\n","\n","# coordinates of the towns on the map (for computing the air distance between\n","# any two towns)\n","\n","romania_coordinates = {\n","    'Arad':(91, 492), 'Bucharest':(400, 327), 'Craiova':(253, 288),\n","    'Drobeta':(165, 299), 'Eforie':(562, 293), 'Fagaras':(305, 449),\n","    'Giurgiu':(375, 270), 'Hirsova':(534, 350), 'Iasi':(473, 506),\n","    'Lugoj':(165, 379), 'Mehadia':(168, 339), 'Neamt':(406, 537),\n","    'Oradea':(131, 571), 'Pitesti':(320, 368), 'Rimnicu':(233, 410),\n","    'Sibiu':(207, 457), 'Timisoara':(94, 410), 'Urziceni':(456, 350),\n","    'Vaslui':(509, 444), 'Zerind':(108, 531)\n","}"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"OWiy-9Xbwhs6"},"source":["#### Visualising the map of Romania\n","\n","![Romania](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/romania.png)"]},{"cell_type":"markdown","metadata":{"id":"k-KQO4Itwhs7"},"source":["#### Data structure required for the search\n","- Best-first search typically uses a [priority queue](https://en.wikipedia.org/wiki/Priority_queue) for picking the most promising vertices.\n","- We'll be using an implementation from the standard library in Python."]},{"cell_type":"code","metadata":{"id":"VTh_0Cd8whs8"},"source":["from queue import PriorityQueue\n","\n","pq = PriorityQueue() # initialising the priority queue\n","\n","# test of the priority queue\n","\n","# see that we always insert pairs (priority, node)\n","pq.put((9999., 'Arad'))\n","pq.put((0., 'Bucharest'))\n","pq.put((8888., 'Zerind'))\n","pq.put((7777., 'Sibiu'))\n","\n","# minimal value is taken out first\n","while not pq.empty():\n","    # check how we take out items from the priority queue\n","    value, node = pq.get()\n","    print(f'An element with the lowest weight ({value}): {node}')"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"OQ8P5MxcwhtA"},"source":["### __Exercise 1.1: Best-first search - heuristic__\n","- For the actual implementation of finding the path between two towns by the best-first search algorithm, one of the applicable heuristics is the air distance between the towns being visited and the goal (Bucharest).\n"," - Note: The air distance between two points A and B is typically computed from the coordinates of A and B using the  [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance).\n","- Implement this heuristic."]},{"cell_type":"code","metadata":{"scrolled":true,"id":"3iSwPpj5whtB"},"source":["import math  # guess which math fn do we need?\n","\n","def heuristic(current, goal='Bucharest'):\n","    \"\"\"Compute the value of distance-based heuristic for finding the path\n","    between the input towns.\n","\n","    Parameters\n","    ----------\n","    current : str\n","        The name of the town from which the path to the goal is currently to\n","        be found.\n","    goal : str, optional (default is 'Bucharest') for this specific assignment\n","        The name of the goal town.\n","\n","    Returns\n","    -------\n","    float\n","        The value of the `current` town heuristic, i.e., how promising it is to\n","        reach the goal from it.\n","    \"\"\"\n","\n","    h_val = float('inf') # returns infinity if there's a wrong input, etc.\n","    # TODO - COMPLETE YOURSELVES\n","    return h_val\n","\n","\n","# checking the correctness of the heuristic\n","if round(heuristic('Arad', 'Bucharest'), 6) == 350.294162:\n","    print('OK.')\n","else:\n","    print('Not quite OK.')"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"tKCVdsagwhtI"},"source":["### __Exercise 1.2: Greedy best-first search - a basic version__\n","- The search is greedy - the vertex to be explored first is always the one with the best heuristic value.\n","- In the basic version we're only testing the path existence."]},{"cell_type":"code","metadata":{"id":"G97H-esIwhtJ"},"source":["def greedy_best_first_search_test_only(graph, h, start='Arad', goal='Bucharest'):\n","    \"\"\"Uses the greedy best-first search algorithm to test for existence of the\n","    path between the two input nodes.\n","\n","    Parameters\n","    ----------\n","    graph : networkx.Graph\n","        The graph representing the map to be searched.\n","    h : typing.Callable (i.e., a function)\n","        The heuristic function to be used for computing how promising the\n","        particular searched towns for reaching the goal town.\n","    start : str, optional (default is 'Arad') for this specific assignment\n","        The name of the starting town.\n","    goal : str, optional (default is 'Bucharest') for this specific assignment\n","        The name of the goal town.\n","\n","    Returns\n","    -------\n","    bool\n","        Whether or not a path has been found between the `start` and `goal`\n","        towns.\n","    \"\"\"\n","\n","    found = False # default result\n","\n","    # TODO - COMPLETE YOURSELVES\n","\n","    return found"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# testing the result of the search\n","if greedy_best_first_search_test_only(romania_map, heuristic):\n","    print('There is a path between Arad and Bucharest.')\n","else:\n","    print('There is no path between Arad and Bucharest.')"],"metadata":{"id":"XcoYkfgmn74N"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"FdOQQHsXwhtQ"},"source":["### __Exercise 1.3: Best-first search - a version with printing out the path__\n","- Augment the search by\n"," - keeping track of the predecessors of vertices on the searched path;\n"," - printing out the path with its final cost (i.e. the total traveled distance between Arad and Bucharest as a sum of the lengths of the particular direct connections between the towns on the path)."]},{"cell_type":"code","metadata":{"id":"_s4mKJldwhtR"},"source":["def greedy_best_first_search(graph, h, start='Arad', goal='Bucharest'):\n","    \"\"\"Uses the greedy best-first search algorithm to test for existence of\n","    the path between the two input nodes.\n","\n","    Parameters\n","    ----------\n","    graph : networkx.Graph\n","        The graph representing the map to be searched.\n","    h : typing.Callable (i.e., a function)\n","        The heuristic function to be used for computing how promising the\n","        particular searched towns for reaching the goal town.\n","    start : str, optional (default is 'Arad') for this specific assignment\n","        The name of the starting town.\n","    goal : str, optional (default is 'Bucharest') for this specific assignment\n","        The name of the goal town.\n","\n","    Returns\n","    -------\n","    tuple\n","        A pair consisting of the following elements:\n","        - A `bool` variable that records whether or not a path has been found\n","          between the `start` and `goal` towns.\n","        - A `dict` variable that records the path itself as a mapping of the\n","          towns in the path to their predecessors.\n","    \"\"\"\n","\n","    found = False\n","    frontier = PriorityQueue()\n","    frontier.put((h(start, goal), start))\n","    came_from = {} # the map of precedessors\n","    came_from[start] = None # initialising the map\n","\n","    # TODO - COMPLETE YOURSELVES\n","\n","    return found, came_from\n","\n","\n","def reconstruct_path(graph, came_from, start='Arad', goal='Bucharest'):\n","    \"\"\"Reconstructs the path from start to goal town (will be also used for A*).\n","\n","    HINT - to get an edge's cost, you can use the `graph[from][to]['cost']`\n","           notation!\n","\n","    Parameters\n","    ----------\n","    graph : networkx.Graph\n","        The graph representing the map to be searched.\n","    came_from : dict\n","        A dictionary mapping the towns in the path to their predecessors.\n","    start : str, optional (default is 'Arad') for this specific assignment\n","        The name of the starting town.\n","    goal : str, optional (default is 'Bucharest') for this specific assignment\n","        The name of the goal town.\n","\n","    Returns\n","    -------\n","    tuple\n","        A pair consisting of the following elements:\n","        - An `int` `list` variable that records the cost (i.e., length) of the\n","          path between the `start` and `goal` towns.\n","        - A `list` that records the path itself.\n","    \"\"\"\n","\n","    current = goal # we're going backwards, i.e. from the goal\n","    path = [] # empty path\n","    cost = 0 # zero cost of an empty path\n","\n","    # TODO - COMPLETE YOURSELVES\n","\n","    return cost, path"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# testing the result of the search and printing out the path\n","start, end = 'Arad', 'Bucharest'\n","found, came_from = greedy_best_first_search(romania_map, heuristic, start=start,\n","                                            goal=end)\n","if found:\n","    print('There is a path between Arad and Bucharest.')\n","    cost, path = reconstruct_path(romania_map, came_from, start=start, goal=end)\n","    print('  - the cost is:', cost)\n","    print('  - the path is:', path)\n","else:\n","    print('There is no path between Arad and Bucharest.')"],"metadata":{"id":"w2wEUILVoLyr"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"FXA8GYcNwhtY"},"source":["---\n","\n","## 2. [A\\* Search](https://en.wikipedia.org/wiki/A*_search_algorithm)\n","\n","__Basic facts__\n","- One of the most famous forms of best-first search.\n","- It combines a heuristic estimate of the most promising vertices with the actual cost of the path so far.\n","- Guaranteed to find an optimal solution with the proper choice of a heuristic."]},{"cell_type":"markdown","metadata":{"id":"Xzgfw5yCwhtZ"},"source":["### __Exercise 2.1: Extending the best-first search to A*__\n","- In addition to the vertex promise (defined by the heuristic) we also take into account the actual cost of the path so far.\n","- Slightly more formally, in each step of the search, we're prioritising the vertices $n$ that minimise the value $f(n) = g(n)+h(n)$, where:\n"," - $g(n)$ is the actual cost of the path so far (for the problem of finding a path between cities, it is thus the sum of the lengths of the direct connections between the currently traversed towns);\n"," - $h(n)$ is the heuristic estimate of the cost of making it from the current vertex to the goal one (just like in the greedy best-first search).\n","- Implement this version of best-first search and compare it with the previous one."]},{"cell_type":"code","metadata":{"scrolled":true,"id":"zHQkij1vwhtZ"},"source":["def astar_search(graph, h, start='Arad', goal='Bucharest'):\n","    \"\"\"Uses the A* search to pre-compute a path between two nodes.\n","\n","    Parameters\n","    ----------\n","    graph : networkx.Graph\n","        The graph representing the map to be searched.\n","    h : typing.Callable (i.e., a function)\n","        The heuristic function to be used for computing how promising the\n","        particular searched towns for reaching the goal town.\n","    start : str, optional (default is 'Arad') for this specific assignment\n","        The name of the starting town.\n","    goal : str, optional (default is 'Bucharest') for this specific assignment\n","        The name of the goal town.\n","\n","    Returns\n","    -------\n","    tuple\n","        A pair consisting of the following elements:\n","        - A `bool` variable that records whether or not a path has been found\n","          between the `start` and `goal` towns.\n","        - A `dict` variable that records the path itself as a mapping of the\n","          towns in the path to their predecessors.\n","    \"\"\"\n","\n","    frontier = PriorityQueue()\n","    frontier.put((h(start, goal), start))\n","    found = False\n","    came_from = {}\n","    came_from[start] = None\n","    cost_so_far = {} # adding the map of actual cost of visiting the vertices\n","    cost_so_far[start] = 0 # zero cost for the starting vertex\n","\n","    # TODO - COMPLETE YOURSELVES\n","\n","    return found, came_from"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# testing the result of the search and printing out the path\n","start, end = 'Arad', 'Bucharest'\n","found, came_from = astar_search(romania_map, heuristic, start, end)\n","if found:\n","    print(f'There is a path between {start} and {end}.')\n","    cost, path = reconstruct_path(romania_map, came_from, start, end)\n","    print('  - the cost is:', cost)\n","    print('  - the path is:', path)\n","else:\n","    print(f'There is no path between {start} and {end}.')"],"metadata":{"id":"f1i4QU8Zp-gu"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"LCZKj6ARwhth"},"source":["---\n","\n","## 3. A* search applied to a game (8-puzzle)\n","\n","__Basic facts__\n","- A puzzle consisting of a game board with 9 fields (3x3).\n","- On 8 of these fields, 8 square playing blocks are placed (marked by numbers between 1 and 8). The remaining field is empty.\n","- The goal is to move the blocks around so that they are ordered from 1 to 8.\n","- One can only move the blocks around vertically or horizontally to the empty field.\n"," - In our representation of the problem, this will correspond to \"moving\" the empty field LEFT, RIGHT, UP or DOWN.\n","\n","__An example__ - \"unfolding\" of possible paths towards the goal from a particular state of the 8-puzzle:\n","\n","![8puzzle](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/8puzzle.jpg)"]},{"cell_type":"markdown","metadata":{"id":"65MzWnAIwhti"},"source":["### Representation of the 8-puzzle problem and helper functions\n","- One can represent the board positions using a tuple of $9$ integers from $0$ to $8$, where $0$ corresponds to the empty field.\n","- For instance, `(8,1,3,0,2,4,7,6,5)` corresponds to a board where the first row from the top contains the blocks $8,1,3$, the second starts with the empty field followed by $2,4$ and the third row contains the blocks $7,6,5$. This is the first board from the left in the bottom row in the example above.\n","- The particular states of the problem solution space can be represented as pairs with the following elements:\n"," - the current positions of the blocks on the board,\n"," - the sequence of moves (i.e. \"transitions\" of the empty field) from the starting board to the current state.\n","- The expansion of the current state is performed via a function that generates all possible next states except the one that immediately preceded the current state (to make sure we don't just shuffle the blocks there and back)."]},{"cell_type":"code","metadata":{"scrolled":true,"id":"-o3op8ICwhtj"},"source":["# mapping the natural language representation of moving the empty field to the\n","# corresponding index changes on a matrix representation of the playing board\n","move_map = {\n","    'UP' : (-1,0),\n","    'DOWN' : (1,0),\n","    'LEFT' : (0,-1),\n","    'RIGHT' : (0,1)\n","}\n","\n","# mapping of the inverse moves (to detect trivially repeating consecutive states)\n","move_inverse = {\n","    'LEFT': 'RIGHT',\n","    'RIGHT': 'LEFT',\n","    'UP': 'DOWN',\n","    'DOWN': 'UP'\n","}\n","\n","\n","def transform_board(board, move):\n","    \"\"\"Moves the empty field 'LEFT', 'RIGHT', 'UP' or 'DOWN' and swaps it with\n","    the corresponding tile.\n","\n","    Parameters\n","    ----------\n","    board : tuple\n","        A tuple representation of the board - the elements with indices 0,1,2\n","        representing the top row (from left to right), the elements with indices\n","        3,4,5 representing the middle row (from left to right) and the elements\n","        with indices 6, 7, 8 representing the bottom row (from left to right).\n","        The values of the tuple elements represent the pieces of the game, with\n","        0 corresponding to the empty field.\n","    move : str (one of 'LEFT', 'RIGHT', 'UP' or 'DOWN' accepted)\n","        The move to be executed.\n","\n","    Returns\n","    -------\n","    tuple\n","        A tuple representation of the board after executing the (valid) move.\n","    \"\"\"\n","\n","    board_matrix = {} # simple matrix representation of the board\n","    zero_i, zero_j = -1, -1 # empty field position (nonsense by default)\n","\n","    # filling the matrix from the input \"flat\" representation of the board\n","    for k in range(9):\n","        i, j = k // 3, k % 3\n","        board_matrix[(i, j)] = board[k]\n","        if board[k] == 0:\n","            zero_i, zero_j = i, j\n","\n","    if zero_i == -1 or zero_j == -1: # checking for nonsense empty field\n","        return board # empty field is not valid, return the board unchanged\n","\n","    # generating a new index of the empty field\n","    delta_i, delta_j = move_map[move]\n","    new_zero_i, new_zero_j = zero_i + delta_i, zero_j + delta_j\n","\n","    # generating a new matrix representation of the board for a valid input move\n","    if new_zero_i >= 0 and new_zero_i <= 2 and new_zero_j >= 0 and new_zero_j <= 2:\n","        swap_block = board_matrix[(new_zero_i, new_zero_j)]\n","        board_matrix[(new_zero_i, new_zero_j)] = 0\n","        board_matrix[(zero_i, zero_j)] = swap_block\n","\n","    # \"flattening\" the new matrix and returning the results\n","    new_board = []\n","    for i in range(3):\n","        for j in range(3):\n","            new_board.append(board_matrix[(i,j)])\n","\n","    return tuple(new_board)\n","\n","\n","# NOTE - use this for generating neighbors if following the sample code\n","def expand_state(state):\n","    \"\"\"Generates all possible non-repeating states from the current one.\n","\n","    Parameters\n","    ----------\n","    state : tuple\n","        A pair with the following elements:\n","        - a tuple representation of the board (c.f. the `transform_board`\n","          function documentation for details)\n","        - a list containing the sequence of moves that have led to the current\n","          board from an initial state (from the first to the last move)\n","\n","    Returns\n","    -------\n","    list\n","        A list of length up to 4, containing all possible new states (pairs of\n","        board representations and corresponding lists of moves that have led to\n","        them) that can be generated from the input board, moving the empty\n","        field 'LEFT', 'RIGHT', 'UP' or 'DOWN'.\n","    \"\"\"\n","\n","    # unpacking of the states and the sequence of the past moves\n","    current_board, moves = state\n","\n","    # generating the previous board by a reversing the last move (if it exists)\n","    previous_board = ()\n","    if len(moves) > 0:\n","        previous_board = transform_board(current_board, move_inverse[moves[-1]])\n","\n","    # generating all possible next states\n","    expanded_states = []\n","    for move in move_map.keys():\n","        # generating the board\n","        new_board = transform_board(current_board,move)\n","        # validating the board\n","        if new_board != previous_board and new_board != current_board:\n","            new_moves = moves + [move] # update move history\n","            expanded_states.append((new_board, new_moves))\n","\n","    return expanded_states\n","\n","\n","def print_board(board):\n","    \"\"\"Helper function for printing out the board.\n","\n","    Parameters\n","    ----------\n","    board : tuple\n","        A tuple representation of the board (c.f. the `transform_board`\n","        function documentation for details).\n","    \"\"\"\n","\n","    block_map = {0:' ', 1:'1', 2:'2', 3:'3', 4:'4', 5:'5', 6:'6', 7:'7', 8:'8'}\n","    print('| '+' | '.join([block_map[x] for x in board[:3]])+' |')\n","    print('| '+' | '.join([block_map[x] for x in board[3:6]])+' |')\n","    print('| '+' | '.join([block_map[x] for x in board[6:]])+' |')"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# testing the way the states are generated\n","print('Current board (after moving the empty field DOWN before):')\n","print_board((8,1,3,0,2,4,7,6,5))\n","print('Previous board:')\n","print_board(transform_board((8,1,3,0,2,4,7,6,5),move_inverse['DOWN']))\n","print('\\n---------------\\n')\n","for state in expand_state(((8,1,3,0,2,4,7,6,5),['DOWN'])):\n","    board, moves = state\n","    print('Next possible board:')\n","    print_board(board)\n","    print('Sequence of corresponding moves from the current state:',moves,'\\n')"],"metadata":{"id":"DdXzaKuNqTep"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"00CPVueawhtl"},"source":["### __Exercise 3.1: Defining heuristics for solving the 8-puzzle using A\\* search__\n","- The cost of the current state is the number of moves from the initial board.\n","- Define possible heuristics for estimating the promise of the next possible moves.\n","- Possible options are for instance:\n"," 1. [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) - the number of blocks that are not in the goal position,\n"," 2. [Manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry) - sum of the vertical and horizontal distances of all blocks from their goal positions.\n","- Any other ideas?"]},{"cell_type":"code","metadata":{"scrolled":true,"id":"NMKKdAUVwhtm"},"source":["def hamming_distance(board, goal_board=(1,2,3,4,5,6,7,8,0)):\n","    \"\"\"Computes Hamming distance between given `board` and `goal_board`.\n","\n","    Parameters\n","    ----------\n","    board : tuple\n","        A tuple representation of the board for which the heuristric is to be\n","        computed (c.f. the `transform_board` function documentation for\n","        details).\n","    goal_board : tuple (optional, the default being the desired ordered\n","    configuration of the tiles)\n","        A tuple representation of the goal board.\n","\n","    Returns\n","    -------\n","    int\n","        The value of the Hamming distance between the input board and the\n","        desired goal configuration.\n","    \"\"\"\n","\n","    # infinity for invalid board formats\n","    if len(board) != len(goal_board):\n","        return float('inf')\n","\n","    distance = 0 # deault zero distance\n","\n","    # TODO - COMPLETE YOURSELVES (note: the flat representation of the board\n","    #        comes in handy here)\n","\n","    return distance\n","\n","\n","def manhattan_distance(board, goal_board=(1,2,3,4,5,6,7,8,0)):\n","    \"\"\"Computes Manhattan distance between given `board` and `goal_board`.\n","\n","    Parameters\n","    ----------\n","    board : tuple\n","        A tuple representation of the board for which the heuristric is to be\n","        computed (c.f. the `transform_board` function documentation for\n","        details).\n","    goal_board : tuple (optional, the default being the desired ordered\n","    configuration of the tiles)\n","        A tuple representation of the goal board.\n","\n","    Returns\n","    -------\n","    int\n","        The value of the Manhattan distance between the input board and the\n","        desired goal configuration.\n","    \"\"\"\n","\n","    # infinity for invalid board formats\n","    if len(board) != len(goal_board):\n","        return float('inf')\n","\n","    distance = 0 # default zero distance\n","\n","    # TODO - COMPLETE YOURSELVES (note: here it's more convenient to work with\n","    #        the matrix representation of the board)\n","\n","    return distance"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# testing the distances\n","board1 = (8,1,3,0,2,4,7,6,5)\n","board2 = (1,2,3,4,5,6,7,8,0)\n","print('Board 1:')\n","print_board(board1)\n","print('Board 2:')\n","print_board(board2)\n","print('-'*80)\n","print('Hamming distance from the goal:')\n","print('  - board 1:', hamming_distance(board1))\n","print('  - board 2:', hamming_distance(board2))\n","print('Manhattan distance from the goal:')\n","print('  - board 1:', manhattan_distance(board1))\n","print('  - board 2:', manhattan_distance(board2))"],"metadata":{"id":"W6zMCmguSk5Q"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"fEAZf_E8whtt"},"source":["### __Exercise 3.2: The actual 8-puzzle solution via A\\* search and the defined heuristics__\n","- Adapt the A\\* code for finding a path between towns from the previous exercises to this problem.\n","- Use the heuristics defined above."]},{"cell_type":"code","metadata":{"scrolled":true,"id":"NfsQH8aIwhtt"},"source":["def astar_search_8puzzle(starting_board, goal_board=(1,2,3,4,5,6,7,8,0),\n","                         h=hamming_distance):\n","    \"\"\"Uses the A* search to solve the 8 puzzle (find path to the goal).\n","\n","    Parameters\n","    ----------\n","    starting_board : tuple\n","        A tuple representation of the initial board (c.f. the `transform_board`\n","        function documentation for details).\n","    goal_board : tuple (optional, the default being the desired ordered\n","        configuration of the tiles)\n","    h : typing.Callable (i.e., a function)\n","        The heuristic to measure the promise of the boards for reaching the\n","        final configuration.\n","\n","\n","    Returns\n","    -------\n","    tuple\n","        A pair consisting of the following elements:\n","        - The solution state (i.e., the final board tuple representation and the\n","          sequence of moves that have led to it from the initial board\n","          configuration).\n","        - The number of states explored while finding the solution (i.e., the\n","          total number of nodes expanded in the implicit graph representing the\n","          search space).\n","    \"\"\"\n","\n","    frontier = PriorityQueue() # creating the queue\n","    starting_state = (starting_board, []) # initial board, no previous moves\n","    cost_so_far = {} # cost of explored board (number of moves from the start)\n","    cost_so_far[starting_board] = 0\n","\n","    frontier.put((h(starting_board, goal_board), starting_state))\n","    solution = None # final state (if it was reached)\n","    states_explored = 1 # number of searched states\n","\n","    # processing the queue until the goal is found or all states are explored\n","\n","    # TODO - COMPLETE YOURSELVES\n","\n","    return solution, states_explored\n","\n","\n","def print_solution(start, moves):\n","    \"\"\"Prints the path towards the solution.\n","\n","    Parameters\n","    ----------\n","    start : tuple\n","        A tuple representation of the initial board from which the game starts\n","        (c.f. the `transform_board` function documentation for details).\n","    moves : list\n","        A list of moves that have led from the initial board to the final\n","        solution.\n","    \"\"\"\n","\n","    current_board = start\n","    for move in moves:\n","        print_board(current_board)\n","        print()\n","        current_board = transform_board(current_board,move)\n","    print_board(current_board)"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# testing the search\n","start1 = (0, 1, 3, 4, 2, 5, 7, 8, 6) # has solution\n","start2 = (2, 4, 3, 1, 5, 6, 7, 8, 0) # has solution\n","start3 = (1, 2, 3, 4, 5, 7, 8, 6, 0) # has solution\n","start4 = (1, 2, 3, 4, 5, 6, 8, 7, 0) # no solution\n","for starting_board in [start1, start2, start3, start4]:\n","    print('Starting board:')\n","    print_board(starting_board)\n","    print('... searching with Hamming heuristic ...')\n","    solution_h, states_h = astar_search_8puzzle(starting_board,\n","                                                h=hamming_distance)\n","    print(f'  - searched {states_h} states')\n","    print('... searching with Manhattan heuristic ...')\n","    solution_m, states_m = astar_search_8puzzle(starting_board,\n","                                                h=manhattan_distance)\n","    print(f'  - searched {states_m} states')\n","    if solution_h: # testing for one solution only is OK if they exist at all\n","        print('Solution exists and looks like:')\n","        print_solution(starting_board, solution_h[1])\n","    else:\n","        print('No solution found.')\n","    print('-'*80)"],"metadata":{"id":"ClmzFoqpmKDe"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"collapsed":true,"id":"FioIHsEFwht3"},"source":["---\n","\n","#### _Final note_ - some materials used in this notebook are adapted works licensed by their original authors as follows:\n","- Romania map:\n"," - Adapted from [GitHub AIMA code](https://github.com/aimacode/aima-python/blob/master/search.ipynb)\n"," - Author: The [AIMA-Python](https://github.com/aimacode/aima-python/graphs/contributors) collective\n"," - License: [MIT](https://opensource.org/licenses/MIT)\n","- 8puzzle figure:\n"," - Adapted from [webu GeeksForGeeks](https://www.geeksforgeeks.org/8-puzzle-problem-using-branch-and-bound/)\n"," - Author: [unknown / GeeksForGeeks collective](contribute@geeksforgeeks.org)\n"," - Original source: [GeeksForGeeks](https://media.geeksforgeeks.org/wp-content/uploads/puzzle-1.jpg)\n"," - License: N/A"]}]}