Practical 5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Practical 5 : Write a program to Implement A* Algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "class Node(object):\n",
    "    \"\"\"For state representation\"\"\"\n",
    "    n = 0\n",
    "    def __init__(self, board,prev_state = None):\n",
    "        assert len(board) == 9\n",
    "        self.board = board[:];\n",
    "        self.prev = prev_state\n",
    "        self.step = 0\n",
    "        Node.n += 1\n",
    "        if self.prev:\n",
    "            self.step = self.prev.step + 1\n",
    "\n",
    "\n",
    "    def __eq__(self,other):\n",
    "        return self.board == other.board\n",
    "\n",
    "    def __hash__(self):\n",
    "        h = [0,0,0]\n",
    "        h[0] = self.board[0] << 6 | self.board[1] << 3 | self.board[2]\n",
    "        h[1] = self.board[3] << 6 | self.board[4] << 3 | self.board[5]\n",
    "        h[2] = self.board[6] << 6 | self.board[7] << 3 | self.board[8]\n",
    "        h_val = 0\n",
    "        for h_i in h:\n",
    "            h_val = h_val *31 + h_i\n",
    "        return h_val\n",
    "\n",
    "    def __str__(self):\n",
    "        string_list = [str(i) for i in self.board]\n",
    "        sub_list = (string_list[:3],string_list[3:6],string_list[6:])\n",
    "        return \"\\n\".join([\"\".join(l)for l in sub_list ])\n",
    "\n",
    "    def manhattan_distance(self):\n",
    "        distance = 0\n",
    "        goal = [1,2,3,4,5,6,7,8,0]\n",
    "        for i in range(1,9):\n",
    "            xs,ys = self.pos(self.board.index(i))\n",
    "            xg,yg = self.pos(goal.index(i))\n",
    "            distance += abs(xs-xg) + abs(ys-yg)\n",
    "        return distance\n",
    "\n",
    "    def hamming_distance(self):\n",
    "        distance = 0\n",
    "        goal = [1,2,3,4,5,6,7,8,0]\n",
    "        for i in range(9):\n",
    "            if goal[i] != self.board[i]: distance += 1\n",
    "        return distance\n",
    "\n",
    "    def next(self):\n",
    "        next_moves = []\n",
    "        i = self.board.index(0)\n",
    "        next_moves = (self.moveUp(i),self.moveDown(i),self.moveRight(i),self.moveLeft(i))\n",
    "        return [s for s in next_moves if s]\n",
    "\n",
    "\n",
    "    def moveLeft(self,i):\n",
    "        x,y = self.pos(i)\n",
    "        if y > 0:\n",
    "            left_state = Node(self.board,self)\n",
    "            left = self.sop(x,y-1)\n",
    "            left_state.swap(i,left)\n",
    "            return left_state\n",
    "\n",
    "    def moveRight(self,i):\n",
    "        x,y = self.pos(i)\n",
    "        if y < 2 :\n",
    "            right_state = Node(self.board,self)\n",
    "            right = self.sop(x,y+1)\n",
    "            right_state.swap(i,right)\n",
    "            return right_state\n",
    "\n",
    "    def moveUp(self,i):\n",
    "        x,y = self.pos(i)\n",
    "        if x > 0:\n",
    "            up_state = Node(self.board,self)\n",
    "            up = self.sop(x-1,y)\n",
    "            up_state.swap(i,up)\n",
    "            return up_state\n",
    "\n",
    "    def moveDown(self , i):\n",
    "        x,y = self.pos(i)\n",
    "        if x < 2 :\n",
    "            down_state = Node(self.board,self)\n",
    "            down = self.sop(x+1,y)\n",
    "            down_state.swap(i,down)\n",
    "            return down_state\n",
    "\n",
    "    def swap(self,i,j):\n",
    "        self.board[j],self.board[i] = self.board[i],self.board[j]\n",
    "\n",
    "    def pos(self,index):\n",
    "        return (int(index/3),index%3)\n",
    "\n",
    "\n",
    "    def sop(self,x,y):\n",
    "        return x * 3 + y\n",
    "\n",
    "class PriorityQueue:\n",
    "    def  __init__(self):\n",
    "        self.heap = []\n",
    "        self.count = 0\n",
    "\n",
    "    def push(self, item, priority):\n",
    "        entry = (priority, self.count, item)\n",
    "        heapq.heappush(self.heap, entry)\n",
    "        self.count += 1\n",
    "\n",
    "    def pop(self):\n",
    "        (_, _, item) = heapq.heappop(self.heap)\n",
    "        return item\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return len(self.heap) == 0\n",
    "\n",
    "def printPath(state):\n",
    "    path = []\n",
    "    while state:\n",
    "        path.append(state)\n",
    "        state = state.prev\n",
    "    path.reverse()\n",
    "    print(\"\\n    \\n\".join([str(state) for state in path]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8-puzzle solution using A*\n",
      "201\n",
      "453\n",
      "876\n",
      "    \n",
      "021\n",
      "453\n",
      "876\n",
      "    \n",
      "421\n",
      "053\n",
      "876\n",
      "    \n",
      "421\n",
      "503\n",
      "876\n",
      "    \n",
      "421\n",
      "573\n",
      "806\n",
      "    \n",
      "421\n",
      "573\n",
      "086\n",
      "    \n",
      "421\n",
      "073\n",
      "586\n",
      "    \n",
      "421\n",
      "703\n",
      "586\n",
      "    \n",
      "401\n",
      "723\n",
      "586\n",
      "    \n",
      "410\n",
      "723\n",
      "586\n",
      "    \n",
      "413\n",
      "720\n",
      "586\n",
      "    \n",
      "413\n",
      "726\n",
      "580\n",
      "    \n",
      "413\n",
      "726\n",
      "508\n",
      "    \n",
      "413\n",
      "726\n",
      "058\n",
      "    \n",
      "413\n",
      "026\n",
      "758\n",
      "    \n",
      "013\n",
      "426\n",
      "758\n",
      "    \n",
      "103\n",
      "426\n",
      "758\n",
      "    \n",
      "123\n",
      "406\n",
      "758\n",
      "    \n",
      "123\n",
      "456\n",
      "708\n",
      "    \n",
      "123\n",
      "456\n",
      "780\n",
      "Find solution\n"
     ]
    }
   ],
   "source": [
    "def astar(start,goal):\n",
    "    depth = 75\n",
    "    priotity_queue = PriorityQueue()\n",
    "    h_val = start.manhattan_distance() + start.hamming_distance()\n",
    "\n",
    "    f_val = h_val + start.step\n",
    "    priotity_queue.push(start, f_val)\n",
    "    visited = set()\n",
    "    found = False\n",
    "    while not priotity_queue.isEmpty():\n",
    "        state = priotity_queue.pop()\n",
    "        if state == goal:\n",
    "            found = state\n",
    "            break\n",
    "\n",
    "        if state in visited or state.step > depth:\n",
    "            continue\n",
    "\n",
    "        visited.add(state)\n",
    "\n",
    "        for s in state.next():\n",
    "            h_val_s = s.manhattan_distance() + s.hamming_distance()\n",
    "            f_val_s = h_val_s + s.step\n",
    "            priotity_queue.push(s, f_val_s)\n",
    "\n",
    "    if found:\n",
    "        printPath(found)\n",
    "        print(\"Find solution\")\n",
    "    else:\n",
    "        print(\"No solution found\")\n",
    "\n",
    "print(\"8-puzzle solution using A*\")\n",
    "start = Node([2,0,1,4,5,3,8,7,6])\n",
    "goal = Node([1,2,3,4,5,6,7,8,0])\n",
    "astar(start,goal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "",
   "title_sidebar": "",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}