Lab8_Puzzle_Single_Player_Game_(A-star) (1).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "h-47G4nF1lBG"
   },
   "source": [
    "<h1>8 Puzzle Single Player Game (A* Algorithm)</h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BXCcK4Il4p78"
   },
   "source": [
    "<h2>Introduction</h2>\n",
    "An instance of the n-puzzle game consists of a board holding $n^{2}-1$ distinct movable tiles, plus an empty space. The tiles are numbers from the set $1,..,n^{2}-1$. For any such board, the empty space may be legally swapped with any tile horizontally or vertically adjacent to it. In this assignment, the blank space is going to be represented with the number 0. Given an initial state of the board, the combinatorial search problem is to find a sequence of moves that transitions this state to the goal state; that is, the configuration with all tiles arranged in ascending order  $0,1,..,n^{2}-1$ . \n",
    "\n",
    "The search space is the set of all possible states reachable from the initial state. The blank space may be swapped with a component in one of the four directions {‘Up’, ‘Down’, ‘Left’, ‘Right’}, one move at a time. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NlVyyuFI2IyW"
   },
   "source": [
    "**A* Algorithm:** It is a searching algorithm that searches for the shortest path between the initial and the final state. It is used in various applications, such as maps. In maps the A* algorithm is used to calculate the shortest distance between the source (initial state) and the destination (final state)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HTDnbYRR6FrN"
   },
   "source": [
    "<h2>Explanation</h2>\n",
    "A* algorithm has 3 parameters:\n",
    "1.   g : the cost of moving from the initial cell to the current cell.\n",
    "2.   h : also known as the heuristic value, it is the estimated cost of moving from the current cell to the final cell. The actual cost cannot be calculated until the final cell is reached. Hence, h is the estimated cost. We must make sure that there is never an over estimation of the cost.\n",
    "3.   f : it is the sum of g and h. So, f = g + h\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "rcBUwpzpAcr-"
   },
   "outputs": [],
   "source": [
    "from time import time\n",
    "from queue import PriorityQueue\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "bBHJzbPW6pH-"
   },
   "outputs": [],
   "source": [
    "class Puzzle:\n",
    "    goal_state=[1,2,3,8,0,4,7,6,5]\n",
    "    heuristic=None\n",
    "    evaluation_function=None\n",
    "    needs_hueristic=False\n",
    "    num_of_instances=0\n",
    "    def __init__(self,state,parent,action,path_cost,needs_hueristic=False):\n",
    "        self.parent=parent\n",
    "        self.state=state\n",
    "        self.action=action\n",
    "        if parent:\n",
    "            self.path_cost = parent.path_cost + path_cost\n",
    "        else:\n",
    "            self.path_cost = path_cost\n",
    "        if needs_hueristic:\n",
    "            self.needs_hueristic=True\n",
    "            self.generate_heuristic()\n",
    "            self.evaluation_function=self.heuristic+self.path_cost\n",
    "        Puzzle.num_of_instances+=1\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.state[0:3])+'\\n'+str(self.state[3:6])+'\\n'+str(self.state[6:9])\n",
    "\n",
    "    def generate_heuristic(self):\n",
    "        self.heuristic=0\n",
    "        for num in range(1,9):\n",
    "            distance=abs(self.state.index(num) - self.goal_state.index(num))\n",
    "            i=int(distance/3)\n",
    "            j=int(distance%3)\n",
    "            self.heuristic=self.heuristic+i+j\n",
    "\n",
    "    def goal_test(self):\n",
    "        if self.state == self.goal_state:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    @staticmethod\n",
    "    def find_legal_actions(i,j):\n",
    "        legal_action = ['U', 'D', 'L', 'R']\n",
    "        if i == 0:  # up is disable\n",
    "            legal_action.remove('U')\n",
    "        elif i == 2:  # down is disable\n",
    "            legal_action.remove('D')\n",
    "        if j == 0:\n",
    "            legal_action.remove('L')\n",
    "        elif j == 2:\n",
    "            legal_action.remove('R')\n",
    "        return legal_action\n",
    "\n",
    "    def generate_child(self):\n",
    "        children=[]\n",
    "        x = self.state.index(0)\n",
    "        i = int(x / 3)\n",
    "        j = int(x % 3)\n",
    "        legal_actions=self.find_legal_actions(i,j)\n",
    "\n",
    "        for action in legal_actions:\n",
    "            new_state = self.state.copy()\n",
    "            if action is 'U':\n",
    "                new_state[x], new_state[x-3] = new_state[x-3], new_state[x]\n",
    "            elif action is 'D':\n",
    "                new_state[x], new_state[x+3] = new_state[x+3], new_state[x]\n",
    "            elif action is 'L':\n",
    "                new_state[x], new_state[x-1] = new_state[x-1], new_state[x]\n",
    "            elif action is 'R':\n",
    "                new_state[x], new_state[x+1] = new_state[x+1], new_state[x]\n",
    "            children.append(Puzzle(new_state,self,action,1,self.needs_hueristic))\n",
    "        return children\n",
    "\n",
    "    def find_solution(self):\n",
    "        solution = []\n",
    "        solution.append(self.action)\n",
    "        path = self\n",
    "        while path.parent != None:\n",
    "            path = path.parent\n",
    "            solution.append(path.action)\n",
    "        solution = solution[:-1]\n",
    "        solution.reverse()\n",
    "        return solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "WMcheK0f93H6"
   },
   "outputs": [],
   "source": [
    "def Astar_search(initial_state):\n",
    "    count=0\n",
    "    explored=[]\n",
    "    start_node=Puzzle(initial_state,None,None,0,True)\n",
    "    q = PriorityQueue()\n",
    "    q.put((start_node.evaluation_function,count,start_node))\n",
    "\n",
    "    while not q.empty():\n",
    "        node=q.get()\n",
    "        node=node[2]\n",
    "        explored.append(node.state)\n",
    "        if node.goal_test():\n",
    "            return node.find_solution()\n",
    "\n",
    "        children=node.generate_child()\n",
    "        for child in children:\n",
    "            if child.state not in explored:\n",
    "                count += 1\n",
    "                q.put((child.evaluation_function,count,child))\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 238
    },
    "colab_type": "code",
    "id": "YY1EiLOk95Du",
    "outputId": "570ac2b4-93f5-47bb-92b1-39a2a30cf2ac"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A*: ['U', 'R', 'U', 'L', 'D']\n",
      "space: 16\n",
      "time: 0.0\n",
      "\n",
      "A*: ['U', 'R', 'R', 'D', 'L', 'L', 'U', 'R', 'D']\n",
      "space: 42\n",
      "time: 0.0009860992431640625\n",
      "\n",
      "A*: ['R', 'U', 'L', 'U', 'R', 'R', 'D', 'L', 'L', 'U', 'R', 'D']\n",
      "space: 95\n",
      "time: 0.002992391586303711\n",
      "\n",
      "------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "#Start executing the 8-puzzle with setting up the initial state\n",
    "#Here we have considered 3 initial state intitalized using state variable\n",
    "state=[[1, 3, 4,\n",
    "        8, 6, 2,\n",
    "        7, 0, 5],\n",
    "\n",
    "       [2, 8, 1,\n",
    "        0, 4, 3,\n",
    "        7, 6, 5],\n",
    "\n",
    "       [2, 8, 1,\n",
    "        4, 6, 3,\n",
    "        0, 7, 5]]\n",
    "\n",
    "for i in range(0,3):\n",
    "    Puzzle.num_of_instances = 0\n",
    "    t0 = time()\n",
    "    astar = Astar_search(state[i])\n",
    "    t1 = time() - t0\n",
    "    print('A*:',astar)\n",
    "    print('space:', Puzzle.num_of_instances)\n",
    "    print('time:', t1)\n",
    "    print()\n",
    "print('------------------------------------------')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ii-7pr4I-fDu"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Solution_Lab2_8 Puzzle Single Player Game (BFS).ipynb",
   "provenance": []
  },
  "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": 1
}