Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

8 Puzzle

  The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space. 

  In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.

1 3 0
4 2 5
7 8 6

  You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).

1 2 3
4 5 6
7 8 0

  Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Input

  The $3 \times 3$ integers denoting the pieces or space are given.

Output

  Print the fewest steps in a line.

Constraints

There is a solution.

Sample Input 

1 3 0
4 2 5
7 8 6

Sample Output

4



Sample input:
1 3 0
4 2 5
7 8 6


Sample output:
4

Submission status: Runtime Error

Solution code:
import time
import math

class Node:
    def __init__(self, board, parent, fValue, depth):
        self.board = board
        self.parent = parent
        self.fValue = fValue
        self.depth = depth

    def __eq__(self, other):
        return self.board == other.board

    def __lt__(self, other):
        return self.fValue < other.fValue

    def __hash__(self):
        return hash(self.board)

    def __bool__(self):
        return True

class Board:
    # The 8-puzzle board representation #
    def __init__(self, matrix):
        self.matrix = matrix

        for i in range(len(matrix)):
            if 0 in matrix[i]:
                self.blankPos = (i, matrix[i].index(0))

    def __str__(self):
        s = ""
        for i in range(len(self.matrix)):
            s += str(self.matrix[i]) + "\n"
        return s + "\n"

    def __eq__(self, other):
        otherMatrix = other.matrix
        thisMatrix = self.matrix

        if len(thisMatrix) != len(otherMatrix):
            return False
        for i in range(len(thisMatrix)):
            if len(thisMatrix[i]) != len(otherMatrix[i]):
                return False
            for j in range(len(thisMatrix[i])):
                if thisMatrix[i][j] != otherMatrix[i][j]:
                    return False
        return True

    def duplicate(self):
        newMatrix = []
        for i in range(len(self.matrix)):
            newMatrix.append([])
            for j in range(len(self.matrix[i])):
                newMatrix[i].append(self.matrix[i][j])
        return Board(newMatrix)

    def findElement(self, elem):
        for i in range(len(self.matrix)):
            for j in range(len(self.matrix[i])):
                if self.matrix[i][j] == elem:
                    return (i, j)
        return None

    def slideBlank(self, dir):
        # dir is a tuple (deltaY,deltaX)
        if dir not in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            raise ValueError("Invalid dir")
        newBlankPos = (self.blankPos[0] + dir[0], self.blankPos[1] + dir[1])
        if newBlankPos[0] < 0 or newBlankPos[0] > len(self.matrix) - 1:
            return None
        elif newBlankPos[1] < 0 or newBlankPos[1] > len(self.matrix[0]) - 1:
            return None
        else:
            newBoard = self.duplicate()
            saveVal = newBoard.matrix[self.blankPos[0] + dir[0]][self.blankPos[1] + dir[1]]
            newBoard.matrix[self.blankPos[0] + dir[0]][self.blankPos[1] + dir[1]] = 0
            newBoard.matrix[self.blankPos[0]][self.blankPos[1]] = saveVal
            newBoard.blankPos = (self.blankPos[0] + dir[0], self.blankPos[1] + dir[1])
            return newBoard

    def __hash__(self):
        s = 0
        for i in range(len(self.matrix)):
            for j in range(len(self.matrix[i])):
                s *= 10
                s += self.matrix[i][j]

        return s


def fastSearch(frontier, goalBoard, explored):
    curNode = frontier.pop(0)
    explored.add(curNode)
    if curNode.board == goalBoard:
        print(curNode.depth)
        return True
    aStarExpansion(curNode, frontier, goalBoard, explored)
    return False


def fastSearchClient(board, goalBoard):
    frontier = [Node(board, None, heuristic(board, goalBoard), 0)]
    explored = set()

    limit = 0

    while (limit < 1000):
        retval = fastSearch(frontier, goalBoard, explored)
        if retval:
            return
        limit += 1
    return

# Function to expand the frontier using aStar #
def aStarExpansion(currentNode, frontier, goalBoard, explored):
    sideLength = len(currentNode.board.matrix)
    pos = currentNode.board.blankPos
    depth = currentNode.depth + 1
    toInsert = []

    # if we can move there, make a node and put it in toInsert
    if pos[0] != 0:
        upCost = depth + heuristic(currentNode.board.slideBlank((-1, 0)), goalBoard)
        upNode = Node(currentNode.board.slideBlank((-1, 0)), currentNode, upCost, depth)
        toInsert.append(upNode)
    if pos[0] != sideLength - 1:
        downCost = depth + heuristic(currentNode.board.slideBlank((1, 0)), goalBoard)
        downNode = Node(currentNode.board.slideBlank((1, 0)), currentNode, downCost, depth)
        toInsert.append(downNode)
    if pos[1] != 0:
        leftCost = depth + heuristic(currentNode.board.slideBlank((0, -1)), goalBoard)
        leftNode = Node(currentNode.board.slideBlank((0, -1)), currentNode, leftCost, depth)
        toInsert.append(leftNode)
    if pos[1] != sideLength - 1:
        rightCost = depth + heuristic(currentNode.board.slideBlank((0, 1)), goalBoard)
        rightNode = Node(currentNode.board.slideBlank((0, 1)), currentNode, rightCost, depth)
        toInsert.append(rightNode)

    # if we've already been there, we don't want to try that board again
    for node in explored:
        for insertNode in toInsert:
            if insertNode == node:
                toInsert.remove(insertNode)

    # now we are putting the nodes to be inserted into the correct place in frontier
    for node in toInsert:
        for i in range(len(frontier) + 1):
            if i == len(frontier):
                frontier.append(node)
                break
            if frontier[i] > node:
                frontier.insert(i, node)
                break

def heuristic(currentBoard, goalBoard):
    currentMatrix = currentBoard.matrix
    sum = 0

    for i in range(len(currentMatrix)):
        for j in range(len(currentMatrix[i])):
            cur = currentMatrix[i][j]

            if cur % 3 == 0:
                curx = 3
            else:
                curx = cur % 3

            if cur != 0:
                sum += abs(curx - (j + 1)) + abs(math.ceil(cur / 3) - (i + 1))

    return sum

arr = [[1 for i in range(3)] for j in range(3)]

for i in range(3):
    arr[i][0], arr[i][1], arr[i][2] = raw_input().split()


for i in range(3):
    for j in range(3):
        arr[i][j] = int(arr[i][j])

fastSearchClient(Board(arr), Board([[1, 2, 3], [4, 5, 6], [7, 8, 0]]))

Submission status: Runtime Error

Solution code:
import time import math class Node: def __init__(self, board, parent, fValue, depth): self.board = board self.parent = parent self.fValue = fValue self.depth = depth def __eq__(self, other): return self.board == other.board def __lt__(self, other): return self.fValue < other.fValue def __hash__(self): return hash(self.board) def __bool__(self): return True class Board: # The 8-puzzle board representation # def __init__(self, matrix): self.matrix = matrix for i in range(len(matrix)): if 0 in matrix[i]: self.blankPos = (i, matrix[i].index(0)) def __str__(self): s = "" for i in range(len(self.matrix)): s += str(self.matrix[i]) + "\n" return s + "\n" def __eq__(self, other): otherMatrix = other.matrix thisMatrix = self.matrix if len(thisMatrix) != len(otherMatrix): return False for i in range(len(thisMatrix)): if len(thisMatrix[i]) != len(otherMatrix[i]): return False for j in range(len(thisMatrix[i])): if thisMatrix[i][j] != otherMatrix[i][j]: return False return True def duplicate(self): newMatrix = [] for i in range(len(self.matrix)): newMatrix.append([]) for j in range(len(self.matrix[i])): newMatrix[i].append(self.matrix[i][j]) return Board(newMatrix) def findElement(self, elem): for i in range(len(self.matrix)): for j in range(len(self.matrix[i])): if self.matrix[i][j] == elem: return (i, j) return None def slideBlank(self, dir): # dir is a tuple (deltaY,deltaX) if dir not in [(0, 1), (0, -1), (-1, 0), (1, 0)]: raise ValueError("Invalid dir") newBlankPos = (self.blankPos[0] + dir[0], self.blankPos[1] + dir[1]) if newBlankPos[0] < 0 or newBlankPos[0] > len(self.matrix) - 1: return None elif newBlankPos[1] < 0 or newBlankPos[1] > len(self.matrix[0]) - 1: return None else: newBoard = self.duplicate() saveVal = newBoard.matrix[self.blankPos[0] + dir[0]][self.blankPos[1] + dir[1]] newBoard.matrix[self.blankPos[0] + dir[0]][self.blankPos[1] + dir[1]] = 0 newBoard.matrix[self.blankPos[0]][self.blankPos[1]] = saveVal newBoard.blankPos = (self.blankPos[0] + dir[0], self.blankPos[1] + dir[1]) return newBoard def __hash__(self): s = 0 for i in range(len(self.matrix)): for j in range(len(self.matrix[i])): s *= 10 s += self.matrix[i][j] return s def fastSearch(frontier, goalBoard, explored): curNode = frontier.pop(0) explored.add(curNode) if curNode.board == goalBoard: print(curNode.depth) return True aStarExpansion(curNode, frontier, goalBoard, explored) return False def fastSearchClient(board, goalBoard): frontier = [Node(board, None, heuristic(board, goalBoard), 0)] explored = set() limit = 0 while (limit < 1000): retval = fastSearch(frontier, goalBoard, explored) if retval: return limit += 1 return # Function to expand the frontier using aStar # def aStarExpansion(currentNode, frontier, goalBoard, explored): sideLength = len(currentNode.board.matrix) pos = currentNode.board.blankPos depth = currentNode.depth + 1 toInsert = [] # if we can move there, make a node and put it in toInsert if pos[0] != 0: upCost = depth + heuristic(currentNode.board.slideBlank((-1, 0)), goalBoard) upNode = Node(currentNode.board.slideBlank((-1, 0)), currentNode, upCost, depth) toInsert.append(upNode) if pos[0] != sideLength - 1: downCost = depth + heuristic(currentNode.board.slideBlank((1, 0)), goalBoard) downNode = Node(currentNode.board.slideBlank((1, 0)), currentNode, downCost, depth) toInsert.append(downNode) if pos[1] != 0: leftCost = depth + heuristic(currentNode.board.slideBlank((0, -1)), goalBoard) leftNode = Node(currentNode.board.slideBlank((0, -1)), currentNode, leftCost, depth) toInsert.append(leftNode) if pos[1] != sideLength - 1: rightCost = depth + heuristic(currentNode.board.slideBlank((0, 1)), goalBoard) rightNode = Node(currentNode.board.slideBlank((0, 1)), currentNode, rightCost, depth) toInsert.append(rightNode) # if we've already been there, we don't want to try that board again for node in explored: for insertNode in toInsert: if insertNode == node: toInsert.remove(insertNode) # now we are putting the nodes to be inserted into the correct place in frontier for node in toInsert: for i in range(len(frontier) + 1): if i == len(frontier): frontier.append(node) break if frontier[i] > node: frontier.insert(i, node) break def heuristic(currentBoard, goalBoard): currentMatrix = currentBoard.matrix sum = 0 for i in range(len(currentMatrix)): for j in range(len(currentMatrix[i])): cur = currentMatrix[i][j] if cur % 3 == 0: curx = 3 else: curx = cur % 3 if cur != 0: sum += abs(curx - (j + 1)) + abs(math.ceil(cur / 3) - (i + 1)) return sum arr = [[1 for i in range(3)] for j in range(3)] for i in range(3): arr[i][0], arr[i][1], arr[i][2] = input().split() for i in range(3): for j in range(3): arr[i][j] = int(arr[i][j]) fastSearchClient(Board(arr), Board([[1, 2, 3], [4, 5, 6], [7, 8, 0]]))

Submission status: Runtime Error

Solution code:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(simpleHS(swap_puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+c_dWithH) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Submission status: Runtime Error

Solution code:
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append(sumcost,(0,i,j,0,puz))
    global finding

    while len(q):
        c_dWithH, items = q.pop(0)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        print(c_depth)
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),(c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),(c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),(c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),(c_depth+1,_i,_j+1,3,swap_puz))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Submission status: Runtime Error

Solution code:
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append(sumcost,0,i,j,0,puz)
    global finding

    while len(q):
        c_dWithH, items = q.pop(0)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        print(c_depth)
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),c_depth+1,_i-1,_j,2,swap_puz)
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),c_depth+1,_i+1,_j,1,swap_puz)
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),c_depth+1,_i,_j-1,4,swap_puz)
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),c_depth+1,_i,_j+1,3,swap_puz)

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Submission status: Runtime Error

Solution code:
class Puzzle:
    def __init__(self, field=None, path=''):
        self.f = field
        self.space = None
        for i in range(9):
            if self.f[i] == 9:
                self.space = i
        self.path = path

    def __lt__(self, pzl): # <
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] > pzl.f[i]
        return False

    def __gt__(self, pzl): # >
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] < pzl.f[i]
        return False

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
dir = ['u', 'l', 'd', 'r']

def is_target(pzl):
    for i in range(9):
        if pzl.f[i] != i+1:
            return False
    return True

def bfs(pzl):
    queue = deque([])
    V = {}
    pzl.path = ''
    queue.append(pzl)
    V[str(pzl.f)] = True
    if is_target(pzl): return u.path

    while len(queue) != 0:
        u = queue.popleft()
        sx, sy = u.space//3, u.space%3
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= 3 or ty >= 3:
                continue
            v = Puzzle(field=[u.f[i] for i in range(9)], path=u.path)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if str(v.f) not in V:
                V[str(v.f)] = True
                v.path += dir[r]
                if is_target(v): return v.path
                queue.append(v)
    return 'unsolvable'

field = []
for i in range(3):
    field.extend(list(map(int, input().split(' '))))

for i in range(9):
    if field[i] == 0: field[i] = 9

pzl = Puzzle(field=field)
ans= bfs(pzl)
print(len(ans))

Submission status: Runtime Error

Solution code:
class Puzzle:
    def __init__(self, field=None, path=''):
        self.f = field
        self.space = None
        for i in range(9):
            if self.f[i] == 9:
                self.space = i
        self.path = path

    def __lt__(self, pzl): # <
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] > pzl.f[i]
        return False

    def __gt__(self, pzl): # >
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] < pzl.f[i]
        return False

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
dir = ['u', 'l', 'd', 'r']

def is_target(pzl):
    for i in range(9):
        if pzl.f[i] != i+1:
            return False
    return True

def bfs(pzl):
    queue = deque([])
    V = {}
    pzl.path = ''
    queue.append(pzl)
    V[str(pzl.f)] = True
    if is_target(pzl): return u.path

    while len(queue) != 0:
        u = queue.popleft()
        sx, sy = u.space//3, u.space%3
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= 3 or ty >= 3:
                continue
            v = Puzzle(field=[u.f[i] for i in range(9)], path=u.path)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if str(v.f) not in V:
                V[str(v.f)] = True
                v.path += dir[r]
                if is_target(v): return v.path
                queue.append(v)
    return 'unsolvable'

field = []
for i in range(3):
    field.extend(list(map(int, input().split(' '))))

for i in range(9):
    if field[i] == 0: field[i] = 9

pzl = Puzzle(field=field)
ans= bfs(pzl)
print(len(ans))

Submission status: Runtime Error

Solution code:
from collections import deque, OrderedDict

class Puzzle:
    def __init__(self, field=None, path=''):
        self.f = field
        self.space = None
        for i in range(9):
            if self.f[i] == 9:
                self.space = i
        self.path = path

    def __lt__(self, pzl): # <
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] > pzl.f[i]
        return False

    def __gt__(self, pzl): # >
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] < pzl.f[i]
        return False

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
dir = ['u', 'l', 'd', 'r']

def is_target(pzl):
    for i in range(9):
        if pzl.f[i] != i+1:
            return False
    return True

def bfs(pzl):
    queue = deque([])
    V = {}
    pzl.path = ''
    queue.append(pzl)
    V[str(pzl.f)] = True
    if is_target(pzl): return u.path

    while len(queue) != 0:
        u = queue.popleft()
        sx, sy = u.space//3, u.space%3
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= 3 or ty >= 3:
                continue
            v = Puzzle(field=[u.f[i] for i in range(9)], path=u.path)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if str(v.f) not in V:
                V[str(v.f)] = True
                v.path += dir[r]
                if is_target(v): return v.path
                queue.append(v)
    return 'unsolvable'

field = []
for i in range(3):
    field.extend(list(map(int, input().split(' '))))

for i in range(9):
    if field[i] == 0: field[i] = 9

pzl = Puzzle(field=field)
ans= bfs(pzl)
print(len(ans))