A1: The k-Puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>CS152 Assignment 1: The 8-puzzle</h1>\n",
    "\n",
    "In this assignment, you are required to code a solution to the 8-puzzle, and its natural generalizations,\n",
    "applying the A∗ search algorithm with various admissible heuristics.\n",
    "\n",
    "<h2> Assignment Overview </h2>\n",
    "\n",
    "1. Design a python class named PuzzleNode with appropriate attributes and methods to capture the state of the 8-puzzle and its generalizations, as well as the elements needed to implement an A∗ search. Your class should also contain a parent attribute to point to a parent node, which can be used after search to reconstruct the optimal solution. It should also implement the method `str(__self__)` , which should print out a grid showing the board state.\n",
    "\n",
    "2. Define the skeleton of a function solvePuzzle that accepts three arguments and returns three values. It should be callable by using the syntax \n",
    "\n",
    "    $$steps, frontierSize, err = solvePuzzle(n, state, heuristic, prnt)$$\n",
    "\n",
    "    <u>Input Arguments:</u>\n",
    "    - n - the puzzle dimension (i.e. n x n board)\n",
    "    - state - the starting (scrambled) state of the puzzle, provided as a list of lists, with the blank space represented by the number 0. For example, for n=3, we could have state = [[7 2 4],[5 0 6],[8 3 1]] as in the image shown previously.\n",
    "    - heuristic - a handle to a heuristic function (more details in the next step)\n",
    "    - prnt - a boolean value that indicates whether or not to print the solution\n",
    "\n",
    "   <u> Output Arguments: </u>\n",
    "    - steps - the number of steps to optimally reach the goal state from the initial state\n",
    "    - frontierSize - the maximum (i.e. worst-case) size of the frontier during the search\n",
    "    - err - an error code (details given in the next step)\n",
    "\n",
    "   Your function must follow this exact template, since your implementation will be tested as needed using another python script.\n",
    "\n",
    "\n",
    "3. Implement the A∗ search within the body of solvePuzzle.\n",
    "\n",
    "    1. Your implementation should first test whether or not the state provided is of the correct size and format, and contains every number from $0$ to $n^{2} − 1$ precisely once. If any of these are not satisfied, then the function should return error code -1, and zeros for the remaining outputs steps and frontierSize. You may put the code for this test inside another function if you wish and call this function from within solvePuzzle.\n",
    "    \n",
    "    2. Next, define two heuristic functions based on the board state: the number of misplaced tiles and the Manhattan distance. The heuristic functions should take a list of lists for the board state as above and return a numerical value, using a function call of the form `val = h1(state)`. The heuristic functions will be passed into solvePuzzle as defined in step 2. Once you have defined your heuristic functions, create a list of function handles to point to them in the main workspace (i.e. not a local variable inside a function). Call this list heuristics. The idea is that calling heuristics[0](state) will return the number of misplaced tiles, and heuristics[1](state) will return the Manhattan distance. The automated testing script will call each heuristic in turn. In the extension activities to follow, you can append any custom heuristic functions onto the end of the list\n",
    "    \n",
    "    3. Define the remainder of the A∗ search, using an appropriate data structure for the frontier, making use of your PuzzleNode class. The implementation should check for repeated states and avoid expanding these (including simply undoing the previous move). It should also check if a better path to a previously-visited state has been found at any search step and modify the frontier, as well as the relevant attributes of the the node pointing to that step accordingly. You may use a similar method to those adopted in Lesson 3.1.\n",
    "    \n",
    "    4. After having completed the search, return the maximum frontier size and number of\n",
    "steps as required, and an error code of zero. If prnt is true, the function should additionally print out the states of the board (as lists of lists) from the initial scrambled state all\n",
    "the way to the goal, as well as the number of moves to reach the goal and the maximum\n",
    "frontier size. Each should be printed on its own line.\n",
    "\n",
    "\n",
    "4. Run your code from the following scrambled 3 × 3 boards:\n",
    "    - [[5,7,6],[2,4,3],[8,1,0]]\n",
    "    - [[7,0,8],[4,6,1],[5,3,2]]\n",
    "    - [[2,3,7],[1,8,0],[6,5,4]]\n",
    "    \n",
    "   Compare the performance of the two heuristics in terms of the number of moves and the frontier size from each of these initial conditions. You may automate this with another function if you wish. Document the results using a markdown cell if using a python notebook, or as a separate section in the PDF, making it clear which initial state lead to which result. Your code will be tested from other initial states also (with a possibly larger $n$) to ensure its correct operation\n",
    "   \n",
    "   \n",
    "<h3> Extensions </h3>\n",
    "\n",
    "1. [Extension to (3a)] If we were to simply place the numbers 1 - 8 in the nine squares of the 8-puzzle, we may end up in a configuration that is impossible to solve. However, we can show that this configuration can be resolved to a state that differs from the true solved state by switching the places of any two adjacent tiles, excluding the blank square (see exercise 3.4 in Russell & Norvig). In addition to testing the format and sizes of initial state provided, test whether or not the puzzle can actually be solved from that state in the first place in the solvePuzzlefunction, returning error code -2 if it cannot be solved.\n",
    "\n",
    "2. [Extension to (3b) and (4)] Design and implement another heuristic for the 8-puzzle that outperforms both of the heuristics tested previously. This could include other more sophisticated\n",
    "heuristics that have been investigated in the literature. Justify why this heuristic dominates\n",
    "both the number or misplaced tiles and the Manhattan distance, then implement your heuristic and compare its performance as in the basic requirements section. Extra kudos will be\n",
    "given for anyone who implements a heuristic based on a pattern database.\n",
    "\n",
    "3. [Extension to (3c)] Speed up the execution of the code by saving the heuristic values previously evaluated for a given state, to avoid the heuristic function being evaluated again for a\n",
    "different puzzle instance. You can use a python decorator for achieving this - this is known\n",
    "as memoization. What this means is that subsequent calls to solvePuzzle will be sped up by\n",
    "storing knowledge of the heuristic function from previous search runs. You could also use\n",
    "memoization for constructing a pattern database in extension question 2. Note that you are\n",
    "not required to store this information between successive runs of the python kernel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3582513581b2e5d1806ee2b1117ac019",
     "grade": false,
     "grade_id": "5bb4ce",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "<h1>\n",
    "Question 1    \n",
    "</h1>\n",
    "Define your <code>PuzzleNode</code> class below.  Ensure that you include all attributes that you need to implement an A* search.  If you wish, you can even include member functions, such as a function to generate successor states.  Alternatively, you can code up this functionality later in the <code>solvePuzzle</code> function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4326143183f9b58edcedbc64aed31100",
     "grade": false,
     "grade_id": "b5da05",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "#Import packages needed to implement A* search for 8 puzzle problem\n",
    "import itertools\n",
    "import numpy as np\n",
    "from copy import deepcopy\n",
    "import heapq\n",
    "import json\n",
    "import math\n",
    "from collections import deque\n",
    "\n",
    "#Now, define the class PuzzleNode:\n",
    "class PuzzleNode:\n",
    "    \n",
    "    \"\"\"\n",
    "    Class PuzzleNode: Provides a structure for performing A* search for the n^2-1 puzzle\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, state=[], parent= None, path_cost= 0, heuristic_cost= 0):\n",
    "        \n",
    "        \"\"\"\n",
    "        Class constructor to initialize attributes needed for A* search and solving the n^2-1 puzzle \n",
    "        \n",
    "        Inputs:\n",
    "            - state (list of lists): Current state of the puzzle board (default: [])\n",
    "            - parent: Pointer to parent node which was acted on to on to get current board state (default: None)\n",
    "            - path_cost: Cost of getting to current node from the initial node (default: 0)\n",
    "            - heuristic_cost: Estimated cost of going from current node to goal node as determined by a \n",
    "              specific heuristic function (default: 0)\n",
    "        \"\"\"\n",
    "        \n",
    "        self.state= state\n",
    "        self.parent= parent\n",
    "        self.path_cost= path_cost\n",
    "        self.h_cost= heuristic_cost\n",
    "        \n",
    "        #Estimated cost of the cheapest solution through the node\n",
    "        #This will be used for comparison to determine which node in the p_queue should be expanded\n",
    "        self.f_cost= path_cost+heuristic_cost  \n",
    "        \n",
    "        self.pruned = False #Indicate if node can be ignored during search\n",
    "     \n",
    "    def __lt__(self,other):\n",
    "        \"\"\"\n",
    "        Comparison function based on f_cost to be used by Priority Queue for ordering.\n",
    "        A smaller f_cost has higher priority\n",
    "        \"\"\"\n",
    "        return self.f_cost < other.f_cost\n",
    "    \n",
    "    def __str__(self):\n",
    "        \n",
    "        \"\"\"\n",
    "        Print out a grid showing the current board state\n",
    "        \"\"\"\n",
    "        return (\"\\n\".join(str(row).replace(',','').replace('[','|').replace(']','|') for row in self.state))\n",
    "                       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f523db3048f85be39ef3dc740b53fdba",
     "grade": false,
     "grade_id": "859d2c",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "<h1>\n",
    "Question 2    \n",
    "</h1>\n",
    "Define your heuristic functions using the templates below.  Ensure that you extend the <code>heuristics</code> list to include all the heuristic functions you implement.  Note that state will be given as a list of lists, so ensure your function accepts this format.  You may use packages like numpy if you wish within the functions themselves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "686c6cabd6955171ad70aa6fd37d31a9",
     "grade": false,
     "grade_id": "3fb850",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def memoize(func):\n",
    "    \"\"\"\n",
    "    Store the results of the decorated function for fast lookup and avoidance of recomputation\n",
    "    \"\"\"\n",
    "    \n",
    "    #Store the results in a dictionary that maps the argument (state) to results\n",
    "    cache= {}\n",
    "    \n",
    "    #Define the wrapper function to return\n",
    "    def wrapper(arg):\n",
    "        \n",
    "        #If the argument (in this case the state) has not been seen before\n",
    "        if str(arg) not in cache:\n",
    "            \n",
    "            #Call func() and store the result\n",
    "            cache[str(arg)]= func(arg)\n",
    "        \n",
    "        #Return the function value\n",
    "        return cache[str(arg)]\n",
    "    \n",
    "    return wrapper\n",
    "\n",
    "# Memoized Misplaced tiles heuristic\n",
    "@memoize\n",
    "def h1(state):\n",
    "    \"\"\"\n",
    "    This function returns the number of misplaced tiles, given the board state\n",
    "    \n",
    "    Input:\n",
    "        - state: the board state as a list of lists\n",
    "    Output:\n",
    "        - h: the number of misplaced tiles\n",
    "    \"\"\"\n",
    "    \n",
    "    #-Flatten state and pair up each tile in state with the corresponding goal tile in its position\n",
    "    #-Compare each tile with its matched goal tile and record mismatches\n",
    "    h = [goal_tile!= current_tile for (goal_tile,current_tile) in enumerate(itertools.chain(*state))]\n",
    "    \n",
    "    #Return the number of misplaced tiles (blank space (0) excluded)\n",
    "    return sum(h)-1\n",
    "    \n",
    "# Memoized Manhattan distance heuristic\n",
    "@memoize\n",
    "def h2(state):\n",
    "    \"\"\"\n",
    "    This function returns the Manhattan distance from the solved state, given the board state\n",
    "    Input:\n",
    "        - state: the board state as a list of lists\n",
    "    Output:\n",
    "        - h: the Manhattan distance from the solved configuration\n",
    "    \"\"\"\n",
    "    \n",
    "    #Get size of the board\n",
    "    board_size= len(state)\n",
    "    \n",
    "    #Determine the coordinate of each tile in the goal state\n",
    "    goal_coords= [(x, y) for x in range(board_size) for y in range(board_size)]\n",
    "    \n",
    "    #Assign the coordinate of a given tile to its tile value\n",
    "    goal_coords_dict= {tile: coordinate for tile,coordinate in enumerate(goal_coords)}\n",
    "    \n",
    "    #Initialize manhattan distance to 0\n",
    "    h= 0\n",
    "    \n",
    "    #Iterate through each tile in the current state\n",
    "    for x in range(board_size):\n",
    "        for y in range(board_size):\n",
    "            tile = state[x][y]\n",
    "            \n",
    "            #If not the blank space\n",
    "            if tile != 0:\n",
    "                \n",
    "                #Get the actual goal coordinate of the tile \n",
    "                goal_x, goal_y = goal_coords_dict[tile]\n",
    "                \n",
    "                #Calculate the vertical + horizontal distance from the tile to its goal position \n",
    "                h += abs(x - goal_x) + abs(y - goal_y)\n",
    "    \n",
    "    #Return the manhattan distance from the goal state\n",
    "    return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_pattern_db(n):\n",
    "    \n",
    "    \"\"\"\n",
    "    Create a pattern database for a given puzzle dimension n, storing all the subproblems in an external json file\n",
    "    \n",
    "    Input:\n",
    "        -n: size of puzzle\n",
    "        \n",
    "    \"\"\"\n",
    "    \n",
    "    #Calculate the number of possible puzzles from the goal states\n",
    "    #Only half of the possible permutations of the numbers are reachable from the goal state\n",
    "    num_states= math.factorial(n**2)/2\n",
    "    \n",
    "    #Generate goal state (in lists of lists form) for given dimensions\n",
    "    goal= [[x for x in range(row*n,(row*n)+n)] for row in range(n)]\n",
    "    \n",
    "    #Defining dependencies and begginning Breadth First Search (BFS) to compute all possible solutions\n",
    "    \n",
    "    #Initialize a frontier with the goal state and the current cost of 0\n",
    "    frontier= deque([[goal,0]])\n",
    "    \n",
    "    ##Initialize dictionaries to store explored states & solutions with the goal state\n",
    "    solutions, explored= {str(goal):0}, set()\n",
    "    \n",
    "    print(\"Generating pattern database....\")\n",
    "    print(\"Storing cost of solutions.....\")\n",
    "    \n",
    "    #While there are nodes in the frontier\n",
    "    while frontier:\n",
    "        \n",
    "        #Choose current first node in the frontier\n",
    "        node = frontier.popleft()\n",
    "        \n",
    "        #Get its state and the cost to get to the node from the goal state \n",
    "        state = node[0]\n",
    "        cost = node[1]\n",
    "        \n",
    "        #Add 1 to the cost as all the successor nodes that will be generated below incur an additional\n",
    "        #cost of 1 from the goal state\n",
    "        successor_cost= cost+1\n",
    "        \n",
    "        #Get the different successor states after performing all valid moves of the blank space\n",
    "        for successor in get_successors(state):\n",
    "                \n",
    "            #If the child node is already in the explored set, see if we need to update the path.\n",
    "            if str(successor) in explored:\n",
    "                if solutions[str(successor)] > successor_cost:\n",
    "                    solutions[str(successor)] = successor_cost \n",
    "                else:\n",
    "                    continue #Ignore this child, since a better path has been found previously.\n",
    "            \n",
    "            #If the child node has not been explored yet\n",
    "            else:\n",
    "                \n",
    "                #Add to the frontier, record the cost to get to the child node, and mark it as explored\n",
    "                frontier.append([successor,successor_cost])\n",
    "                solutions[str(successor)]= successor_cost\n",
    "                explored.add(str(successor))\n",
    "                \n",
    "        # Exit the loop when all permutations for the puzzle from the goal state have been found.\n",
    "        if len(solutions) >= num_states:\n",
    "            break\n",
    "    \n",
    "    print(\"Writing entries to external pattern database....\")\n",
    "    \n",
    "    # Write solutions to a json file.\n",
    "    with open('pattern_db.json', 'w') as fp:\n",
    "        json.dump(solutions, fp)\n",
    "    \n",
    "    print(\"\\n\")\n",
    "    print(\"Pattern database successfully generated.\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Discussion of Heuristic 3\n",
    "\n",
    "The third heuristic which implements a pattern database containing the exact number of moves (cost) to the goal state is guaranteed to outperform the two heuristics above in terms of node expansion for that exact reason. As the heuristic value for a node is exactly equal to the cost of moving from n to the goal, A* will behave perfectly (only follow the best path) and never expand anything else, making it very fast. This differs from the other heuristic values where A* could take wrong turns but will eventually still arrive at the optimal solution.\n",
    "\n",
    "#### Admissibility and Consistency of Heuristic 3\n",
    "\n",
    "It is clear that heuristic 3 is both admissible and consistent.\n",
    "\n",
    "With regards to admissibility, we see that the cost to the goal is never overestimated (but is exact in this case) for any node by the heuristic. Hence, f(n) never overestimates the true cost of a solution along the current path through n.\n",
    "\n",
    "As for consistency, since a uniform step cost was assigned in the precomputation of the solutions, we note that for every node $n$ and every successor $n'$ of $n$, the estimated cost of reaching the goal from $n$ is no greater than the step cost of getting to $n'$ plus the estimated cost of reaching the goal from $n'$.  \n",
    "\n",
    "It is important to note that the time taken to compute all solutions is quite significant. However, this is amortized after time through speedy lookup and accuracy of solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Create a set to note which databases have been created for heuristic 3 usage\n",
    "built_dbs= set()\n",
    "\n",
    "def h3(state):\n",
    "    \"\"\"\n",
    "    This function returns a heuristic that dominates the Manhattan distance, given the board state.\n",
    "    It is implemented with a pattern database which contains the precomputed distances from the goal state\n",
    "    to all possible states in this given puzzle. This distance will serve as the heuristic value\n",
    "    \n",
    "    \n",
    "    Input:\n",
    "        -state: the board state as a list of lists\n",
    "    Output:\n",
    "        -h: the heuristic distance of the state from its solved configuration\n",
    "        \n",
    "    Note: This should eventually work for all puzzle dimensions but will be impractical with board size > 3\n",
    "    \"\"\"\n",
    "    \n",
    "    #Create and load a pattern database for this particular puzzle dimension if it has not been \n",
    "    #previously created\n",
    "    if len(state) not in built_dbs:\n",
    "        create_pattern_db(len(state))\n",
    "        built_dbs.add(len(state))\n",
    "        \n",
    "        #Load the data into a dictionary called heuristic_vals and make it global to avoid recomputation\n",
    "        with open('pattern_db.json') as f:\n",
    "            global heuristic_vals\n",
    "            heuristic_vals = json.load(f)\n",
    "    \n",
    "    #Return the cost from the goal state of the inputted state\n",
    "    return heuristic_vals[str(state)]\n",
    "    \n",
    "#Memoized Linear conflict + Manhattan Distance\n",
    "@memoize\n",
    "def h4(state):\n",
    "    \"\"\"\n",
    "    This function returns the sum of the manhattan distance and the least number of moves required to \n",
    "    resolve all linear conflicts in the given state.\n",
    "    \n",
    "    LINEAR CONFLICT DESCRIPTION:\n",
    "    Two tiles ‘a’ and ‘b’ are in a linear conflict if they are in the same row or column,also their \n",
    "    goal positions are in the same row or column and the goal position of one of the tiles is blocked \n",
    "    by the other tile in that row.\n",
    "\n",
    "    Input:\n",
    "        -state: the board state as a list of lists\n",
    "    Output:\n",
    "        -h: the heuristic distance of the state from its solved configuration\n",
    "    \"\"\"\n",
    "    \n",
    "    #Get the dimension of the board\n",
    "    board_size= len(state)\n",
    "    \n",
    "    #Generate goal state (in lists of lists form) for given dimensions\n",
    "    goal= [[x for x in range(row*board_size,(row*board_size)+board_size)] for row in range(board_size)]\n",
    "    \n",
    "    \n",
    "    #Initialize counter to record the number of linear conflicts\n",
    "    sum_conflict = 0\n",
    "    \n",
    "    \n",
    "    ### CALCULTATING HORIZONTAL LINEAR CONFLICT (NO. OF LINEAR CONFLICTS ON EACH ROW)\n",
    "    \n",
    "    #For each row\n",
    "    for i in range(0, board_size):\n",
    "        #For each tile\n",
    "        for j in range(0, board_size):\n",
    "            \n",
    "            #If the not the blank tile\n",
    "            if state[i][j] != '0':\n",
    "                \n",
    "                #Check all consecutive tiles on the row\n",
    "                for k in range(j + 1, board_size):\n",
    "                    \n",
    "                    #If two tiles are on their goal row but are wrongly positioned, record linear conflict\n",
    "                    if state[i][k] != '0' \\\n",
    "                            and state[i][j] in goal[i] \\\n",
    "                            and state[i][k] in goal[i] \\\n",
    "                            and goal[i].index(state[i][j]) > goal[i].index(state[i][k]):\n",
    "                        sum_conflict += 1\n",
    "    \n",
    "    ### CALCULTATING VERTICAL LINEAR CONFLICT (NO. OF LINEAR CONFLICTS ON EACH COLUMN)\n",
    "    #For each column in the puzzle\n",
    "    for column in range(0, board_size):\n",
    "        #For each tile in a given column\n",
    "        for tile in range(0, board_size):\n",
    "            \n",
    "            #If not the blank tile\n",
    "            if state[tile][column] != '0':\n",
    "                \n",
    "                #Check all consecutive tiles on the column\n",
    "                for k in range(tile + 1, board_size):\n",
    "                    \n",
    "                    #Get current column\n",
    "                    current_column= list(zip(*goal))[column]\n",
    "                    \n",
    "                    #If two tiles are on their goal column but are wrongly positioned, record linear conflict\n",
    "                    if state[k][column] != '0' \\\n",
    "                            and state[tile][column] in current_column \\\n",
    "                            and state[k][column] in current_column \\\n",
    "                            and current_column.index(state[tile][column]) > current_column.index(\n",
    "                        state[k][column]):\n",
    "                        sum_conflict += 1\n",
    "        \n",
    "        \n",
    "    return h2(state) + 2*sum_conflict\n",
    "    \n",
    "# If you implement more than 3 heuristics, then add any extra heuristic functions onto the end of this list.\n",
    "heuristics = [h1, h2, h3, h4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "591174c27300d0a4d4d96ee841e46810",
     "grade": false,
     "grade_id": "e224d9",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "<h1>\n",
    "Question 3    \n",
    "</h1>\n",
    "Code up your A* search using the SolvePuzzle function within the template below.  Please do not modify the function header, otherwise the automated testing will fail.  You may define other functions or import packages as needed in this cell or by adding additional cells."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solvability_test(state):\n",
    "    \n",
    "    \"\"\"\n",
    "    Determine if a puzzle is solvable based on the number of inversions (total sum of the number of tiles with\n",
    "    lower numbers preceded by a tile with a larger number for each tile)of the board and the board width\n",
    "    \n",
    "    RULES FOR DETERMINATION (Ryan, 2004):\n",
    "    - If the grid width is odd, then the number of inversions in a solvable state is even.\n",
    "    - If the grid width is even, and the blank is on an even row counting from the bottom, then the number of\n",
    "      inversions in a solvable state is odd.\n",
    "    - If the grid width is even, and the blank is on an odd row counting from the bottom \n",
    "      (last, third-last, fifth-last,etc) then the number of inversions in a solvable state is even.\n",
    "      \n",
    "    Input:\n",
    "        - state (list of lists): the current state of the board\n",
    "    \n",
    "    Output:\n",
    "        - True or False (boolean): Returns True if Puzzle is solvable and False otherwise\n",
    "    \"\"\"\n",
    "    \n",
    "    #Check if the state is in the right format\n",
    "    if type(state) != list:\n",
    "        raise TypeError('State must be a list of lists')\n",
    "\n",
    "    #Initialize counter to record number of inversions. \n",
    "    inversions = 0\n",
    "    \n",
    "    #Get board with and the number of tiles\n",
    "    board_width = len(state)\n",
    "    num_tiles = board_width**2\n",
    "    \n",
    "    \n",
    "    #If the Puzzle is not in the right dimension, reshape it\n",
    "    state= np.array(state)\n",
    "    if state.shape != (board_width,board_width):\n",
    "        state = state.reshape(board_width, board_width) \n",
    "    \n",
    "    #Find the row of the blank space. This is necessary for checking solvability as outlined above\n",
    "    blank_tile_row = np.where(state==0)[0][0]\n",
    "    \n",
    "    #Flatten the state to a list to allow easy computation of inversions\n",
    "    tiles = [*state.flatten()]  \n",
    "    \n",
    "    #Calculate the number of inversions\n",
    "    for i in range(num_tiles - 1):\n",
    "        for j in range(i+1, num_tiles):\n",
    "            if (tiles[j] and tiles[i] != 0) and tiles[i] > tiles[j]:\n",
    "                inversions += 1\n",
    "                \n",
    "    #Scenarios for solvability as outlined above\n",
    "    \n",
    "    #Board of odd width and even number of inversions\n",
    "    if (board_width % 2 != 0) and (inversions % 2 == 0):\n",
    "        return True\n",
    "    \n",
    "    #Board of even width, blank on an even row counting from the bottom, and odd number of inversions\n",
    "    elif (board_width % 2 == 0) and (blank_tile_row % 2 != 0) and (inversions % 2 != 0):\n",
    "        return True \n",
    "    \n",
    "    #Board of even width, blank on an odd row counting from the bottom, and even number of inversions\n",
    "    elif (board_width % 2 == 0) and (blank_tile_row % 2 == 0) and (inversions % 2 == 0):\n",
    "        return True\n",
    "    \n",
    "    #If none of the cases above, the board is not solvable\n",
    "    else:\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_successors(state):\n",
    "    \n",
    "    \"\"\"\n",
    "    Generates successor states by moving blank space in possible directions given its current location.\n",
    "    \n",
    "    Input: \n",
    "        - state (list of lists): the current board state\n",
    "    \n",
    "    Output:\n",
    "        - successors_list: the possible successor board states after applying all possible actions\n",
    "    \"\"\"\n",
    "    \n",
    "    # Find the current coordinates of the blank tile\n",
    "    blank_position= np.where(np.array(state) == 0)\n",
    "    row,col = blank_position[0][0], blank_position[1][0]\n",
    "    \n",
    "    #Create list to store successor states\n",
    "    successors_list = []\n",
    "     \n",
    "    #Move blank space up if not on the first row\n",
    "    if row != 0: \n",
    "        \n",
    "        #Create a copy of the state to perform valid action on\n",
    "        next_state = deepcopy(state)\n",
    "        \n",
    "        #Move the blank space up and record the successor state\n",
    "        next_state[row][col], next_state[row-1][col] = next_state[row-1][col], next_state[row][col]\n",
    "        successors_list.append(next_state)\n",
    "    \n",
    "    #Move blank space left if not in the first column\n",
    "    if col != 0:\n",
    "        \n",
    "        #Create a copy of the state to perform valid action on\n",
    "        next_state = deepcopy(state)\n",
    "        \n",
    "        #Move the blank space left and record the successor state\n",
    "        next_state[row][col], next_state[row][col-1] = state[row][col-1], state[row][col]\n",
    "        successors_list.append(next_state)\n",
    "    \n",
    "    #Move blank space down if not on the last row\n",
    "    if row != len(state)-1: \n",
    "        \n",
    "        #Create a copy of the state to perform valid action on\n",
    "        next_state = deepcopy(state)\n",
    "        \n",
    "        #Move the blank space down and record the successor state\n",
    "        next_state[row][col], next_state[row+1][col] = state[row+1][col], state[row][col]\n",
    "        successors_list.append(next_state)\n",
    "\n",
    "    #Move blank space right if not in the last column\n",
    "    if col != len(state)-1: \n",
    "        \n",
    "        #Create a copy of the state to perform valid action on\n",
    "        next_state = deepcopy(state) \n",
    "        \n",
    "        #Move the blank space right and record the successor state\n",
    "        next_state[row][col], next_state[row][col+1] = state[row][col+1], state[row][col]\n",
    "        successors_list.append(next_state)\n",
    "    \n",
    "    #Return the list of successor states\n",
    "    return successors_list\n",
    "\n",
    "def generate_goal(state):\n",
    "    \n",
    "    \"\"\"\n",
    "    Generate the goal state for a Puzzle given its dimension\n",
    "    \n",
    "    Input:\n",
    "        - state (list of lists): the current state of the board\n",
    "    \"\"\"\n",
    "    \n",
    "    #Get the dimension of the board\n",
    "    board_size= len(state)\n",
    "    \n",
    "    #Generate goal state (in lists of lists form) for given dimensions\n",
    "    return [[x for x in range(row*board_size,(row*board_size)+board_size)] for row in range(board_size)]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "91dda09c4f5df1db4607bb3b82e81afd",
     "grade": false,
     "grade_id": "328d7b",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def solvePuzzle(state, heuristic, show= False):\n",
    "    \n",
    "    \"\"\"This function should solve the n**2-1 puzzle for any n > 2 (although it may take too long for n > 4)).\n",
    "    \n",
    "    A* n-puzzle solver, adapted from A* Search in Python for Robot Navigation (Session 3.1) by R. Shekhar(2017) \n",
    "    \n",
    "    Inputs:\n",
    "        -state: The initial state of the puzzle as a list of lists\n",
    "        -heuristic: a handle to a heuristic function.  Will be one of those defined in Question 2.\n",
    "        \n",
    "    Outputs:\n",
    "        -steps: The number of steps to optimally solve the puzzle (excluding the initial state)\n",
    "        -exp: The number of nodes expanded to reach the solution\n",
    "        -max_frontier: The maximum size of the frontier over the whole search\n",
    "        -opt_path: The optimal path as a list of list of lists.  That is, opt_path[:,:,i] should give a list of \n",
    "         lists that represents the state of the board at the ith step of the solution.\n",
    "        -err: An error code. If state is not of the appropriate size and dimension, return -1. For the extention \n",
    "         task, if the state is not solvable, then return -2\n",
    "    \"\"\"\n",
    "    \n",
    "    #Initialize relevant counters or variables\n",
    "    steps = 0\n",
    "    exp= 0\n",
    "    max_frontier = 0 \n",
    "    err = 0     \n",
    "    \n",
    "    \"\"\"\n",
    "    EXTENSION 1 INCLUDED BELOW IN THE FORM OF 'solvability_test' FUNCTION DEFINED ABOVE\n",
    "    \"\"\"\n",
    "    \n",
    "    #If the inputted Puzzle is not solvable\n",
    "    if solvability_test(state) is False:\n",
    "        print(\"Error. The inputted puzzle is not solvable.\")\n",
    "        opt_path, err = None,-2\n",
    "        return steps, exp, max_frontier, opt_path, err\n",
    "    \n",
    "    \n",
    "    #Checking for correct dimensions\n",
    "    board_size= len(state)\n",
    "        \n",
    "    #Check if the puzzle board is not a square (n*n) board\n",
    "    for row in state:\n",
    "        if len(row) != board_size:\n",
    "            opt_path, err = None,-1\n",
    "            return steps, exp, max_frontier, opt_path, err\n",
    "    \n",
    "    #Checking if the state contains the right numbers\n",
    "    \n",
    "    #The correct set of the numbers in sorted form (each number from 0 to n^2 − 1)\n",
    "    correct_state = [*range(board_size**2)]\n",
    "    \n",
    "    #The sorted form of the numbers in the current state\n",
    "    sorted_state= sorted([*itertools.chain(*state)])\n",
    "    \n",
    "    #Return False if the numbers in the sorted state is the not the correct set\n",
    "    if sorted_state != correct_state:\n",
    "        opt_path, err = None,-1\n",
    "        return steps, exp, max_frontier, opt_path, err\n",
    "    \n",
    "    \n",
    "    # Outlining dependencies and running the A* search algorithm:\n",
    "    \n",
    "    #Define the goal state for the given puzzle dimension\n",
    "    goal_state = generate_goal(state)\n",
    "    \n",
    "    #Define the initial/root node\n",
    "    initial_node = PuzzleNode(state,heuristic_cost=heuristic(state))\n",
    "    \n",
    "    #A dictionary to store visited PuzzleNodes. This prevents repeated states, including those which arise \n",
    "    #from simply undoing the previous move. \n",
    "    explored = {str(initial_node.state): initial_node}\n",
    "    \n",
    "    #Frontier, stored as a Priority Queue,\n",
    "    #Add initial node to the priority queue and increment frontier size\n",
    "    frontier = [initial_node]\n",
    "    \n",
    "    #While there are nodes in the frontier\n",
    "    while frontier:\n",
    "        \n",
    "        #Get the node with the highest priority (lowest f_cost)\n",
    "        current_node = heapq.heappop(frontier)\n",
    "        \n",
    "        #Check if node has been explored and marked for pruning\n",
    "        if current_node.pruned:\n",
    "            continue # Skip if it has\n",
    "        \n",
    "        # Check if the current_node is the goal state\n",
    "        if current_node.state == goal_state: \n",
    "            break #End loop if it is\n",
    "        \n",
    "        #Get successor states (by moving blank space in all possible directions)\n",
    "        successor_states = get_successors(current_node.state)\n",
    "        \n",
    "        #A node was expanded to yield successor states therefore increase the relevant counter\n",
    "        exp +=1\n",
    "        \n",
    "        # Evaluating the next moves\n",
    "        for successor in successor_states:\n",
    "            #Tentative path cost to reach the node\n",
    "            g_cost = current_node.path_cost + 1\n",
    "            \n",
    "            #If the child node is already in the explored set, see if we need to update the path.\n",
    "            if str(successor) in explored:\n",
    "                if explored[str(successor)].path_cost > g_cost:\n",
    "                    explored[str(successor)].pruned = True # Mark existing value for deletion from frontier\n",
    "                else:\n",
    "                    continue # ignore this child, since a better path has been found previously.\n",
    "                    \n",
    "            # Create new node for successor\n",
    "            child_node = PuzzleNode(successor, current_node, g_cost, heuristic(successor)) \n",
    "            \n",
    "            #Add the successor/child node to the frontier and keep the highest priority node at the top\n",
    "            #i.e. the node with the lowest f_cost\n",
    "            heapq.heappush(frontier, child_node)\n",
    "            \n",
    "            #Update the maximum frontier size\n",
    "            max_frontier= max(len(frontier), max_frontier)\n",
    "            \n",
    "            #Mark the child node as explored\n",
    "            explored[str(successor)] = child_node \n",
    "    \n",
    "    \n",
    "    #Print out the progression from the initial to the goal state (optimal path)\n",
    "    if show:\n",
    "        \n",
    "        # Compiling the optimal path to reach the goal state\n",
    "        opt_path = [current_node]\n",
    "        while current_node.parent: \n",
    "            opt_path.append((current_node.parent))\n",
    "            current_node = current_node.parent\n",
    "    \n",
    "        #Reverse the paths as we want the path from the initial to the goal state\n",
    "        opt_path.reverse()\n",
    "        \n",
    "        tag_str= ''\n",
    "        \n",
    "        for node in opt_path: \n",
    "            print(node,'\\n')\n",
    "            \n",
    "        opt_path= [node.state for node in opt_path]\n",
    "    \n",
    "    #If not show\n",
    "    else: \n",
    "        # Compiling the optimal path to reach the goal state\n",
    "        opt_path = [current_node.state]\n",
    "        while current_node.parent: \n",
    "            opt_path.append((current_node.parent).state)\n",
    "            current_node = current_node.parent\n",
    "    \n",
    "        #Reverse the paths as we want the path from the initial to the goal state\n",
    "        opt_path.reverse()\n",
    "    \n",
    "    return len(opt_path)-1, exp, max_frontier, opt_path, err\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "93712bce8426499023ace13735ea998d",
     "grade": false,
     "grade_id": "cell-3fc6e687e03655a1",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<h1>Extension Questions</h1>\n",
    "\n",
    "The extensions can be implemented by modifying the code from Q2-3 above appropriately.\n",
    "\n",
    "1. <b>Initial state solvability:</b>  Modify your SolvePuzzle function code in Q3 to return -2 if an initial state is not solvable to the goal state.\n",
    "2. <b>Extra heuristic function:</b> Add another heuristic function (e.g. pattern database) that dominates the misplaced tiles and Manhattan distance heuristics to your Q2 code.\n",
    "3. <b>Memoization:</b>  Modify your heuristic function definitions in Q2 by using a Python decorator to speed up heuristic function evaluation\n",
    "\n",
    "There are test cells provided for extension questions 1 and 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c89ea5c4d80cc73d321b4d15a043e8b7",
     "grade": false,
     "grade_id": "fb9ccd",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "<h1>Basic Functionality Tests</h1>\n",
    "The cells below contain tests to verify that your code is working properly to be classified as basically functional.  Please note that a grade of <b>3</b> on #aicoding and #search as applicable for each test requires the test to be successfully passed.  <b>If you want to demonstrate some other aspect of your code, then feel free to add additional cells with test code and document what they do.<b>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f8d927b41dc95f7b76d81ed7f6cd13ec",
     "grade": true,
     "grade_id": "8fbc24",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "## Test for state not correctly defined\n",
    "\n",
    "incorrect_state = [[0,1,2],[2,3,4],[5,6,7]]\n",
    "_,_,_,_,err = solvePuzzle(incorrect_state, lambda state: 0)\n",
    "assert(err == -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "005a7a99916dafeb7180172c66365597",
     "grade": true,
     "grade_id": "cell-5738a2124877e52e",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "## Heuristic function tests for misplaced tiles and manhattan distance\n",
    "\n",
    "# Define the working initial states\n",
    "working_initial_states_8_puzzle = ([[2,3,7],[1,8,0],[6,5,4]], [[7,0,8],[4,6,1],[5,3,2]], [[5,7,6],[2,4,3],[8,1,0]])\n",
    "\n",
    "# Test the values returned by the heuristic functions\n",
    "h_mt_vals = [7,8,7]\n",
    "h_man_vals = [15,17,18]\n",
    "\n",
    "for i in range(0,3):\n",
    "    h_mt = heuristics[0](working_initial_states_8_puzzle[i])\n",
    "    h_man = heuristics[1](working_initial_states_8_puzzle[i])\n",
    "    assert(h_mt == h_mt_vals[i])\n",
    "    assert(h_man == h_man_vals[i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "293094319e63d67c5f6d94cd7aee0c02",
     "grade": true,
     "grade_id": "cell-99c07d9541559b52",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "## A* Tests for 3 x 3 boards\n",
    "## This test runs A* with both heuristics and ensures that the same optimal number of steps are found\n",
    "## with each heuristic.\n",
    "\n",
    "# Optimal path to the solution for the first 3 x 3 state\n",
    "opt_path_soln = [[[2, 3, 7], [1, 8, 0], [6, 5, 4]], [[2, 3, 7], [1, 8, 4], [6, 5, 0]], \n",
    "                 [[2, 3, 7], [1, 8, 4], [6, 0, 5]], [[2, 3, 7], [1, 0, 4], [6, 8, 5]], \n",
    "                 [[2, 0, 7], [1, 3, 4], [6, 8, 5]], [[0, 2, 7], [1, 3, 4], [6, 8, 5]], \n",
    "                 [[1, 2, 7], [0, 3, 4], [6, 8, 5]], [[1, 2, 7], [3, 0, 4], [6, 8, 5]], \n",
    "                 [[1, 2, 7], [3, 4, 0], [6, 8, 5]], [[1, 2, 0], [3, 4, 7], [6, 8, 5]], \n",
    "                 [[1, 0, 2], [3, 4, 7], [6, 8, 5]], [[1, 4, 2], [3, 0, 7], [6, 8, 5]], \n",
    "                 [[1, 4, 2], [3, 7, 0], [6, 8, 5]], [[1, 4, 2], [3, 7, 5], [6, 8, 0]], \n",
    "                 [[1, 4, 2], [3, 7, 5], [6, 0, 8]], [[1, 4, 2], [3, 0, 5], [6, 7, 8]], \n",
    "                 [[1, 0, 2], [3, 4, 5], [6, 7, 8]], [[0, 1, 2], [3, 4, 5], [6, 7, 8]]]\n",
    "\n",
    "astar_steps = [17, 25, 28]\n",
    "for i in range(0,3):\n",
    "    steps_mt, expansions_mt, _, opt_path_mt, _ = solvePuzzle(working_initial_states_8_puzzle[i], heuristics[0])\n",
    "    steps_man, expansions_man, _, opt_path_man, _ = solvePuzzle(working_initial_states_8_puzzle[i], heuristics[1])\n",
    "    # Test whether the number of optimal steps is correct and the same\n",
    "    assert(steps_mt == steps_man == astar_steps[i])\n",
    "    # Test whether or not the manhattan distance dominates the misplaced tiles heuristic in every case\n",
    "    assert(expansions_man < expansions_mt)\n",
    "    # For the first state, test that the optimal path is the same\n",
    "    if i == 0:\n",
    "        assert(opt_path_mt == opt_path_soln)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "94ad7f950f87fcc281af1f3946c4e196",
     "grade": true,
     "grade_id": "cell-2981ba2cc7745c22",
     "locked": true,
     "points": 8,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "## A* Test for 4 x 4 board\n",
    "## This test runs A* with both heuristics and ensures that the same optimal number of steps are found\n",
    "## with each heuristic.\n",
    "\n",
    "working_initial_state_15_puzzle = [[1,2,6,3],[0,9,5,7],[4,13,10,11],[8,12,14,15]]\n",
    "steps_mt, expansions_mt, _, _, _ = solvePuzzle(working_initial_state_15_puzzle, heuristics[0])\n",
    "steps_man, expansions_man, _, _, _ = solvePuzzle(working_initial_state_15_puzzle, heuristics[1])\n",
    "# Test whether the number of optimal steps is correct and the same\n",
    "assert(steps_mt == steps_man == 9)\n",
    "# Test whether or not the manhattan distance dominates the misplaced tiles heuristic in every case\n",
    "assert(expansions_mt >= expansions_man)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "7251e4aad7b1e19b42a78e54d8e7b920",
     "grade": false,
     "grade_id": "cell-2c262efb90518641",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<h1>Extension Tests</h1>\n",
    "The cells below can be used to test the extension questions.  Memoization if implemented will be tested on the final submission - you can test it yourself by testing the execution time of the heuristic functions with and without it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "efc4b74c95e814a4fb07d2c5ed26f337",
     "grade": true,
     "grade_id": "cell-21cada9978e9a1bb",
     "locked": true,
     "points": 16,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error. The inputted puzzle is not solvable.\n"
     ]
    }
   ],
   "source": [
    "## Puzzle solvability test\n",
    "\n",
    "unsolvable_initial_state = [[7,5,6],[2,4,3],[8,1,0]]\n",
    "_,_,_,_,err = solvePuzzle(unsolvable_initial_state, lambda state: 0)\n",
    "assert(err == -2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9b7ebb02bcf675ab3a5157eaa1155763",
     "grade": true,
     "grade_id": "cell-8c7a414efc152379",
     "locked": true,
     "points": 32,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generating pattern database....\n",
      "Storing cost of solutions.....\n",
      "Writing entries to external pattern database....\n",
      "\n",
      "\n",
      "Pattern database successfully generated.\n"
     ]
    }
   ],
   "source": [
    "## Extra heuristic function test.  \n",
    "## This tests that for all initial conditions, the new heuristic dominates over the manhattan distance.\n",
    "\n",
    "dom = 0\n",
    "for i in range(0,3):\n",
    "    steps_new, expansions_new, _, _, _ = solvePuzzle(working_initial_states_8_puzzle[i], heuristics[2])\n",
    "    steps_man, expansions_man, _, _, _ = solvePuzzle(working_initial_states_8_puzzle[i], heuristics[1])\n",
    "    # Test whether the number of optimal steps is correct and the same\n",
    "    assert(steps_new == steps_man == astar_steps[i])\n",
    "    # Test whether or not the manhattan distance is dominated by the new heuristic in every case, by checking\n",
    "    # the number of nodes expanded\n",
    "    dom = expansions_man - expansions_new\n",
    "assert(dom > 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Domination of Heuristic 1&2 By 3\n",
    "\n",
    "From the above test, we see that the third heuristic (which is a precomputed exact solution) dominates the manhattan distance in all cases, and so in extension, it also dominates the misplaced tiles heuristic (which is dominated by the manhattan distance). More specifically, less nodes are expanded using heuristic 3 than heuristic 1 and 2. This is expected as heuristic three computes to exact cost to the goal state. Hence it leads A* on the perfect path with no needless node expanded. This differs from the manhattan and misplaces tiles heuristics which might traverse through unnessary nodes before eventually finding the optimal path. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-14-011f354e77a3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     11\u001b[0m     \u001b[0;31m# the number of nodes expanded\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[0mdom\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mexpansions_man\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mexpansions_new\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 13\u001b[0;31m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdom\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "## Extra heuristic function test.  \n",
    "## This tests that for all initial conditions, the new heuristic dominates over the manhattan distance.\n",
    "\n",
    "dom = 0\n",
    "for i in range(0,3):\n",
    "    steps_new, expansions_new, _, _, _ = solvePuzzle(working_initial_states_8_puzzle[i], heuristics[3])\n",
    "    steps_man, expansions_man, _, _, _ = solvePuzzle(working_initial_states_8_puzzle[i], heuristics[1])\n",
    "    # Test whether the number of optimal steps is correct and the same\n",
    "    assert(steps_new == steps_man == astar_steps[i])\n",
    "    # Test whether or not the manhattan distance is dominated by the new heuristic in every case, by checking\n",
    "    # the number of nodes expanded\n",
    "    dom = expansions_man - expansions_new\n",
    "assert(dom > 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear Conflict + Manhattan Distance vs. Manhattan Distances\n",
    "\n",
    "From the above test, we see that the linear conflict heuristic does not dominate the manhattan distance as the number of nodes expanded was actually larger than that of the manhattan distance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "af551e00bc8334100b7cf901ece597a2",
     "grade": true,
     "grade_id": "cell-09f710b6aa2e3fa3",
     "locked": true,
     "points": 64,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "## Memoization test - will be carried out after submission"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>References</h1>\n",
    "\n",
    "Ryan, M. (2004, November 26). Solvability of the tiles game. School of Computer Science - University of Birmingham. https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html"
   ]
  }
 ],
 "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.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}