iddfs_8puzzel.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs(src,target,limit,visited_states):\n",
    "    if src == target:\n",
    "        return True\n",
    "    if limit <= 0:\n",
    "        return False\n",
    "    visited_states.append(src)\n",
    "    moves = possible_moves(src,visited_states)   \n",
    "    for move in moves:\n",
    "        if dfs(move, target, limit-1, visited_states):\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def possible_moves(state,visited_states): \n",
    "    b = state.index(-1)  \n",
    "    d = []\n",
    "    if b not in [0,1,2]: \n",
    "        d += 'u'\n",
    "    if b not in [6,7,8]:\n",
    "        d += 'd'\n",
    "    if b not in [2,5,8]: \n",
    "        d += 'r'\n",
    "    if b not in [0,3,6]: \n",
    "        d += 'l'\n",
    "    pos_moves = []\n",
    "    for move in d:\n",
    "        pos_moves.append(gen(state,move,b))\n",
    "    return [move for move in pos_moves if move not in visited_states]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gen(state, move, blank): \n",
    "    temp = state.copy()                              \n",
    "    if move == 'u':\n",
    "        temp[blank-3], temp[blank] = temp[blank], temp[blank-3]\n",
    "    if move == 'd':\n",
    "        temp[blank+3], temp[blank] = temp[blank], temp[blank+3]\n",
    "    if move == 'r':\n",
    "        temp[blank+1], temp[blank] = temp[blank], temp[blank+1]\n",
    "    if move == 'l':\n",
    "        temp[blank-1], temp[blank] = temp[blank], temp[blank-1]\n",
    "    return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def iddfs(src,target,depth):\n",
    "    for i in range(depth):\n",
    "        visited_states = []\n",
    "        if dfs(src,target,i+1,visited_states):\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "#Test 1\n",
    "src = [1,2,3,-1,4,5,6,7,8]\n",
    "target = [1,2,3,4,5,-1,6,7,8]         \n",
    "\n",
    "depth = 1\n",
    "iddfs(src, target, depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Test 2\n",
    "src = [3,5,2,8,7,6,4,1,-1]\n",
    "target = [-1,3,7,8,1,5,4,6,2]\n",
    "\n",
    "depth = 1\n",
    "iddfs(src, target, depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Test 2\n",
    "src = [1,2,3,-1,4,5,6,7,8] \n",
    "target=[1,2,3,6,4,5,-1,7,8]\n",
    "\n",
    "depth = 1\n",
    "iddfs(src, target, depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 False\n",
      "2 False\n",
      "3 False\n",
      "4 False\n",
      "5 False\n",
      "6 False\n",
      "7 False\n",
      "8 False\n",
      "9 False\n",
      "10 False\n",
      "11 False\n",
      "12 False\n",
      "13 False\n",
      "14 False\n",
      "15 False\n",
      "16 False\n",
      "17 False\n",
      "18 False\n",
      "19 False\n",
      "20 False\n",
      "21 False\n",
      "22 False\n",
      "23 False\n",
      "24 False\n",
      "25 True\n"
     ]
    }
   ],
   "source": [
    "src = [1, 2, 3, 4, 5, 6, 7, 8, -1]\n",
    "target = [-1, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "\n",
    "for i in range(1, 100):\n",
    "    val = iddfs(src,target,i)\n",
    "    print(i, val)\n",
    "    if val == True:\n",
    "        break"
   ]
  },
  {
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}