A*_algo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''Note: please read comments for more clarification.'''\n",
    "\n",
    "\n",
    "#finding blank's location in state\n",
    "def findBlankPosition(array):\n",
    "    for i in range(3):\n",
    "        for j in range(3):\n",
    "            if array[i][j] == 0:\n",
    "                return i,j\n",
    "\n",
    "\n",
    "#finding man-hattan distance \n",
    "def heuristicFun(arr,heuristic_value=0): #NOTE: goal must be numpy array for using np.where(list==element)\n",
    "    Goal=np.array([[0,1,2],[3,4,5],[6,7,8]])\n",
    "    for i in range(3):\n",
    "        for j in range(3):\n",
    "            x,y=np.where(Goal==arr[i][j])\n",
    "            heuristic_value += abs(x[0]-i)+abs(y[0]-j)\n",
    "    return heuristic_value\n",
    "   \n",
    "    \n",
    "# creating child node for particular action\n",
    "def childNode(problem,node,array_loc):\n",
    "    i,j = array_loc\n",
    "    if i<0 or j<0 or j>2 or i>2: #for avoiding out of bound case\n",
    "        return None\n",
    "    else:\n",
    "        iB,jB = findBlankPosition(node.state)\n",
    "        node.state[iB][jB] = node.state[i][j]\n",
    "        node.state[i][j] = 0\n",
    "        return node\n",
    "    \n",
    "\n",
    "#class for Node for containing g,f,h values and state list\n",
    "class Node:\n",
    "    def __init__(self):#need in f=g+h function\n",
    "        self.g=0\n",
    "        self.h=0\n",
    "        self.f=0\n",
    "        self.state=[[0,0,0],[0,0,0],[0,0,0]]\n",
    "\n",
    "\n",
    "#class for normal functions\n",
    "class puzzle:\n",
    "    \n",
    "    def __init__(self):  \n",
    "        self.node=Node()\n",
    "        self.goal=[[0,1,2],[3,4,5],[6,7,8]]\n",
    "        \n",
    "    def ACTIONS(self,arr): #find 0 and take actions as top,down,left,right\n",
    "        self.node=arr\n",
    "        i,j=findBlankPosition(self.node)\n",
    "        return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]] #sending all 4 case, boundry will be checked there itself\n",
    "         \n",
    "    def GOAL_TEST(self,node):\n",
    "        self.node=node\n",
    "        if self.node.state == self.goal: # for verifying with goal\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def INITIAL_STATE(self):\n",
    "#         self.node.state=RandomArray()\n",
    "        self.node.state =[[6,0,2],[4,7,3],[1,5,8]]\n",
    "        self.node.h = heuristicFun(self.node.state)\n",
    "        self.node.g = 0\n",
    "        self.node.f = self.node.g + self.node.h  #using f(n) = g(n) + h(n)\n",
    "        return self.node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#here, problem is object of puzzle class\n",
    "def A_Star(problem,closedList,openList):\n",
    "\n",
    "    if len(openList)==0:# when openList is empty\n",
    "        print(\"\\n\\n\\nFailed to find solution\")\n",
    "        return -1\n",
    "    \n",
    "    node=openList[0]\n",
    "    for succ in openList: #finding mimnimun f_value node in openList\n",
    "        if node.f > succ.f:\n",
    "            node=succ\n",
    "            \n",
    "    openList.remove(openList[openList.index(node)]) # removing node from openList that has min. f value \n",
    "    closedList.append(node)#adding popped node to closedList\n",
    "    print(\"\\ncurrent node \",node.state)\n",
    "    \n",
    "    if problem.GOAL_TEST(node):#checking, whether node is goal or not ?\n",
    "        print(\"\\n\\nWow! finally you have found the solution.\\n\\nThat is:\\n\",node.state)\n",
    "        return node.f #SOLUTION found returning f_value \n",
    "\n",
    "    for action_loc in problem.ACTIONS(node.state):\n",
    "        child=deepcopy(childNode(problem,node,action_loc))#deepcopy,for avoiding call by reference in array pointer\n",
    "        if child:#checking, child is not None ?\n",
    "            \n",
    "            if child in openList:#for updating g of child ==>> child.g = min(child.g , node.g + 1)\n",
    "                openList[openList.index(child)].g = min(child.g , node.g + 1) \n",
    "            elif (child not in closedList): # obviously, not in openList due to if condition\n",
    "                child.g = node.g + 1\n",
    "                child.h = heuristicFun(child.state)\n",
    "                child.f = child.g + child.h   #using f(n) = g(n) + h(n)\n",
    "                openList.append(child) #adding to openList after calculating f,g,h values\n",
    "                \n",
    "#             print(\"\\nchild added to openSet \",child.state)\n",
    "    return A_Star(problem,closedList,openList)\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#creating starting board 8-puzzle \n",
    "'''NOTE: But it can't be used due to unsolvable case might generate.'''\n",
    "def RandomArray():\n",
    "    arr=np.zeros([3,3],dtype=int)\n",
    "    for i in range(3):    #generate random 2D array of size 3x3 with one number repeated (form 1 to 8)\n",
    "        for j in range(3):\n",
    "            k=0;x=np.random.randint(1,9)\n",
    "            while(x in arr and k<100):\n",
    "                x=np.random.randint(1,9);k+=1\n",
    "            arr[i][j]=x\n",
    "    \n",
    "    dic={}    #for finding repeated number from that 2D array (It can't be done by predefined functions)\n",
    "    for i in range(3): #creating dictionary for  keeping count \n",
    "        for j in range(3):\n",
    "            x=arr[i][j]\n",
    "            dic[x]=0 if x not in dic else 1\n",
    "    for key, value in dic.items():  # finding that number\n",
    "        if value==1:\n",
    "            num=key\n",
    "            break\n",
    "    x,y=np.where(arr==num) #finding index of the number in the array \n",
    "    print(arr)\n",
    "    print(x,y)\n",
    "    arr[x[0]][x[1]]=0   # replacing that number with zero\n",
    "    print(\"\\nstarting Array:\\n\",arr)\n",
    "    return [arr]     # finally, we got a random array with 0 to 8 number in 3x3 matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "NOTE:- You might get 'maximum recursion depth exceeded' due to unsolvable 8-puzzle problem.\n",
      "\n",
      "started execution............\n",
      "\n",
      "current node  [[6, 0, 2], [4, 7, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [4, 0, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [4, 7, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [0, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 7, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [3, 7, 0], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 7, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 5, 3], [7, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 5, 0], [3, 7, 2], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 7, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 6, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 4, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 7, 3], [0, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 8], [3, 1, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [3, 0, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 7, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 4, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[4, 7, 2], [0, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 7, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 6, 3], [0, 5, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 8], [3, 0, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 5, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[2, 7, 0], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 6, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 8], [3, 1, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [7, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[0, 6, 2], [7, 4, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [4, 7, 3], [1, 0, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [4, 1, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [0, 1, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [4, 0, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [4, 5, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [6, 1, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 6, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [0, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 7, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [5, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [0, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [5, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 6, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[3, 5, 2], [0, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [5, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 3, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 5, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [5, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 5, 3], [7, 0, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [3, 7, 0], [1, 4, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 6, 5], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 6, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 4, 3], [7, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [5, 7, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [5, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [5, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [7, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 7, 5], [1, 0, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 1, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [0, 1, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 0, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 4, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [6, 1, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 6, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [0, 7, 5], [1, 3, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 7, 5], [1, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 7, 5], [0, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 5], [7, 3, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 5], [7, 3, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [0, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 5], [7, 3, 8]]\n",
      "\n",
      "current node  [[0, 3, 2], [1, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 4, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [4, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 3, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[4, 7, 2], [0, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [7, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 5, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [5, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[7, 1, 2], [0, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 4, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 4, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 3, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 6, 3], [4, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 7, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 5, 2], [6, 0, 7]]\n",
      "\n",
      "current node  [[1, 4, 8], [0, 5, 2], [6, 3, 7]]\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current node  [[2, 0, 5], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 5], [3, 2, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 6, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 3, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [7, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[7, 0, 2], [6, 4, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 7, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [0, 1, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [5, 1, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 6, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [0, 5, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [6, 5, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [6, 5, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [3, 5, 0], [1, 4, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [5, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 7, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 5, 3], [7, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[5, 1, 2], [0, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [0, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [7, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 4, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 4, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 3, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 6, 5], [3, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 4, 0], [6, 5, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [0, 1, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [4, 1, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 3, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 4, 5], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 4, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [4, 3, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [6, 4, 5], [7, 0, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [0, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[7, 1, 2], [0, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [7, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[5, 1, 2], [0, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 5, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [7, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[5, 1, 2], [0, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[2, 7, 0], [4, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [4, 0, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [4, 7, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [0, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 7, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 7, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [3, 7, 0], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 7, 3], [6, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 5, 3], [7, 0, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 5, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [1, 7, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [1, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [1, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [0, 5, 3], [7, 1, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 5, 3], [7, 1, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 5, 0], [7, 1, 8]]\n",
      "\n",
      "current node  [[2, 5, 0], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[2, 0, 3], [6, 1, 5], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 1, 3], [6, 2, 5], [7, 4, 8]]\n",
      "\n",
      "current node  [[3, 1, 0], [6, 2, 5], [7, 4, 8]]\n",
      "\n",
      "current node  [[7, 4, 2], [1, 5, 3], [0, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 5, 2], [7, 6, 0]]\n",
      "\n",
      "current node  [[2, 5, 0], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[2, 0, 4], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 1, 4], [3, 2, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 5, 8], [3, 0, 2], [1, 4, 7]]\n",
      "\n",
      "current node  [[6, 0, 8], [3, 5, 2], [1, 4, 7]]\n",
      "\n",
      "current node  [[2, 5, 0], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[2, 0, 3], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 3], [4, 2, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 1, 0], [4, 2, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [5, 0, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 0], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 7, 8], [3, 0, 2], [6, 4, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 7, 2], [6, 4, 5]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[2, 7, 0], [3, 6, 5], [1, 4, 8]]\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 4, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [3, 0, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 7, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[2, 4, 0], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[2, 7, 0], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [1, 7, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [1, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [1, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [0, 5, 3], [7, 1, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 5, 3], [7, 1, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 5, 0], [7, 1, 8]]\n",
      "\n",
      "current node  [[1, 5, 8], [3, 7, 2], [6, 4, 0]]\n",
      "\n",
      "current node  [[2, 7, 0], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[2, 5, 0], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[2, 0, 3], [4, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 3], [4, 2, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 1, 0], [4, 2, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [5, 0, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 0], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 8], [3, 0, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 5, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[6, 7, 2], [3, 1, 5], [0, 4, 8]]\n",
      "\n",
      "current node  [[2, 1, 0], [7, 3, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[2, 4, 0], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 8], [3, 0, 2], [6, 4, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 7, 2], [6, 4, 5]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 8], [3, 0, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 5, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[1, 5, 8], [3, 0, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 5, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[2, 7, 0], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 1, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[2, 7, 0], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [4, 1, 3], [8, 7, 0]]\n",
      "\n",
      "current node  [[4, 5, 2], [6, 0, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [6, 5, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 4, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [4, 0, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [4, 5, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 5, 2], [4, 1, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 6, 3], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 1, 2], [5, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [5, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[4, 1, 2], [5, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[2, 1, 0], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 4, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 7, 3], [0, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[6, 5, 0], [3, 7, 2], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 7, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[2, 7, 0], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[2, 4, 0], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 6, 2], [7, 3, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 6, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [1, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [1, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 7, 3], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [5, 6, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [5, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [7, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 1, 5], [8, 7, 0]]\n",
      "\n",
      "current node  [[3, 4, 2], [6, 0, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [6, 4, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 0, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 4, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[6, 4, 2], [3, 1, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[2, 4, 0], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 5], [7, 3, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 5], [7, 3, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [0, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [5, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 4, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [4, 0, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[4, 1, 2], [7, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [3, 1, 0], [6, 7, 8]]\n",
      "\n",
      "current node  [[2, 1, 0], [7, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[4, 1, 2], [5, 0, 3], [6, 7, 8]]\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current node  [[2, 1, 0], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 4, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 6, 3], [4, 5, 8]]\n",
      "\n",
      "current node  [[4, 7, 2], [1, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [1, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 7, 3], [6, 1, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 7, 3], [6, 1, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [3, 7, 0], [6, 1, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [0, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [7, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 6, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [6, 5, 7]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [6, 5, 7]]\n",
      "\n",
      "current node  [[0, 4, 8], [1, 5, 2], [6, 3, 7]]\n",
      "\n",
      "current node  [[2, 1, 5], [3, 0, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 6, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [1, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [1, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [1, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [1, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [7, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [6, 1, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[4, 5, 2], [0, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[6, 1, 2], [5, 0, 3], [4, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [6, 0, 3], [5, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 7, 3], [5, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [5, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 7, 0], [5, 6, 8]]\n",
      "\n",
      "current node  [[6, 7, 0], [3, 5, 2], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 5, 7], [1, 4, 8]]\n",
      "\n",
      "current node  [[4, 1, 2], [5, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[2, 1, 0], [5, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 6, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 4, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 7, 3], [0, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [7, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 4, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 6, 5], [3, 4, 8]]\n",
      "\n",
      "current node  [[3, 7, 2], [1, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [1, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 7, 5], [6, 1, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 7, 5], [6, 1, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 6, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [1, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [1, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 4, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 4, 2], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 7], [6, 5, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [6, 1, 5], [0, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [0, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[6, 1, 2], [4, 0, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [3, 0, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 4, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[3, 1, 2], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [6, 0, 5], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 3, 5], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 3, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [6, 7, 5], [0, 4, 8]]\n",
      "\n",
      "current node  [[1, 3, 2], [0, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 5], [6, 3, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 6, 5], [3, 7, 8]]\n",
      "\n",
      "current node  [[3, 4, 2], [1, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[3, 0, 2], [1, 4, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 3, 2], [1, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 2], [4, 0, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 7, 0], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [7, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 6, 3], [1, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [6, 0, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 5, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 5, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 8], [3, 0, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 0, 8], [3, 4, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 0, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[6, 5, 0], [3, 7, 2], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 7, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 6, 3], [0, 7, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [4, 0, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [4, 5, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 0, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [6, 4, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [0, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 2], [3, 4, 0], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [6, 7, 3], [0, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [0, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [1, 5, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 7, 0], [3, 5, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 6, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 4, 0], [3, 5, 2], [7, 1, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 5, 4], [7, 1, 8]]\n",
      "\n",
      "current node  [[2, 1, 3], [6, 0, 5], [7, 4, 8]]\n",
      "\n",
      "current node  [[2, 1, 4], [3, 0, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[4, 1, 0], [3, 2, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 8], [3, 6, 2], [1, 4, 7]]\n",
      "\n",
      "current node  [[2, 1, 3], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 7, 2], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 4], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 8], [3, 1, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[0, 7, 8], [3, 1, 2], [6, 4, 5]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 8], [3, 1, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[0, 4, 8], [3, 1, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 4, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 6, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 6, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[6, 4, 0], [3, 5, 2], [7, 1, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 5, 4], [7, 1, 8]]\n",
      "\n",
      "current node  [[2, 1, 3], [4, 0, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [5, 1, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 7, 2], [6, 5, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 4], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 8], [3, 1, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[0, 7, 8], [3, 1, 2], [6, 4, 5]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 8], [3, 1, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[0, 5, 8], [3, 1, 2], [6, 4, 7]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [4, 6, 3], [1, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 8], [3, 1, 2], [7, 6, 5]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [4, 1, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 7, 2], [6, 4, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 7, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 3], [7, 5, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 5, 0], [3, 4, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 7, 3], [6, 5, 8]]\n",
      "\n",
      "current node  [[6, 7, 2], [3, 0, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[6, 0, 2], [3, 7, 5], [1, 4, 8]]\n",
      "\n",
      "current node  [[0, 7, 2], [3, 1, 5], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 4, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [5, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [6, 1, 3], [7, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [1, 5, 3], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 0], [3, 5, 2], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 5, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [1, 7, 3], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [5, 1, 3], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 7], [6, 4, 8]]\n",
      "\n",
      "current node  [[0, 5, 2], [3, 1, 4], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 3, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 6, 5], [1, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [6, 1, 5], [7, 3, 8]]\n",
      "\n",
      "current node  [[0, 3, 2], [1, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 4, 2], [3, 1, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 4, 2], [3, 0, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[1, 0, 2], [3, 4, 5], [7, 6, 8]]\n",
      "\n",
      "current node  [[4, 5, 0], [3, 1, 2], [6, 7, 8]]\n",
      "\n",
      "current node  [[4, 0, 2], [3, 1, 5], [6, 7, 8]]\n",
      "\n",
      "current node  [[0, 1, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "\n",
      "Wow! finally you have found the solution.\n",
      "\n",
      "That is:\n",
      " [[0, 1, 2], [3, 4, 5], [6, 7, 8]]\n",
      "\n",
      "Total f_value :  11\n"
     ]
    }
   ],
   "source": [
    "#main function for starting execution \n",
    "import numpy as np\n",
    "from copy import deepcopy\n",
    "if __name__==\"__main__\":\n",
    " \n",
    "    print(\"\\nNOTE:- You might get 'maximum recursion depth exceeded' due to unsolvable 8-puzzle problem.\")\n",
    "    print(\"\\nstarted execution............\")\n",
    "    problem = puzzle() #object for simplicity of code\n",
    "    closedSet=[]  #visited states ,adding visited array for reducing space complexcity\n",
    "        \n",
    "    openSet=[problem.INITIAL_STATE()]#adding starting state in openList\n",
    "    \n",
    "    print(\"\\nTotal f_value : \",A_Star(problem,closedSet,openSet))"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}