sliding puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sliding Puzzle\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Sliding puzzle is a fun game. Let's be a bit nostalgic. In windows 7, you can pin a picture puzzle to the desktop from the gadgets. That basically is a sliding puzzle. In our case, we intent to seek solutions to number puzzle. The objective is the same. Move the tiles to sort them in numerical orders. In translation, the puzzle needs to go from one status to the other. Your instinct should tell that we are going to tackle this problem via graph theory. Although it can be solved via different graph traversal algorithms, we merely apply BFS here. Nonetheless, this isn't the usual BFS. We will make a variation of conventional BFS. Traditionally we convert a problem to a graph structure first, whereas this time we do not create a graph structure at all. We only find eligible children vertices when they are required to join BFS queue, which is similar to the concept of just-in-time compilation. Certainly, there are merits to this change. One is that we avoid creating vertices that the traversal algorithm never actually will visit. Given how many combinations a 3 by 3 sliding puzzle has, it's a great improvement on the time complexity. In addition to the first point, we also use less memory since we do not create a graph structure hosting all possible scenarios of the sliding puzzle.\n",
    "\n",
    "More details of the sliding puzzle game can be found in the link below\n",
    "\n",
    "https://en.wikipedia.org/wiki/Sliding_puzzle\n",
    "\n",
    "&nbsp;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation as pltani\n",
    "import os\n",
    "os.chdir('K:/ecole/github/televerser')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#initial status\n",
    "sliding_puzzle_init=[[5,8,2],[7,0,3],[1,4,6]]\n",
    "\n",
    "#desired result\n",
    "sliding_puzzle_final=[[1,2,3],[4,5,6],[7,8,0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#find next possible moves and append to queue\n",
    "def check_around(current,row_id,col_id,visited,queue,pred):\n",
    "\n",
    "    #avoid left most\n",
    "    #move left tile to the right\n",
    "    if col_id!=0:\n",
    "        sliding_puzzle_next=copy.deepcopy(current)\n",
    "        exchange=sliding_puzzle_next[row_id][col_id-1]\n",
    "        sliding_puzzle_next[row_id][col_id]=exchange\n",
    "        sliding_puzzle_next[row_id][col_id-1]=0\n",
    "        \n",
    "        #visit each status once\n",
    "        #convert to string to store in dict\n",
    "        if sliding_puzzle_next not in visited and sliding_puzzle_next not in queue:\n",
    "            queue.append(sliding_puzzle_next)\n",
    "            pred[''.join([str(j) for i in sliding_puzzle_next for j in i])]=current\n",
    "\n",
    "    #avoid right most\n",
    "    #move right tile to the left\n",
    "    if col_id!=len(current[0])-1:\n",
    "        sliding_puzzle_next=copy.deepcopy(current)\n",
    "        exchange=sliding_puzzle_next[row_id][col_id+1]\n",
    "        sliding_puzzle_next[row_id][col_id]=exchange\n",
    "        sliding_puzzle_next[row_id][col_id+1]=0\n",
    "        \n",
    "        #visit each status once\n",
    "        #convert to string to store in dict\n",
    "        if sliding_puzzle_next not in visited and sliding_puzzle_next not in queue:\n",
    "            queue.append(sliding_puzzle_next)\n",
    "            pred[''.join([str(j) for i in sliding_puzzle_next for j in i])]=current\n",
    "\n",
    "    #avoid top most\n",
    "    #move top tile down\n",
    "    if row_id!=0:\n",
    "        sliding_puzzle_next=copy.deepcopy(current)\n",
    "        exchange=sliding_puzzle_next[row_id-1][col_id]\n",
    "        sliding_puzzle_next[row_id][col_id]=exchange\n",
    "        sliding_puzzle_next[row_id-1][col_id]=0\n",
    "        \n",
    "        #visit each status once\n",
    "        #convert to string to store in dict\n",
    "        if sliding_puzzle_next not in visited and sliding_puzzle_next not in queue:\n",
    "            queue.append(sliding_puzzle_next)\n",
    "            pred[''.join([str(j) for i in sliding_puzzle_next for j in i])]=current\n",
    "\n",
    "    #avoid bottom most\n",
    "    #move bottom tile up\n",
    "    if row_id!=len(current)-1:\n",
    "        sliding_puzzle_next=copy.deepcopy(current)\n",
    "        exchange=sliding_puzzle_next[row_id+1][col_id]\n",
    "        sliding_puzzle_next[row_id][col_id]=exchange\n",
    "        sliding_puzzle_next[row_id+1][col_id]=0\n",
    "        \n",
    "        #visit each status once\n",
    "        #convert to string to store in dict\n",
    "        if sliding_puzzle_next not in visited and sliding_puzzle_next not in queue:\n",
    "            queue.append(sliding_puzzle_next)\n",
    "            pred[''.join([str(j) for i in sliding_puzzle_next for j in i])]=current\n",
    "            \n",
    "    return queue,pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#solve sliding puzzle problem via bfs\n",
    "#details of bfs can be found in the following link\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20DFS%20on%20DCG.ipynb\n",
    "def sliding_puzzle(sliding_puzzle_init,sliding_puzzle_final):\n",
    "\n",
    "    #initialize\n",
    "    start=sliding_puzzle_init\n",
    "    stop=False\n",
    "\n",
    "    #create a queue with rule of first-in-first-out\n",
    "    queue=[]\n",
    "    queue.append(start)\n",
    "    visited=[]\n",
    "\n",
    "    #pred keeps track of how we get to the current vertex\n",
    "    pred={}\n",
    "\n",
    "    #bfs\n",
    "    while not stop:\n",
    "\n",
    "        #keep track of the visited vertices\n",
    "        current=queue.pop(0)\n",
    "        visited.append(current)\n",
    "\n",
    "        #locate the sliding tile\n",
    "        row_id=current.index([i for i in current if 0 in i][0])\n",
    "        col_id=current[row_id].index(0)\n",
    "\n",
    "        #target reached\n",
    "        if current==sliding_puzzle_final:\n",
    "            stop=True\n",
    "\n",
    "        #find next status\n",
    "        else:\n",
    "            queue,pred=check_around(current,row_id,col_id,visited,queue,pred)    \n",
    "\n",
    "        #impossible to reach target\n",
    "        if len(queue)==0:\n",
    "            stop=True\n",
    "\n",
    "    #create the path by backtracking\n",
    "    #trace the predecessor vertex from end to start\n",
    "    previous=''.join([str(j) for i in sliding_puzzle_final for j in i])\n",
    "    path=[]\n",
    "    while pred:\n",
    "        path.insert(0, previous)\n",
    "        if previous==''.join([str(j) for i in start for j in i]):\n",
    "            break\n",
    "        previous=''.join([str(j) for i in pred[previous] for j in i])\n",
    "\n",
    "    return len(path)-1,path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create animation for sliding\n",
    "def draw_sliding_puzzle(step,*args):\n",
    "\n",
    "    ax,row_num,col_num,path=args\n",
    "    ax.clear()\n",
    "    ax.axis('off')\n",
    "    \n",
    "    #viz tiles\n",
    "    for row_id in range(row_num):\n",
    "        for col_id in range(col_num):\n",
    "            ax.plot([col_id-0.5,col_id-0.5,col_id+0.5,col_id+0.5,col_id-0.5,],\n",
    "                    [-row_id-0.5,-row_id+0.5,-row_id+0.5,-row_id-0.5,-row_id-0.5,],c='k')\n",
    "            if path[step][row_id*col_num+col_id]!='0':        \n",
    "                ax.text(col_id,-row_id,path[step][row_id*col_num+col_id],\n",
    "                        ha='center',va='center',fontsize=20)\n",
    "            else:\n",
    "                ax.fill_between([col_id-0.5,col_id+0.5,],[-row_id+0.5,-row_id+0.5],\n",
    "                                [-row_id-0.5,-row_id-0.5],color='cyan')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#use bfs to get path\n",
    "num_of_steps,path=sliding_puzzle(sliding_puzzle_init,sliding_puzzle_final)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "MovieWriter ffmpeg unavailable.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAFpCAYAAACVjP/1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAADrhJREFUeJzt3HnMZXddx/HPF0YBW5xREKoGkSICglJQgYJAqbgALoDUGGQzQiFiCFsQEQQ0RurKYqIiSLVIooAQtWWnCwSURCiERRFK2dICbZnKvpSvf9w7dDqdcQph7rlPv69X8vTMc8+T3O/0ZM773vM796nuDgDzXGPpAQBYhgAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEPtWnqAI6GqTk7ygKXn4Aq+e729YNEpOJDjsp1e3N3PO9JPcnV9B/CAJMctPQRXcNP1F9vFcdk+x2VDL2CruzfxPBtVVWclSXefsOwk7FNVe5Oku/csPQuXc1y2zybPX1fXdwAAHIYAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCQDAUAIAMJQAAAwlAABDCcAWqqrzq6oP8XXh0vNNVVX3rqrXVNVHq+rzVXVeVb2kqo5feraJqup6VfWwqnp5Vb1/fUwurao3VdWvV5Xz22HsWnoADunSJM86yOOf2fQgJFV1SpInJrk4ySuSXJTkB5L8YpJfqqoHd/eLFhxxopOS/GWSC5KcmeTDSW6Y5H5Jnp/knlV1Unf3ciNut7o6/r+pqrOSpLtPWHaSb0xVnZ8k3f39y07yzVNVe5Oku/csPcvXq6qOSfKxJJ9M8iPd/Yn99t09yRuSfLC7j11oxG/YDj8uJyY5Ksnp3f3V/R4/Jslbk9woyf27+2ULjfgN2eT5y1skOLwbZ/Vv5T/2P/knSXefmeTTSb5ricEm6+43dPe/7n/yXz9+YZK/Wn97wsYH20FcAtpe16qqByb5viSfTfLOJOd092XLjjXS/yT5UpLbV9X1u/uifTuq6q5JrpvVZSG2x5fX268sOsWWE4DtdUyS0w547INV9WvdffYSA03V3ZdU1W8l+bMk76mqV2S1FnDTJL+Q5LVJHrHgiOynqnYlefD621ctOcu2E4Dt9MIkb0zy7qwuLxyb5DeTnJzklVV1fHe/Y8H5xunuZ63XZv42ycP32/X+JKceeGmIRT0zya2TnNHdr156mG1mDWALdfcz1tc3P97dn+vud3X3I7N6BXqdJE9fdsJ5quqJSV6a5NSsXvkfleRHk5yX5B+q6o+Wm459qurRSR6f5L+SPGjhcbaeAOws+xa27rroFMNU1QlJTknyL939uO4+bx3mtyW5b1Z3CD2+qnbcXUBXJ1X1qCTPTvKeJHfv7ksWHmnrCcDOsu8yw1GLTjHPz623Zx64o7s/l9Uth9dIcttNDsXlquoxSf4iybuyOvn7wORVIAA7y75PnJ636BTzXGu9PdStnvse/9IGZuEA6wX6P09yblYnf+sxV5EAbJmqulVVfedBHr9xVq9wksQnTjfrjevtyVX1vfvvqKp7Jrlzki8kefOmB5uuqp6a1aLvfyb5yf1v0eXw3AW0fU5K8qSqOjPJB7O6C+imSe6d5NpJzkjyJ8uNN9JLk7wuyT2SvLeqXp7kwiS3zOryUCV5UndfvNyI81TVQ5L8XpLLsor0o6vqwB87v7tP3fBoO4YAbJ8zk9w8q+vJx2d1vX9vkjdl9bmA0/xuk83q7q9W1b2SPCrJr2S18PttSS7JKsjP6e7XLDjiVDdZb6+Z5DGH+Jmzs7pzi4Pwu4DYiJ38O2euzhyX7eN3AQFwxAkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFDV3UvP8E1XVfv+UpcuOgj7273eOibbxXHZPkcn+UB33/xIP9GuI/0EcAW7d+8+/A+xMZc67092dQ3A2UnS3ScsPAdrVbU3u3fvzt69S4/C/vbsSZL03r17Fp6Etao6a1PPZQ0AYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEgCAoQQAYCgBABhKAACGEoAtU1UPrao+zNdlS88J26CqTqmq11fVR6rq81V1SVW9vaqeVlXXW3q+bbdr6QG4knOTPOMQ++6S5MQkr9zcOLDVHpvkbUlem+QTSY5KcsckT09yclXdsbs/stx4200Atkx3n5tVBK6kqt6y/uPzNjcRbLVv7+4vHPhgVf1Bkicn+e0kv7HxqXYIl4B2iKq6dVavbD6W5PSFx4GtcLCT/9o/rbc329QsO5EA7ByPWG9f0N3WAOD/9/Pr7TsXnWLLuQS0A1TVdZI8MMlXkzx/4XFg61TVE5IcnWR3kh9L8hNZnfyfueRc204AdoZfTrInyekWtOCgnpDkhvt9/6okD+3uTy40z47gEtDOcPJ6+9eLTgFbqruP6e5KckyS+yU5Nsnbq+p2y0623QRgy1XVDyW5U5KPJjlj4XFgq3X3x7v75Ul+Osn1kvz9wiNtNQHYfhZ/4evU3R9K8p4kt6qq6y89z7YSgC1WVddO8qCsFn9fsPA4sNN8z3rrhdMhCMB2OynJdyQ5w+IvXFFV3aKqjjnI49dYfxDsBkne3N2f2vx0O4O7gLbbvsVfn/yFK/vZJH9cVeck+UCSi7O6E+huWS0CX5jk4cuNt/0EYEtV1S2zupfZ4i8c3OuyenF05yS3yepW6c8meV+S05I8p7svWW687ScAW6q735uklp4DtlV3vyvJo5aeYyezBgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADFXdvfQM33RVte8vdemig7C/3av/7l54DK7g0q/9E/FvZXscneQD3X3zI/1E3gEADLVr6QGOkLOTpLtPWHgO1qpqb5L03r17lp6Fy33tuHQ7Lluiqs7a1HN5BwAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJAMBQAgAwlAAADCUAAEMJwJapqvtX1XOr6o1V9b9V1VX1oqXn4sqq6kHr49NV9bCl55mqqu5SVS+rqguq6ovr7Wuq6l5Lz7btdi09AFfylCS3SfKZJB9Ncotlx+FgqupGSZ6b1XE6euFxxqqqpyT5/SQXJfm3JBckuX6S2yY5IckZiw23AwjA9nlsVif+9ye5W5Izlx2HA1VVJXlhkouT/HOSJyw70UxVdVJWJ//XJblfd3/6gP3fsshgO4gAbJnu/toJf3WeYQs9OsmJWb3CPHHZUWaqqmskOSXJ55I84MCTf5J095c3PtgOIwDwdaiqWyZ5ZpJnd/c5VSUAy7hTkpskeWmST1XVvZPcOskXkry1u9+y5HA7hQDAVVRVu5KcluTDSZ688DjT/fh6+/Ekb0vyw/vvrKpzkty/uz+56cF2EncBwVX3u1ktLj60uz+/9DDD3WC9fWSS6yS5R5LrZvUu4NVJ7prkJcuMtnMIAFwFVXX7rF71/6nLC1vhmuttZfVK//Xd/ZnufneS+2Z1I8Xdqur4xSbcAQQADmO/Sz/vS/LUhcdh5VPr7Xnd/Y79d6zfnb16/e3tNzrVDiMAcHhHJ/nBJLdM8oX9PvzVSZ62/pm/WT/2rMWmnOW/19u9h9i/LxDX2cAsO5ZFYDi8LyZ5wSH23S6rdYE3ZXVScnloM85J8pUkN6uqb+3uLx2w/9br7fkbnWqHEQA4jPUlhYP+qoeqenpWAfi77n7+JuearLsvqqp/TPKrWS3OP2Xfvqr6qSQ/k+TSJK9aZsKdQQC2TFXdJ8l91t8es94eX1Wnrv98UXf75Ckkj0tyhyS/U1V3TfLWJDfOahH4siQP7+5DXSIiArCNjkvykAMeO3b9lSQfil89AOnuT1TVHbJ69X/fJHdM8ukkpyf5w+7+9yXn2wmqu5ee4Zuuqs5Kku4+YdlJ2Keq9iZJd+9ZehYu57hsn02ev9wFBDCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMtWvpAY6QuyVJVZ218BxcbnfimGwhx2X7HJfk3E08kXcAANvl3CQv3sQTVXdv4nkA2DLeAQAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAMJQAAQwkAwFACADCUAAAM9X8de9oTR0jEcAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "#viz\n",
    "row_num=len(sliding_puzzle_init)\n",
    "col_num=len(sliding_puzzle_init[0])\n",
    "fig,ax=plt.subplots(figsize=(row_num*2,col_num*2))\n",
    "\n",
    "ax.set_xlim(-1,col_num)\n",
    "ax.set_ylim(-row_num-1,0)\n",
    "ax.axis('off')\n",
    "\n",
    "#create animations\n",
    "anim=pltani.FuncAnimation(fig,draw_sliding_puzzle,\n",
    "                          frames=len(path),\n",
    "                          interval=900,\n",
    "                          fargs=(ax,row_num,col_num,path))\n",
    "anim.save('sliding puzzle.gif')"
   ]
  },
  {
   "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.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}