 8Puzzle by Group 12.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "[1, 2, 3]\n",
      "[0, 4, 6]\n",
      "[7, 5, 8]\n",
      "\n",
      "R\n",
      "[1, 2, 3]\n",
      "[4, 0, 6]\n",
      "[7, 5, 8]\n",
      "\n",
      "D\n",
      "[1, 2, 3]\n",
      "[4, 5, 6]\n",
      "[7, 0, 8]\n",
      "\n",
      "R\n",
      "[1, 2, 3]\n",
      "[4, 5, 6]\n",
      "[7, 8, 0]\n",
      "\n",
      "Total number of steps: 4\n",
      "Total amount of time in search: 0.0004899000000015974 second(s)\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\Alou\\Anaconda\\envs\\tf\\lib\\site-packages\\ipykernel_launcher.py:198: DeprecationWarning: time.clock has been deprecated in Python 3.3 and will be removed from Python 3.8: use time.perf_counter or time.process_time instead\n",
      "C:\\Users\\Alou\\Anaconda\\envs\\tf\\lib\\site-packages\\ipykernel_launcher.py:200: DeprecationWarning: time.clock has been deprecated in Python 3.3 and will be removed from Python 3.8: use time.perf_counter or time.process_time instead\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import itertools\n",
    "import collections\n",
    "import time\n",
    "\n",
    "class Node:\n",
    "    \"\"\"\n",
    "    A class representing an Solver node\n",
    "    - 'puzzle' is a Puzzle instance\n",
    "    - 'parent' is the preceding node generated by the solver, if any\n",
    "    - 'action' is the action taken to produce puzzle, if any\n",
    "    \"\"\"\n",
    "    def __init__(self, puzzle, parent=None, action=None):\n",
    "        self.puzzle = puzzle\n",
    "        self.parent = parent\n",
    "        self.action = action\n",
    "        if (self.parent != None):\n",
    "            self.g = parent.g + 1\n",
    "        else:\n",
    "            self.g = 0\n",
    "\n",
    "    @property\n",
    "    def score(self):\n",
    "        return (self.g + self.h)\n",
    "\n",
    "    @property\n",
    "    def state(self):\n",
    "        \"\"\"\n",
    "        Return a hashable representation of self\n",
    "        \"\"\"\n",
    "        return str(self)\n",
    "\n",
    "    @property \n",
    "    def path(self):\n",
    "        \"\"\"\n",
    "        Reconstruct a path from to the root 'parent'\n",
    "        \"\"\"\n",
    "        node, p = self, []\n",
    "        while node:\n",
    "            p.append(node)\n",
    "            node = node.parent\n",
    "        yield from reversed(p)\n",
    "\n",
    "    @property\n",
    "    def solved(self):\n",
    "        \"\"\" Wrapper to check if 'puzzle' is solved \"\"\"\n",
    "        return self.puzzle.solved\n",
    "\n",
    "    @property\n",
    "    def actions(self):\n",
    "        \"\"\" Wrapper for 'actions' accessible at current state \"\"\"\n",
    "        return self.puzzle.actions\n",
    "\n",
    "    @property\n",
    "    def h(self):\n",
    "        \"\"\"\"h\"\"\"\n",
    "        return self.puzzle.manhattan\n",
    "\n",
    "    @property\n",
    "    def f(self):\n",
    "        \"\"\"\"f\"\"\"\n",
    "        return self.h + self.g\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.puzzle)\n",
    "\n",
    "class Solver:\n",
    "    \"\"\"\n",
    "    An '8-puzzle' solver\n",
    "    - 'start' is a Puzzle instance\n",
    "    \"\"\"\n",
    "    def __init__(self, start):\n",
    "        self.start = start\n",
    "\n",
    "    def solve(self):\n",
    "        \"\"\"\n",
    "        Perform breadth first search and return a path\n",
    "        to the solution, if it exists\n",
    "        \"\"\"\n",
    "        queue = collections.deque([Node(self.start)])\n",
    "        seen = set()\n",
    "        seen.add(queue[0].state)\n",
    "        while queue:\n",
    "            queue = collections.deque(sorted(list(queue), key=lambda node: node.f))\n",
    "            node = queue.popleft()\n",
    "            if node.solved:\n",
    "                return node.path\n",
    "\n",
    "            for move, action in node.actions:\n",
    "                child = Node(move(), node, action)\n",
    "\n",
    "                if child.state not in seen:\n",
    "                    queue.appendleft(child)\n",
    "                    seen.add(child.state)\n",
    "\n",
    "class Puzzle:\n",
    "    \"\"\"\n",
    "    A class representing an '8-puzzle'.\n",
    "    - 'board' should be a square list of lists with integer entries 0...width^2 - 1\n",
    "       e.g. [[1,2,3],[4,0,6],[7,5,8]]\n",
    "    \"\"\"\n",
    "    def __init__(self, board):\n",
    "        self.width = len(board[0])\n",
    "        self.board = board\n",
    "\n",
    "    @property\n",
    "    def solved(self):\n",
    "        \"\"\"\n",
    "        The puzzle is solved if the flattened board's numbers are in\n",
    "        increasing order from left to right and the '0' tile is in the\n",
    "        last position on the board\n",
    "        \"\"\"\n",
    "        N = self.width * self.width\n",
    "        return str(self) == ''.join(map(str, range(1,N))) + '0'\n",
    "\n",
    "    @property \n",
    "    def actions(self):\n",
    "        \"\"\"\n",
    "        Return a list of 'move', 'action' pairs. 'move' can be called\n",
    "        to return a new puzzle that results in sliding the '0' tile in\n",
    "        the direction of 'action'.\n",
    "        \"\"\"\n",
    "        def create_move(at, to):\n",
    "            return lambda: self._move(at, to)\n",
    "\n",
    "        moves = []\n",
    "        for i, j in itertools.product(range(self.width),\n",
    "                                      range(self.width)):\n",
    "            direcs = {'R':(i, j-1),\n",
    "                      'L':(i, j+1),\n",
    "                      'D':(i-1, j),\n",
    "                      'U':(i+1, j)}\n",
    "\n",
    "            for action, (r, c) in direcs.items():\n",
    "                if r >= 0 and c >= 0 and r < self.width and c < self.width and \\\n",
    "                   self.board[r][c] == 0:\n",
    "                    move = create_move((i,j), (r,c)), action\n",
    "                    moves.append(move)\n",
    "        return moves\n",
    "\n",
    "    @property\n",
    "    def manhattan(self):\n",
    "        distance = 0\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if self.board[i][j] != 0:\n",
    "                    x, y = divmod(self.board[i][j]-1, 3)\n",
    "                    distance += abs(x - i) + abs(y - j)\n",
    "        return distance\n",
    "\n",
    "    def shuffle(self):\n",
    "        \"\"\"\n",
    "        Return a new puzzle that has been shuffled with 1000 random moves\n",
    "        \"\"\"\n",
    "        puzzle = self\n",
    "        for _ in range(1000):\n",
    "            puzzle = random.choice(puzzle.actions)[0]()\n",
    "        return puzzle\n",
    "\n",
    "    def copy(self):\n",
    "        \"\"\"\n",
    "        Return a new puzzle with the same board as 'self'\n",
    "        \"\"\"\n",
    "        board = []\n",
    "        for row in self.board:\n",
    "            board.append([x for x in row])\n",
    "        return Puzzle(board)\n",
    "\n",
    "    def _move(self, at, to):\n",
    "        \"\"\"\n",
    "        Return a new puzzle where 'at' and 'to' tiles have been swapped.\n",
    "        NOTE: all moves should be 'actions' that have been executed\n",
    "        \"\"\"\n",
    "        copy = self.copy()\n",
    "        i, j = at\n",
    "        r, c = to\n",
    "        copy.board[i][j], copy.board[r][c] = copy.board[r][c], copy.board[i][j]\n",
    "        return copy\n",
    "\n",
    "    def pprint(self):\n",
    "        for row in self.board:\n",
    "            print(row)\n",
    "        print()\n",
    "\n",
    "    def __str__(self):\n",
    "        return ''.join(map(str, self))\n",
    "\n",
    "    def __iter__(self):\n",
    "        for row in self.board:\n",
    "            yield from row\n",
    "\n",
    "\n",
    "# example of use     \n",
    "board = [[1,2,3],[0,4,6],[7,5,8]]\n",
    "puzzle = Puzzle(board)\n",
    "#puzzle = puzzle.shuffle()\n",
    "s = Solver(puzzle)\n",
    "tic = time.clock()\n",
    "p = s.solve()\n",
    "toc = time.clock()\n",
    "\n",
    "steps = 0\n",
    "for node in p:\n",
    "    print(node.action)\n",
    "    node.puzzle.pprint()\n",
    "    steps += 1\n",
    "\n",
    "print(\"Total number of steps: \" + str(steps))\n",
    "print(\"Total amount of time in search: \" + str(toc - tic) + \" second(s)\")"
   ]
  },
  {
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}