AI - Lab 02 - 8 Puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Artificial Intelligence — Lab — Exercise 02"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Session 2: Uninformed & Informed Search Strategies — 8 - Puzzle Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26 August 2020"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a 3×3 board, 8 of the squares are filled with integers 1 to 9, and one square is left empty.\n",
    "One move is sliding into the empty square the integer in any one of its adjacent squares. The\n",
    "start state is given on the left side of the figure, and the goal state given on the right side. Find\n",
    "a sequence of moves to go from the start state to the goal state.\n",
    "1. Formulate the problem as a state space search problem.\n",
    "2. Find a suitable representation for the states and the nodes.\n",
    "3. Solve the problem using any of the uninformed search strategies.\n",
    "4. We can use Manhattan distance as a heuristic h(n). The cheapest cost from the current\n",
    "node to the goal node, can be estimated as how many moves will be required to transform the current node into the goal node. This is related to the distance each tile must\n",
    "travel to arrive at its destination, hence we sum the Manhattan distance of each square\n",
    "from its home position.\n",
    "5. An alternative heuristic should consider the number of tiles that are “out-of-sequence”.\n",
    "An out of sequence score can be computed as follows:<br>\n",
    "• a tile in the center counts 1,<br>\n",
    "• a tile not in the center counts 0 if it is followed by its proper successor as defined\n",
    "by the goal arrangement,<br>\n",
    "• otherwise, a tile counts 2.<br>\n",
    "6. Use anyone of the two heuristics, and implement Greedy Best-First Search.\n",
    "7. Use anyone of the two heuristics, and implement A* Search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initial State:     \n",
    "\n",
    "#### [7, 2, 4]    \n",
    "#### [5, 0, 6]\n",
    "#### [8, 3, 1]\n",
    "\n",
    "### Final State:\n",
    "#### [0, 1, 2]\n",
    "#### [3, 4, 5]\n",
    "#### [6, 7, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "import heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Puzzle_State:\n",
    "    \"\"\"Container class to hold the current state of the Puzzle.\"\"\"\n",
    "\n",
    "    parent = None\n",
    "    state = None\n",
    "    operation = None\n",
    "    zero = None\n",
    "    depth = 0\n",
    "    cost = 0\n",
    "    backward_cost = False\n",
    "\n",
    "    def __init__(self, state, parent = None, operation = None, depth = 0, backward_cost = False):\n",
    "        \"\"\"Default constructor.\"\"\"\n",
    "\n",
    "        self.parent = parent\n",
    "        self.state = state\n",
    "        self.operation = operation\n",
    "        self.zero = self.find_zero()\n",
    "        self.depth = depth\n",
    "        self.backward_cost = backward_cost\n",
    "\n",
    "        if backward_cost == True:       #for A* Search Algorithm, the backward-path cost is required\n",
    "            self.cost = self.depth + self.manhattan_distance()\n",
    "        else:                           #for Greedy BFS Algorithm, the backward-path cost is not required.\n",
    "            self.cost = self.manhattan_distance()\n",
    "\n",
    "\n",
    "    def __str__(self):\n",
    "        \"\"\"String notation of the Puzzle_State object.\"\"\"\n",
    "\n",
    "        return  str(self.state[:3]) + \"\\n\" \\\n",
    "            +   str(self.state[3:6]) + \"\\n\" \\\n",
    "            +   str(self.state[6:]) + \"\\n\"\n",
    "\n",
    "    def __lt__(self, another_board):\n",
    "        \"\"\"To override the < operator for the class with the cost function f(n) of the puzzle configuration.\"\"\"\n",
    "        \n",
    "        if self.cost == another_board.cost:\n",
    "            return self.depth < another_board.depth\n",
    "        return self.cost < another_board.cost\n",
    "\n",
    "    \n",
    "    def is_goal_state(self):\n",
    "        \"\"\"Checks if the goal state has been reached.\"\"\"\n",
    "\n",
    "        for i in range(0, len(self.state)):\n",
    "            if i == self.state[i]:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def find_zero(self):\n",
    "        \"\"\"Finds the index of 0 from the given state configuration.\"\"\"\n",
    "\n",
    "        for i in range(9):\n",
    "            if self.state[i] == 0:\n",
    "                return i\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        \"\"\"Swaps the ith element and jth element of the state configuration.\"\"\"\n",
    "\n",
    "        new_state = list(self.state)\n",
    "        new_state[i], new_state[j] = new_state[j], new_state[i]\n",
    "        return new_state\n",
    "\n",
    "    def move_up(self):\n",
    "        \"\"\"Moves a block up, if there is a zero in the appropriate position. \n",
    "        Returns None if configuration is not possible.\"\"\"\n",
    "\n",
    "        if self.zero > 2:\n",
    "            return Puzzle_State(self.swap(self.zero, self.zero-3), self, 'Up', self.depth+1, self.backward_cost)\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    def move_down(self):\n",
    "        \"\"\"Moves a block down, if there is a zero in the appropriate position. \n",
    "        Returns None if configuration is not possible.\"\"\"\n",
    "\n",
    "        if self.zero < 6:\n",
    "            return Puzzle_State(self.swap(self.zero, self.zero+3), self, 'Down', self.depth+1, self.backward_cost)\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    def move_left(self):\n",
    "        \"\"\"Moves a block left, if there is a zero in the appropriate position. \n",
    "        Returns None if configuration is not possible.\"\"\"\n",
    "\n",
    "        if self.zero % 3 != 0:\n",
    "            return Puzzle_State(self.swap(self.zero, self.zero-1), self, 'Left', self.depth+1, self.backward_cost)\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    def move_right(self):\n",
    "        \"\"\"Moves a block right, if there is a zero in the appropriate position. \n",
    "        Returns None if configuration is not possible.\"\"\"\n",
    "\n",
    "        if (self.zero + 1) % 3 != 0:\n",
    "            return Puzzle_State(self.swap(self.zero, self.zero+1), self, 'Right', self.depth+1, self.backward_cost)\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def find_next_states(self):\n",
    "        \"\"\"Finds the possible next state configurations based on the 4 available moves.\"\"\"\n",
    "\n",
    "        next_states = []\n",
    "        next_states.append(self.move_up())\n",
    "        next_states.append(self.move_down())\n",
    "        next_states.append(self.move_left())\n",
    "        next_states.append(self.move_right())\n",
    "\n",
    "        next_states = list(filter(None, next_states))\n",
    "\n",
    "        return next_states\n",
    "\n",
    "    def manhattan_distance(self):\n",
    "        \"\"\"Calculates the Heuristic Function h(n) based on the Manhattan Distance \n",
    "        between a block and it's final state position.\"\"\"\n",
    "\n",
    "        heuristic = 0\n",
    "\n",
    "        for i in range(len(self.state)):\n",
    "            if self.state[i] == 0:      #do not include the blank tile as part of the Manhattan distance.\n",
    "                continue\n",
    "                        #absolute vertical distance + absolute horizontal distance from it's goal position\n",
    "            heuristic += abs(self.state[i] // 3 - i // 3) + abs(self.state[i] % 3 - i % 3)\n",
    "\n",
    "        return heuristic\n",
    "\n",
    "    # def blocks_out_of_sequence(self):\n",
    "    #     \"\"\"Calculates the Heuristic Function h(n) based on the number of \n",
    "    #       blocks that are out of sequence from it's final state position.\"\"\"\n",
    "\n",
    "    #     heuristic = 0\n",
    "\n",
    "    #     for i in range(len(self.state)):\n",
    "    #         if self.state[i] != 0 and i == 4:                                   \n",
    "    #             heuristic += 1\n",
    "    #         elif i != 4 and i-1 > 0 and self.state[i] == self.state[i-1] + 1:  \n",
    "    #             heuristic += 0                                                  \n",
    "    #         else:                                                               \n",
    "    #             heuristic += 1\n",
    "        \n",
    "    #     return heuristic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Puzzle_Solver:\n",
    "    \"\"\"Container class that implements the functions to solve the 8-Puzzle board and trace the path.\"\"\"\n",
    "\n",
    "    solution = None\n",
    "    nodes_found = 0\n",
    "    current_depth = 0\n",
    "    no_of_moves = 0\n",
    "\n",
    "\n",
    "    def BFS(self, init_state):\n",
    "        \"\"\"Performs an uninformed BFS algorithm on the given initial Puzzle configuration.\"\"\"\n",
    "\n",
    "        frontier = deque()\n",
    "        visited = set()\n",
    "\n",
    "        frontier.append(init_state)\n",
    "        visited.add(tuple(init_state.state))\n",
    "\n",
    "        while frontier:\n",
    "            board = frontier.popleft()\n",
    "            #visited.add(tuple(board.state))\n",
    "\n",
    "            if board.is_goal_state():\n",
    "                self.solution = board\n",
    "                self.nodes_found = len(visited)\n",
    "                return self.solution\n",
    "            \n",
    "            for next_state in board.find_next_states():\n",
    "                if tuple(next_state.state) not in visited:\n",
    "                    frontier.append(next_state)\n",
    "                    visited.add(tuple(next_state.state))\n",
    "                    self.current_depth = max(self.current_depth, next_state.depth)\n",
    "            \n",
    "        return None\n",
    "\n",
    "    def a_star(self, init_state):\n",
    "        \"\"\"Performs an informed A* Search Algorithm on the given initial Puzzle configuration.\"\"\"\n",
    "\n",
    "        frontier = []\n",
    "        explored = set()\n",
    "        visited = set()\n",
    "\n",
    "        heapq.heappush(frontier, init_state)\n",
    "        visited.add(tuple(init_state.state))\n",
    "\n",
    "        while frontier:\n",
    "            board = heapq.heappop(frontier)\n",
    "            \n",
    "            if tuple(board.state) in explored:\n",
    "                continue\n",
    "\n",
    "            explored.add(tuple(board.state))\n",
    "\n",
    "            if board.is_goal_state():\n",
    "                self.solution = board\n",
    "                self.nodes_found = len(visited)\n",
    "                return self.solution\n",
    "            \n",
    "            for next_state in board.find_next_states():\n",
    "                if tuple(next_state.state) not in visited:\n",
    "                    heapq.heappush(frontier, next_state)\n",
    "                    visited.add(tuple(next_state.state))\n",
    "                    self.current_depth = max(self.current_depth, next_state.depth)\n",
    "                \n",
    "            \n",
    "        return None\n",
    "\n",
    "    def greedy_BFS(self, init_state):\n",
    "        \"\"\"Performs a Greedy Best-First Search Algorithm on the given initial Puzzle configuration.\"\"\"\n",
    "\n",
    "        frontier = []\n",
    "        explored = set()\n",
    "        visited = set()\n",
    "\n",
    "        heapq.heappush(frontier, init_state)\n",
    "        visited.add(tuple(init_state.state))\n",
    "\n",
    "        while frontier:\n",
    "            board = heapq.heappop(frontier)\n",
    "\n",
    "            if tuple(board.state) in explored:\n",
    "                continue\n",
    "\n",
    "            explored.add(tuple(board.state))\n",
    "\n",
    "            if board.is_goal_state():\n",
    "                self.solution = board\n",
    "                self.nodes_found = len(visited)\n",
    "                return self.solution\n",
    "\n",
    "            for next_state in board.find_next_states():\n",
    "                if tuple(next_state.state) not in visited:\n",
    "                    visited.add(tuple(next_state.state))\n",
    "                    heapq.heappush(frontier, next_state)\n",
    "                    self.current_depth = max(self.current_depth, next_state.depth)\n",
    "\n",
    "        \n",
    "        return None\n",
    "\n",
    "    def trace_path(self):\n",
    "        \"\"\"Traces the path taken by any search algorithm using the parent data member of the Puzzle object.\"\"\"\n",
    "\n",
    "        this_state = self.solution\n",
    "        path = [this_state]\n",
    "\n",
    "        while this_state.parent != None:\n",
    "            path.append(this_state.parent)\n",
    "            this_state = this_state.parent\n",
    "\n",
    "        self.no_of_moves = len(path) - 1\n",
    "\n",
    "        return path[::-1]\n",
    "\n",
    "    def print_report(self, algorithm):\n",
    "        \"\"\"Function to print the no. of explored states, depth of the path & \n",
    "        the path traced by the algorithm to get the goal state.\"\"\"\n",
    "\n",
    "        path = self.trace_path()\n",
    "\n",
    "        print(\"---------------------------------------------------------------------------------------------------\")\n",
    "        print(\"\\nNo. of States Visited\\t:\", self.nodes_found)\n",
    "        print(\"\\nDepth of {0}\\t: {1}\".format(algorithm, self.current_depth))\n",
    "        print(\"\\nNo. of Moves Taken\\t:\", self.no_of_moves)\n",
    "        print(\"\\nSolution Path:\\n\")\n",
    "        \n",
    "\n",
    "        for state in path:\n",
    "            print(\"Move :\", state.operation)\n",
    "            print(state, \"\\n\")\n",
    "        \n",
    "        print(\"---------------------------------------------------------------------------------------------------\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\t\t\tUninformed Search : Breadth-First Search\n",
      "\n",
      "---------------------------------------------------------------------------------------------------\n",
      "\n",
      "No. of States Visited\t: 177809\n",
      "\n",
      "Depth of BF Search\t: 27\n",
      "\n",
      "No. of Moves Taken\t: 26\n",
      "\n",
      "Solution Path:\n",
      "\n",
      "Move : None\n",
      "[7, 2, 4]\n",
      "[5, 0, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 2, 4]\n",
      "[0, 5, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 2, 4]\n",
      "[7, 5, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[2, 0, 4]\n",
      "[7, 5, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[2, 5, 4]\n",
      "[7, 0, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[2, 5, 4]\n",
      "[7, 3, 6]\n",
      "[8, 0, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[2, 5, 4]\n",
      "[7, 3, 6]\n",
      "[0, 8, 1]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[2, 5, 4]\n",
      "[0, 3, 6]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[2, 5, 4]\n",
      "[3, 0, 6]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[2, 5, 4]\n",
      "[3, 6, 0]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[2, 5, 0]\n",
      "[3, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[2, 0, 5]\n",
      "[3, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[0, 2, 5]\n",
      "[3, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 2, 5]\n",
      "[0, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[6, 0, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[6, 4, 0]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 2, 5]\n",
      "[6, 4, 1]\n",
      "[7, 8, 0]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 2, 5]\n",
      "[6, 4, 1]\n",
      "[7, 0, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 2, 5]\n",
      "[6, 0, 1]\n",
      "[7, 4, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[6, 1, 0]\n",
      "[7, 4, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 2, 0]\n",
      "[6, 1, 5]\n",
      "[7, 4, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 0, 2]\n",
      "[6, 1, 5]\n",
      "[7, 4, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[6, 0, 5]\n",
      "[7, 4, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[6, 4, 5]\n",
      "[7, 0, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[6, 4, 5]\n",
      "[0, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 1, 2]\n",
      "[0, 4, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 1, 2]\n",
      "[3, 4, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "---------------------------------------------------------------------------------------------------\n",
      "\n",
      "\t\t\tInformed Search : A* Search\n",
      "\n",
      "---------------------------------------------------------------------------------------------------\n",
      "\n",
      "No. of States Visited\t: 6172\n",
      "\n",
      "Depth of A* Search\t: 26\n",
      "\n",
      "No. of Moves Taken\t: 26\n",
      "\n",
      "Solution Path:\n",
      "\n",
      "Move : None\n",
      "[7, 2, 4]\n",
      "[5, 0, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 2, 4]\n",
      "[0, 5, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 2, 4]\n",
      "[7, 5, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[2, 0, 4]\n",
      "[7, 5, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[2, 5, 4]\n",
      "[7, 0, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[2, 5, 4]\n",
      "[7, 3, 6]\n",
      "[8, 0, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[2, 5, 4]\n",
      "[7, 3, 6]\n",
      "[0, 8, 1]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[2, 5, 4]\n",
      "[0, 3, 6]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[2, 5, 4]\n",
      "[3, 0, 6]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[2, 5, 4]\n",
      "[3, 6, 0]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[2, 5, 0]\n",
      "[3, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[2, 0, 5]\n",
      "[3, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[0, 2, 5]\n",
      "[3, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 2, 5]\n",
      "[0, 6, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[6, 0, 4]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[6, 4, 0]\n",
      "[7, 8, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 2, 5]\n",
      "[6, 4, 1]\n",
      "[7, 8, 0]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 2, 5]\n",
      "[6, 4, 1]\n",
      "[7, 0, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 2, 5]\n",
      "[6, 4, 1]\n",
      "[0, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 2, 5]\n",
      "[0, 4, 1]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[4, 0, 1]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 2, 5]\n",
      "[4, 1, 0]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 2, 0]\n",
      "[4, 1, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 0, 2]\n",
      "[4, 1, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[4, 0, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[0, 4, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 1, 2]\n",
      "[3, 4, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "---------------------------------------------------------------------------------------------------\n",
      "\n",
      "\t\t\tInformed Search : Greedy Best-First Search\n",
      "\n",
      "---------------------------------------------------------------------------------------------------\n",
      "\n",
      "No. of States Visited\t: 617\n",
      "\n",
      "Depth of Greedy BFS\t: 65\n",
      "\n",
      "No. of Moves Taken\t: 56\n",
      "\n",
      "Solution Path:\n",
      "\n",
      "Move : None\n",
      "[7, 2, 4]\n",
      "[5, 0, 6]\n",
      "[8, 3, 1]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[7, 2, 4]\n",
      "[5, 3, 6]\n",
      "[8, 0, 1]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[7, 2, 4]\n",
      "[5, 3, 6]\n",
      "[8, 1, 0]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[7, 2, 4]\n",
      "[5, 3, 0]\n",
      "[8, 1, 6]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[7, 2, 0]\n",
      "[5, 3, 4]\n",
      "[8, 1, 6]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 0, 2]\n",
      "[5, 3, 4]\n",
      "[8, 1, 6]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[0, 7, 2]\n",
      "[5, 3, 4]\n",
      "[8, 1, 6]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[5, 7, 2]\n",
      "[0, 3, 4]\n",
      "[8, 1, 6]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[5, 7, 2]\n",
      "[3, 0, 4]\n",
      "[8, 1, 6]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[5, 7, 2]\n",
      "[3, 1, 4]\n",
      "[8, 0, 6]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[5, 7, 2]\n",
      "[3, 1, 4]\n",
      "[0, 8, 6]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[5, 7, 2]\n",
      "[0, 1, 4]\n",
      "[3, 8, 6]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 7, 2]\n",
      "[5, 1, 4]\n",
      "[3, 8, 6]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[7, 0, 2]\n",
      "[5, 1, 4]\n",
      "[3, 8, 6]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[7, 1, 2]\n",
      "[5, 0, 4]\n",
      "[3, 8, 6]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 1, 2]\n",
      "[0, 5, 4]\n",
      "[3, 8, 6]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[7, 1, 2]\n",
      "[3, 5, 4]\n",
      "[0, 8, 6]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[7, 1, 2]\n",
      "[3, 5, 4]\n",
      "[8, 0, 6]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[7, 1, 2]\n",
      "[3, 5, 4]\n",
      "[8, 6, 0]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[7, 1, 2]\n",
      "[3, 5, 0]\n",
      "[8, 6, 4]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 1, 2]\n",
      "[3, 0, 5]\n",
      "[8, 6, 4]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[7, 1, 2]\n",
      "[3, 6, 5]\n",
      "[8, 0, 4]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 1, 2]\n",
      "[3, 6, 5]\n",
      "[0, 8, 4]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[7, 1, 2]\n",
      "[0, 6, 5]\n",
      "[3, 8, 4]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[7, 1, 2]\n",
      "[6, 0, 5]\n",
      "[3, 8, 4]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[7, 1, 2]\n",
      "[6, 5, 0]\n",
      "[3, 8, 4]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[7, 1, 2]\n",
      "[6, 5, 4]\n",
      "[3, 8, 0]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 1, 2]\n",
      "[6, 5, 4]\n",
      "[3, 0, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[7, 1, 2]\n",
      "[6, 5, 4]\n",
      "[0, 3, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[7, 1, 2]\n",
      "[0, 5, 4]\n",
      "[6, 3, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 1, 2]\n",
      "[7, 5, 4]\n",
      "[6, 3, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[1, 0, 2]\n",
      "[7, 5, 4]\n",
      "[6, 3, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[1, 5, 2]\n",
      "[7, 0, 4]\n",
      "[6, 3, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[1, 5, 2]\n",
      "[7, 3, 4]\n",
      "[6, 0, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[1, 5, 2]\n",
      "[7, 3, 4]\n",
      "[0, 6, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[1, 5, 2]\n",
      "[0, 3, 4]\n",
      "[7, 6, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[1, 5, 2]\n",
      "[3, 0, 4]\n",
      "[7, 6, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[1, 0, 2]\n",
      "[3, 5, 4]\n",
      "[7, 6, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[0, 1, 2]\n",
      "[3, 5, 4]\n",
      "[7, 6, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[0, 5, 4]\n",
      "[7, 6, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 1, 2]\n",
      "[5, 0, 4]\n",
      "[7, 6, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[5, 6, 4]\n",
      "[7, 0, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[5, 6, 4]\n",
      "[0, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 1, 2]\n",
      "[0, 6, 4]\n",
      "[5, 7, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 1, 2]\n",
      "[6, 0, 4]\n",
      "[5, 7, 8]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 1, 2]\n",
      "[6, 4, 0]\n",
      "[5, 7, 8]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[6, 4, 8]\n",
      "[5, 7, 0]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[6, 4, 8]\n",
      "[5, 0, 7]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[6, 4, 8]\n",
      "[0, 5, 7]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 1, 2]\n",
      "[0, 4, 8]\n",
      "[6, 5, 7]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 1, 2]\n",
      "[4, 0, 8]\n",
      "[6, 5, 7]\n",
      " \n",
      "\n",
      "Move : Down\n",
      "[3, 1, 2]\n",
      "[4, 5, 8]\n",
      "[6, 0, 7]\n",
      " \n",
      "\n",
      "Move : Right\n",
      "[3, 1, 2]\n",
      "[4, 5, 8]\n",
      "[6, 7, 0]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[3, 1, 2]\n",
      "[4, 5, 0]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[4, 0, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Left\n",
      "[3, 1, 2]\n",
      "[0, 4, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "Move : Up\n",
      "[0, 1, 2]\n",
      "[3, 4, 5]\n",
      "[6, 7, 8]\n",
      " \n",
      "\n",
      "---------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    \"\"\"Driver class to implement the 8-Puzzle Solver using different search algorithms.\"\"\"\n",
    "    \n",
    "    \n",
    "    print(\"\\n\\t\\t\\tUninformed Search : Breadth-First Search\\n\")\n",
    "    solver = Puzzle_Solver()\n",
    "    init_state = Puzzle_State([7, 2, 4, 5, 0, 6, 8, 3, 1])\n",
    "    solution = solver.BFS(init_state)\n",
    "    solver.print_report(\"BF Search\")\n",
    "    \n",
    "    print(\"\\n\\t\\t\\tInformed Search : A* Search\\n\")\n",
    "    solver = Puzzle_Solver()\n",
    "    init_state = Puzzle_State([7, 2, 4, 5, 0, 6, 8, 3, 1], backward_cost=True)\n",
    "    solution = solver.a_star(init_state)\n",
    "    solver.print_report(\"A* Search\")\n",
    "    \n",
    "    print(\"\\n\\t\\t\\tInformed Search : Greedy Best-First Search\\n\")\n",
    "    solver = Puzzle_Solver()\n",
    "    init_state = Puzzle_State([7, 2, 4, 5, 0, 6, 8, 3, 1])\n",
    "    solution = solver.greedy_BFS(init_state)\n",
    "    solver.print_report(\"Greedy BFS\")"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}