n-tile Puzzle Solver using Bidirectional Search.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "7QC-keDYwUDw"
      },
      "outputs": [],
      "source": [
        "class node: #Class to track the properties of each node in the search space\n",
        "  def __init__(self, state, parent, action, depth, n):\n",
        "    self.state = state # a n*n 2D matrix - 0 indicates blank\n",
        "    self.parent = parent # a node that generated the current node\n",
        "    self.action = action # a char label that shows which action from the parent state was chosen \n",
        "    self.depth=depth #an integer\n",
        "    self.blankPos = self.findBlank(n) #stores blank coordinates x,y\n",
        "    \n",
        "  def findBlank(self, n): #return position of blank tile\n",
        "    for i in range(n):\n",
        "      for j in range(n):\n",
        "        if(self.state[i][j]==0):\n",
        "          return i,j"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from queue import Queue\n",
        "from math import factorial\n",
        "from copy import deepcopy\n",
        "\n",
        "class board: #class that tracks properties and search state space for a given puzzle configuration \n",
        "  def __init__(self, init_node_state, goal_state, n=3): # default n = 3 for 8-tile puzzle\n",
        "    self.n=n # for dimension of the board\n",
        "    initNode = node(init_node_state, None, '', 0, self.n) #initNode will be the root node\n",
        "    self.currentNode=initNode # current Node that is being looked into\n",
        "    self.goalState=goal_state #target state\n",
        "    self.fringeQ = Queue(factorial(n*n)) #fringe list for generated nodes (but not expanded nodes)\n",
        "    self.fringeQ.put(initNode)\n",
        "    self.expandedList = [] #List for expanded states, so they won't be repeated\n",
        "\n",
        "  def displayBoard(self, aNode: node): #print the current node state\n",
        "    for i in range(self.n):\n",
        "      for j in range(self.n):\n",
        "        print(aNode.state[i][j], end = ' ')\n",
        "      print()\n",
        "\n",
        "  def tracePathFromRoot(self, aNode: node): #when we get a solution we print the path, recursively. Prints from parent node\n",
        "    if aNode == None:\n",
        "      return\n",
        "    self.tracePathFromRoot(aNode.parent)\n",
        "    print('At Level: ', aNode.depth, \", take action: \", aNode.action, \", to get: \")\n",
        "    self.displayBoard(aNode)\n",
        "  \n",
        "  def tracePathFromNode(self, aNode: node, level): #Made especially for BDS, where we print backwards. hence forward pass is printed, then the depth is carried here as well\n",
        "    #Printing the reverse direction\n",
        "    if aNode.action == 'T':\n",
        "      a = 'B'\n",
        "    elif aNode.action == 'B':\n",
        "      a = 'T'\n",
        "    elif aNode.action == 'R':\n",
        "      a = 'L'\n",
        "    else:\n",
        "      a = 'R'\n",
        "    self.displayBoard(aNode) \n",
        "    if(aNode.parent!=None):\n",
        "      print('At Level: ', level, \", take action: \", a, \", to get: \") \n",
        "    else:\n",
        "      return\n",
        "    self.tracePathFromNode(aNode.parent, level+1)\n",
        "  \n",
        "\n",
        "  def childGen(self, aNode: node, dirn, childX, childY): #Generating the child node given the move\n",
        "    x = aNode.blankPos[0]\n",
        "    y = aNode.blankPos[1]\n",
        "    childState = deepcopy(aNode.state)\n",
        "    childState[x][y], childState[childX][childY] = childState[childX][childY], childState[x][y] #swap the tiles\n",
        "    if(childState not in self.expandedList): #make sure same state isn't repeated before adding to fringe list\n",
        "      #Probably almost all of the time of the algos, BDS/BFS, is spent in checking this. HashTable provides a near constant time solution (couldn't implement it here though)\n",
        "      child = node(childState, aNode, dirn, aNode.depth+1, self.n) \n",
        "      self.fringeQ.put(child)\n",
        "\n",
        "  def move(self, aNode: node, dirn): #generate the 4 corresponding nodes from each state. order of direction shouldn't matter much\n",
        "    x = aNode.blankPos[0]\n",
        "    y = aNode.blankPos[1]\n",
        "    if(dirn=='R'):\n",
        "      childX = x\n",
        "      childY = y+1\n",
        "      if(childY<self.n):\n",
        "        self.childGen(aNode, dirn, childX, childY)        \n",
        "    elif(dirn=='T'):\n",
        "      childX = x -1\n",
        "      childY = y\n",
        "      if(childX>=0):\n",
        "        self.childGen(aNode, dirn, childX, childY)\n",
        "    elif(dirn=='B'):\n",
        "      childX = x+1\n",
        "      childY = y\n",
        "      if(childX<self.n):\n",
        "        self.childGen(aNode, dirn, childX, childY)\n",
        "    else:\n",
        "      childX = x\n",
        "      childY = y-1\n",
        "      if(childY>=0):\n",
        "        self.childGen(aNode, dirn, childX, childY)"
      ],
      "metadata": {
        "id": "235plsX8K_Su"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def successorFnBFS(puzzle: board): #Plain BFS successor function\n",
        "  status = ' '\n",
        "  while not puzzle.fringeQ.empty(): \n",
        "    puzzle.currentNode = puzzle.fringeQ.get() #dequeue\n",
        "    if(puzzle.currentNode.state == puzzle.goalState): #test\n",
        "      puzzle.tracePathFromRoot(puzzle.currentNode) #just stop all node searching/generation and print the path\n",
        "      status = 'Solved'\n",
        "      return status\n",
        "    #actual node generation through the 4 moves of the block\n",
        "    for dirn in ['R', 'T', 'B', 'L']: \n",
        "      puzzle.move(puzzle.currentNode, dirn)\n",
        "    puzzle.expandedList.append(puzzle.currentNode.state) #finally, as all the moves from the current node have been enumerated, archive the node\n",
        "\n",
        "  if(status!='Solved'): #if fringe list is empty, it means all possible states were already explored, so no solution exists \n",
        "    status = 'Unsolvable'\n",
        "  return status"
      ],
      "metadata": {
        "id": "iQ_elAGsUXT6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def BFSExpansion(puzzle): #similar to BFS Successor Function, but the looping is being taken care of the overall BDS fn below\n",
        "  puzzle.currentNode = puzzle.fringeQ.get()\n",
        "  if(puzzle.currentNode.state == puzzle.goalState):\n",
        "      puzzle.tracePathFromRoot(puzzle.currentNode)\n",
        "  for dirn in ['R', 'T', 'B', 'L']:\n",
        "      puzzle.move(puzzle.currentNode, dirn)\n",
        "  puzzle.expandedList.append(puzzle.currentNode.state)\n",
        "  #keeping this seperate helps to control the expansion one node at a time, without having to modify the class method code to search the node in another tree's fringe list\n",
        "\n",
        "def successorFnBDS(fwdPuzzle: board, bckPuzzle: board): #BDS successor function\n",
        "  meet = 0 #track when the 2 trees finally meet\n",
        "  \n",
        "  while (not fwdPuzzle.fringeQ.empty()) and (not bckPuzzle.fringeQ.empty()) and meet!=1:\n",
        "    for f in bckPuzzle.fringeQ.queue: #before dequeuing and expanding, see if the state about to be dequeued is already in the fringe list of the backward pass\n",
        "      if(fwdPuzzle.fringeQ.queue[0].state == f.state): #again, could have searched through hashing but not as necessary as the one in childGen()\n",
        "        meet = 1\n",
        "        fwdPuzzle.tracePathFromRoot(fwdPuzzle.fringeQ.queue[0]) #if it meets, print from root to common node...\n",
        "        print('---Meeting point---')\n",
        "        bckPuzzle.tracePathFromNode(f, f.depth+1) #...and then from common node to goal\n",
        "    if(meet==0): #if not meet, expand as usual, one node at a time\n",
        "      BFSExpansion(fwdPuzzle)\n",
        "      BFSExpansion(bckPuzzle)\n",
        "\n",
        "  return meet"
      ],
      "metadata": {
        "id": "cRAOkFXPMEuW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Driver code\n",
        "\n",
        "initialState1 = [[1,2,3],\n",
        "                [4,5,6],\n",
        "                [7,0,8]]\n",
        "goalState1 = [[1,2,3],\n",
        "             [4,5,0],\n",
        "             [7,8,6]]\n",
        "\n",
        "#Let's see how  BFS and BDS do on a simple first puzzle\n",
        "print(\"BFS (forward) solution\")\n",
        "forwardPuzzle = board(initialState1, goalState1)\n",
        "forwardSoln = successorFnBFS(forwardPuzzle)\n",
        "print(forwardSoln)\n",
        "print()\n",
        "print(\"BFS (backward) solution\") #Sanity check\n",
        "backwardPuzzle = board(goalState1, initialState1)\n",
        "backwardSoln = successorFnBFS(backwardPuzzle)\n",
        "print(backwardSoln)\n",
        "print()\n",
        "print(\"BDS Solution\")\n",
        "solnBDS = successorFnBDS(forwardPuzzle, backwardPuzzle)\n",
        "if(solnBDS):\n",
        "  print(\"Solved through BDS\")\n",
        "else:\n",
        "  print(\"Unsolvable\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "puLDXf4HAUQ0",
        "outputId": "bb85269b-5d40-45fc-9793-d747fea7a6ca"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "BFS (forward) solution\n",
            "At Level:  0 , take action:   , to get: \n",
            "1 2 3 \n",
            "4 5 6 \n",
            "7 0 8 \n",
            "At Level:  1 , take action:  R , to get: \n",
            "1 2 3 \n",
            "4 5 6 \n",
            "7 8 0 \n",
            "At Level:  2 , take action:  T , to get: \n",
            "1 2 3 \n",
            "4 5 0 \n",
            "7 8 6 \n",
            "Solved\n",
            "\n",
            "BFS (backward) solution\n",
            "At Level:  0 , take action:   , to get: \n",
            "1 2 3 \n",
            "4 5 0 \n",
            "7 8 6 \n",
            "At Level:  1 , take action:  B , to get: \n",
            "1 2 3 \n",
            "4 5 6 \n",
            "7 8 0 \n",
            "At Level:  2 , take action:  L , to get: \n",
            "1 2 3 \n",
            "4 5 6 \n",
            "7 0 8 \n",
            "Solved\n",
            "\n",
            "BDS Solution\n",
            "At Level:  0 , take action:   , to get: \n",
            "1 2 3 \n",
            "4 5 6 \n",
            "7 0 8 \n",
            "At Level:  1 , take action:  T , to get: \n",
            "1 2 3 \n",
            "4 0 6 \n",
            "7 5 8 \n",
            "At Level:  2 , take action:  R , to get: \n",
            "1 2 3 \n",
            "4 6 0 \n",
            "7 5 8 \n",
            "At Level:  3 , take action:  B , to get: \n",
            "1 2 3 \n",
            "4 6 8 \n",
            "7 5 0 \n",
            "At Level:  4 , take action:  L , to get: \n",
            "1 2 3 \n",
            "4 6 8 \n",
            "7 0 5 \n",
            "At Level:  5 , take action:  T , to get: \n",
            "1 2 3 \n",
            "4 0 8 \n",
            "7 6 5 \n",
            "---Meeting point---\n",
            "1 2 3 \n",
            "4 0 8 \n",
            "7 6 5 \n",
            "At Level:  6 , take action:  R , to get: \n",
            "1 2 3 \n",
            "4 8 0 \n",
            "7 6 5 \n",
            "At Level:  7 , take action:  B , to get: \n",
            "1 2 3 \n",
            "4 8 5 \n",
            "7 6 0 \n",
            "At Level:  8 , take action:  L , to get: \n",
            "1 2 3 \n",
            "4 8 5 \n",
            "7 0 6 \n",
            "At Level:  9 , take action:  T , to get: \n",
            "1 2 3 \n",
            "4 0 5 \n",
            "7 8 6 \n",
            "At Level:  10 , take action:  R , to get: \n",
            "1 2 3 \n",
            "4 5 0 \n",
            "7 8 6 \n",
            "Solved through BDS\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#Now let's illustrate with a second example of why you should use BDS for more complicated trees\n",
        "# initialState = [[6,0,3],\n",
        "#                  [8,5,4],\n",
        "#                  [7,2,1]]\n",
        "\n",
        "initialState = [[8,1,2],\n",
        "                 [0,4,3],\n",
        "                 [7,6,5]]\n",
        "\n",
        "goalState = [[1,2,3],\n",
        "              [4,5,6],\n",
        "              [8,7,0]]\n",
        "forwardPuzzle = board(initialState, goalState)\n",
        "backwardPuzzle = board(goalState, initialState)\n",
        "print(\"BDS Solution\")\n",
        "solnBDS = successorFnBDS(forwardPuzzle, backwardPuzzle)\n",
        "if(solnBDS):\n",
        "  print(\"Solved through BDS\")\n",
        "else:\n",
        "  print(\"Unsolvable through BDS\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "f1fXoYW3aKR3",
        "outputId": "3d385125-d217-4826-8707-c1ff8582c1ce"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "BDS Solution\n",
            "At Level:  0 , take action:   , to get: \n",
            "8 1 2 \n",
            "0 4 3 \n",
            "7 6 5 \n",
            "At Level:  1 , take action:  T , to get: \n",
            "0 1 2 \n",
            "8 4 3 \n",
            "7 6 5 \n",
            "At Level:  2 , take action:  R , to get: \n",
            "1 0 2 \n",
            "8 4 3 \n",
            "7 6 5 \n",
            "At Level:  3 , take action:  R , to get: \n",
            "1 2 0 \n",
            "8 4 3 \n",
            "7 6 5 \n",
            "At Level:  4 , take action:  B , to get: \n",
            "1 2 3 \n",
            "8 4 0 \n",
            "7 6 5 \n",
            "At Level:  5 , take action:  B , to get: \n",
            "1 2 3 \n",
            "8 4 5 \n",
            "7 6 0 \n",
            "---Meeting point---\n",
            "1 2 3 \n",
            "8 4 5 \n",
            "7 6 0 \n",
            "At Level:  7 , take action:  L , to get: \n",
            "1 2 3 \n",
            "8 4 5 \n",
            "7 0 6 \n",
            "At Level:  8 , take action:  L , to get: \n",
            "1 2 3 \n",
            "8 4 5 \n",
            "0 7 6 \n",
            "At Level:  9 , take action:  T , to get: \n",
            "1 2 3 \n",
            "0 4 5 \n",
            "8 7 6 \n",
            "At Level:  10 , take action:  R , to get: \n",
            "1 2 3 \n",
            "4 0 5 \n",
            "8 7 6 \n",
            "At Level:  11 , take action:  R , to get: \n",
            "1 2 3 \n",
            "4 5 0 \n",
            "8 7 6 \n",
            "At Level:  12 , take action:  B , to get: \n",
            "1 2 3 \n",
            "4 5 6 \n",
            "8 7 0 \n",
            "Solved through BDS\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(\"BFS solution\")\n",
        "bfsSoln = successorFnBFS(forwardPuzzle) #I stopped at 26 minutes of run time without a solution. Compare this to the less-than-a-second solution by BDS!! \n",
        "print(bfsSoln)\n",
        "#Note the first example: even though the BDS solution wasn't optimal and involved much more steps, it atleast gave the answer ~immediately. BFS gave neither here."
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 434
        },
        "id": "9cGwhzop66HJ",
        "outputId": "9fa51773-d9bd-425c-ece9-61af04fa4682"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "BFS solution\n"
          ]
        },
        {
          "output_type": "error",
          "ename": "KeyboardInterrupt",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-8-ba2bb38a0e12>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"BFS solution\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mbfsSoln\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msuccessorFnBFS\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mforwardPuzzle\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m#I stopped at 26 minutes of run time without a solution. Compare this to the less-than-a-second solution by BDS!!\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbfsSoln\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;31m#Note the first example: even though the BDS solution wasn't optimal and involved much more steps, it atleast gave the answer ~immediately. BFS gave neither here.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-4-5eb1925b7711>\u001b[0m in \u001b[0;36msuccessorFnBFS\u001b[0;34m(puzzle)\u001b[0m\n\u001b[1;32m      9\u001b[0m     \u001b[0;31m#actual node generation through the 4 moves of the block\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mdirn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m'R'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'T'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'B'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'L'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m       \u001b[0mpuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmove\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurrentNode\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdirn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m     \u001b[0mpuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexpandedList\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurrentNode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstate\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m#finally, as all the moves from the current node have been enumerated, archive the node\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-3-8dc4f5ddcc6d>\u001b[0m in \u001b[0;36mmove\u001b[0;34m(self, aNode, dirn)\u001b[0m\n\u001b[1;32m     61\u001b[0m       \u001b[0mchildY\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     62\u001b[0m       \u001b[0;32mif\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mchildY\u001b[0m\u001b[0;34m<\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 63\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mchildGen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0maNode\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdirn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchildX\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchildY\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     64\u001b[0m     \u001b[0;32melif\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdirn\u001b[0m\u001b[0;34m==\u001b[0m\u001b[0;34m'T'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     65\u001b[0m       \u001b[0mchildX\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-3-8dc4f5ddcc6d>\u001b[0m in \u001b[0;36mchildGen\u001b[0;34m(self, aNode, dirn, childX, childY)\u001b[0m\n\u001b[1;32m     49\u001b[0m     \u001b[0mchildState\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdeepcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0maNode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstate\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     50\u001b[0m     \u001b[0mchildState\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0my\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchildState\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchildX\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchildY\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mchildState\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchildX\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchildY\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchildState\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0my\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;31m#swap the tiles\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 51\u001b[0;31m     \u001b[0;32mif\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mchildState\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexpandedList\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m#make sure same state isn't repeated before adding to fringe list\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     52\u001b[0m       \u001b[0;31m#Probably almost all of the time of the algos, BDS/BFS, is spent in checking this. HashTable provides a near constant time solution (couldn't implement it here though)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     53\u001b[0m       \u001b[0mchild\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mchildState\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0maNode\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdirn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0maNode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdepth\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#That said, check this 3rd example out, where an innocent number swap difference in the initial and goal states causes even BDS to not give a solution appropriately...\n",
        "initialState = [[1,2,3],\n",
        "                [4,5,6],\n",
        "                [8,7,0]]\n",
        "goalState = [[1,2,3],\n",
        "             [4,5,6],\n",
        "             [7,8,0]]\n",
        "forwardPuzzle = board(initialState, goalState)\n",
        "backwardPuzzle = board(goalState, initialState)\n",
        "solnBDS = successorFnBDS(forwardPuzzle, backwardPuzzle)\n",
        "#... a stopped the run in 26 minutes again, without a solution"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 376
        },
        "id": "lDIYx2WDbvVT",
        "outputId": "ec4450cf-6986-4754-ba99-b1e0f9248bbf"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "KeyboardInterrupt",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-9-730808b72d67>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      8\u001b[0m \u001b[0mforwardPuzzle\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mboard\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minitialState\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mgoalState\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m \u001b[0mbackwardPuzzle\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mboard\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgoalState\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitialState\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 10\u001b[0;31m \u001b[0msolnBDS\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msuccessorFnBDS\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mforwardPuzzle\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbackwardPuzzle\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     11\u001b[0m \u001b[0;31m#... a stopped the run in 26 minutes again, without a solution\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-5-2576bd7b3332>\u001b[0m in \u001b[0;36msuccessorFnBDS\u001b[0;34m(fwdPuzzle, bckPuzzle)\u001b[0m\n\u001b[1;32m     12\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m   \u001b[0;32mwhile\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;32mnot\u001b[0m \u001b[0mfwdPuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfringeQ\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mempty\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;32mnot\u001b[0m \u001b[0mbckPuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfringeQ\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mempty\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mmeet\u001b[0m\u001b[0;34m!=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m     \u001b[0;32mfor\u001b[0m \u001b[0mf\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mbckPuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfringeQ\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mqueue\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m#before dequeuing and expanding, see if the state about to be dequeued is already in the fringe list of the backward pass\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m       \u001b[0;32mif\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfwdPuzzle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfringeQ\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mqueue\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstate\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstate\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m#again, could have searched through hashing but not as necessary as the one in childGen()\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m         \u001b[0mmeet\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# def recursiveDLS(aNode: node, puzzle: board, limit):\n",
        "#   cutoffOccurred = 0\n",
        "#   cutoff=30\n",
        "#   if(puzzle.currentNode.state == puzzle.goalState): #test\n",
        "#     puzzle.tracePathFromRoot(puzzle.currentNode) #just stop all node searching/generation and print the path\n",
        "#     return 'Success'\n",
        "#   elif aNode.depth == limit:\n",
        "#     return cutoff\n",
        "#   else:\n",
        "#     puzzle.currentNode = puzzle.fringeQ.get()\n",
        "#     for dirn in ['R', 'T', 'B', 'L']: \n",
        "#       puzzle.move(puzzle.currentNode, dirn)\n",
        "#     puzzle.expandedList.append(puzzle.currentNode.state) \n",
        "# # \n",
        "#     i=0\n",
        "#     while i<len(puzzle.fringeQ) and not puzzle.fringeQ.empty():\n",
        "#       result = recursiveDLS(puzzle.fringeQ.queue[i], puzzle, limit)\n",
        "#       if result == cutoff:\n",
        "#         cutoffOccurred = 1\n",
        "#       elif result != 'Failure':\n",
        "#         return result\n",
        "    \n",
        "#   if cutoffOccurred ==1:\n",
        "#     return cutoff\n",
        "#   else:\n",
        "#     return 'Failure'\n",
        "\n",
        "\n",
        "# def successorFnDLS(puzzle: board, limit):\n",
        "#   return recursiveDLS(puzzle.currentNode,puzzle, limit)\n",
        "\n",
        "\n",
        "# def successorFnIDS(puzzle: board): #IDS successor function\n",
        "#   status = ' '\n",
        "#   depth = 0\n",
        "#   cutoff = 30\n",
        "#   while status!='Solved':\n",
        "#     result = successorFnDLS(puzzle, depth)\n",
        "#     if result!=cutoff or result == 'Success':\n",
        "#       status = 'Solved'\n",
        "  \n",
        "#   return status\n",
        "\n",
        "#   while not puzzle.fringeQ.empty(): \n",
        "#     puzzle.currentNode = puzzle.fringeQ.get() #dequeue\n",
        "#     if(puzzle.currentNode.state == puzzle.goalState): #test\n",
        "#       puzzle.tracePathFromRoot(puzzle.currentNode) #just stop all node searching/generation and print the path\n",
        "#       status = 'Solved'\n",
        "#       return status\n",
        "#     #actual node generation through the 4 moves of the block\n",
        "#     for dirn in ['R', 'T', 'B', 'L']: \n",
        "#       puzzle.move(puzzle.currentNode, dirn)\n",
        "#     puzzle.expandedList.append(puzzle.currentNode.state) #finally, as all the moves from the current node have been enumerated, archive the node\n",
        "\n",
        "#   if(status!='Solved'): #if fringe list is empty, it means all possible states were already explored, so no solution exists \n",
        "#     status = 'Unsolvable'\n",
        "#     return status"
      ],
      "metadata": {
        "id": "eTqTApcoC9O0"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}