8Puzzle (4).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"./logo.png\" alt=\"Header\" align=\"right\" style=\"width: 100px;\"/>\n",
    "<center>\n",
    "    <font size=\"+2\">\n",
    "    <b>Artificial Intelligence<br></b>\n",
    "        <b>Project 1: 8-Puzzle</b>\n",
    "    </font>\n",
    "</center>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this project you will implement the informed version of A* to solve the 8 puzzle. You will implement 2 different heuristic measures as defined in the slides and report the results. You will also develop your own heuristic measure to solve this problem. For this you will need to implement these heuristic measures in the class State. You will also have to research how to create a priority queue in python and how you can make the class `State` comparable. \n",
    "\n",
    "1.1 Add a variable g that will hold the cumulative backward cost\n",
    "\n",
    "1.2 Implement the Tiles heuristic measure to compute h\n",
    "\n",
    "1.3 Implement the Manhattan heuristic to compute h\n",
    "\n",
    "1.4 Test both implementations and report the values for nodes visited and explored. \n",
    "\n",
    "1.5 Design you own heuristic measure and implement it (It has to be consistent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "class State:\n",
    "    def __init__(self,s, zero, prev=None,g=0):\n",
    "        self.s=s\n",
    "        self.prev=prev\n",
    "        self.zero=zero\n",
    "        self.hash=None\n",
    "        self.g=g\n",
    "        \n",
    "    def __hash__(self):\n",
    "        if self.hash:\n",
    "            return self.hash\n",
    "        s=0\n",
    "        for i in range(8,-1,-1):\n",
    "            s=10*s+self.s[i]\n",
    "        self.hash=s\n",
    "        return s\n",
    "        \n",
    "    #1,5,6\n",
    "    #2,0,3\n",
    "    #4,7,8\n",
    "    \n",
    "    #[1,5,6,2,0,3,4,7,8] zero=4\n",
    "    def Successors(self):\n",
    "        succ=[]\n",
    "        s=self.s\n",
    "        zero=self.zero\n",
    "        if (zero-1)>=0 and ((zero-1)//3==zero//3):\n",
    "            tmp=s.copy()\n",
    "            tmp[zero-1],tmp[zero]=s[zero],s[zero-1]\n",
    "            succ.append(State(tmp,zero-1,self,self.g+1))\n",
    "        if (zero+1<9) and ((zero+1)//3==zero//3):\n",
    "            tmp=s.copy()\n",
    "            tmp[zero+1],tmp[zero]=s[zero],s[zero+1]\n",
    "            succ.append(State(tmp,zero+1,self,self.g+1))\n",
    "        if (zero-3)>=0:\n",
    "            tmp=s.copy()\n",
    "            tmp[zero-3],tmp[zero]=s[zero],s[zero-3]\n",
    "            succ.append(State(tmp,zero-3,self,self.g+1))\n",
    "        if (zero+3)<=8:\n",
    "            tmp=s.copy()\n",
    "            tmp[zero+3],tmp[zero]=s[zero],s[zero+3]\n",
    "            succ.append(State(tmp,zero+3,self,self.g+1))\n",
    "        \n",
    "        return succ\n",
    "    \n",
    "    def IsGoal(self):\n",
    "        solution=[1,2,3,4,5,6,7,8,0]\n",
    "        s=self.s\n",
    "        for i in range(9):\n",
    "            if s[i]!=solution[i]:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        for i in range(9):\n",
    "            if self.s[i]!=other.s[i]:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        if self.g + self.ImprovedH() < other.g + other.ImprovedH(): #We substitute self.ImprovedH() and other.ImprovedH() with self.TilesH()/self.ManhattanH() and other.TilesH()/other.ManhattanH() in order to use the Tiles Heuristic/Manhattan Distance instead of the Improved Heuristic\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    \n",
    "    def __str__(self):\n",
    "        \n",
    "        tmp=np.array(self.s)\n",
    "        return str(tmp.reshape(3,3))\n",
    "    \n",
    "    \n",
    "    \n",
    "    def TilesH(self):\n",
    "        solution=[1,2,3,4,5,6,7,8,0]\n",
    "        h=0\n",
    "        for i in range(9):\n",
    "            if self.s[i]!=solution[i]:\n",
    "                h=h+1       \n",
    "        return h\n",
    "    \n",
    "    \n",
    "    \n",
    "    def ManhattanH(self):\n",
    "        solution=[1,2,3,4,5,6,7,8,0]\n",
    "        h=0\n",
    "        for i in range(9):\n",
    "            x1=i%3\n",
    "            y1=i//3\n",
    "            target=solution.index(self.s[i]) #7\n",
    "            x2=target%3\n",
    "            y2=target//3\n",
    "            h=h+abs(y1-y2)+abs(x1-x2)\n",
    "            \n",
    "        return h\n",
    "    \n",
    "    def ImprovedH(self):\n",
    "        solution=[1,2,3,4,5,6,7,8,0]\n",
    "        h=0\n",
    "        for i in range(9):\n",
    "            if self.s[i]!=solution[i]:\n",
    "                h=h+1\n",
    "        for i in range(9):\n",
    "            x1=i%3\n",
    "            y1=i//3\n",
    "            target=solution.index(self.s[i]) #7\n",
    "            x2=target%3\n",
    "            y2=target//3\n",
    "            h=h+abs(y1-y2)+abs(x1-x2)\n",
    "            \n",
    "            \n",
    "        return h\n",
    "    \n",
    "    \n",
    "                \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Solution(state):\n",
    "    path=[]\n",
    "    length=0\n",
    "    while state:\n",
    "        path.append(str(state))\n",
    "        state=state.prev\n",
    "        length=length+1\n",
    "    return ('\\n'.join(path), length)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A*\n",
    "\n",
    "Change the following code to implement the A* algorithm. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "7\n",
      "[[1 2 3]\n",
      " [4 5 6]\n",
      " [7 8 0]]\n",
      "[[1 2 3]\n",
      " [4 5 0]\n",
      " [7 8 6]]\n",
      "[[1 2 3]\n",
      " [4 0 5]\n",
      " [7 8 6]]\n",
      "[[1 2 3]\n",
      " [0 4 5]\n",
      " [7 8 6]]\n",
      "[[0 2 3]\n",
      " [1 4 5]\n",
      " [7 8 6]]\n",
      "[[2 0 3]\n",
      " [1 4 5]\n",
      " [7 8 6]]\n",
      "[[2 4 3]\n",
      " [1 0 5]\n",
      " [7 8 6]]\n",
      "[[2 4 3]\n",
      " [0 1 5]\n",
      " [7 8 6]]\n",
      "[[2 4 3]\n",
      " [7 1 5]\n",
      " [0 8 6]]\n",
      "[[2 4 3]\n",
      " [7 1 5]\n",
      " [8 0 6]]\n",
      "[[2 4 3]\n",
      " [7 0 5]\n",
      " [8 1 6]]\n",
      "[[2 4 3]\n",
      " [7 5 0]\n",
      " [8 1 6]]\n",
      "[[2 4 0]\n",
      " [7 5 3]\n",
      " [8 1 6]]\n",
      "[[2 0 4]\n",
      " [7 5 3]\n",
      " [8 1 6]]\n",
      "[[0 2 4]\n",
      " [7 5 3]\n",
      " [8 1 6]]\n",
      "[[7 2 4]\n",
      " [0 5 3]\n",
      " [8 1 6]]\n",
      "[[7 2 4]\n",
      " [5 0 3]\n",
      " [8 1 6]]\n",
      "[[7 2 4]\n",
      " [5 3 0]\n",
      " [8 1 6]]\n",
      "[[7 2 4]\n",
      " [5 3 6]\n",
      " [8 1 0]]\n",
      "[[7 2 4]\n",
      " [5 3 6]\n",
      " [8 0 1]]\n",
      "[[7 2 4]\n",
      " [5 0 6]\n",
      " [8 3 1]]\n",
      "Moves: 21\n",
      "Visited states: 166\n",
      "Explored: 278\n"
     ]
    }
   ],
   "source": [
    "start=State([7,2,4,5,0,6,8,3,1],4)\n",
    "print(start.ManhattanH())\n",
    "print(start.TilesH())\n",
    "visited=set()\n",
    "solved=False\n",
    "from collections import deque\n",
    "from queue import PriorityQueue\n",
    "q = PriorityQueue() \n",
    "q.put(start)\n",
    "i=0\n",
    "while not q.empty():\n",
    "    i=i+1\n",
    "    current=q.get()\n",
    "    if current.IsGoal():\n",
    "        path, length= Solution(current)\n",
    "        print(path)\n",
    "        print(\"Moves: \"+str(length))\n",
    "        solved=True\n",
    "        break\n",
    "    if current in visited:\n",
    "        continue\n",
    "    visited.add(current)\n",
    "    for tmp in current.Successors():\n",
    "        q.put(tmp)\n",
    "    \n",
    "if not solved: \n",
    "    print(\"No Solution\")\n",
    "\n",
    "print(\"Visited states: \"+str(len(visited)))\n",
    "print(\"Explored: \"+str(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fill the values here\n",
    "\n",
    "Nodes Visited (Tiles): 3396 \n",
    "\n",
    "Nodes Visited (Manhattan): 465\n",
    "\n",
    "Nodes Visited (Yours): 166\n",
    "\n",
    "Nodes Explored (Tiles): 5651\n",
    "\n",
    "Nodes Explored (Manhattan): 766\n",
    "\n",
    "Nodes Explored (Yours): 278\n",
    "\n",
    "Name 1 : Wolf Assi\n",
    "\n",
    "Name 2 : Raoul Boulos\n",
    "\n",
    "Name 3 : Joe Mechref"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SO we know that between 2 heuristic, the one that is less relaxed is better because we do not want to go very far from the actual answer which is the actual amount of steps that we need to take in order to solve the puzzle. Now we know that the Tiles heuristics has the smalles \"h\" and that the Manhattan Distance has a slightly superior \"h\" so we decided to sum the\"h\" of both of them. In that case would have incremented h and got closer to the actual solution of the program."
   ]
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}