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: Wrong Answer

Solution code:
import copy
N = 3


def solved(game):
    for i in range(N):
        for j in range(N):
            if (game[i][j] - 1) != i * N + j and game[i][j] != 0:
                return False
    return True


def calc_cost(game):
    cost = 0

    for i in range(N):
        for j in range(N):
            if game[i][j] != 0:
                ideal = (int((game[i][j] - 1) / N), (game[i][j] - 1) % N)
                cost += abs(i - ideal[0]) + abs(j - ideal[1])

    return cost

games = []

init = [[] for i in range(N)]

for i in range(N):
    init[i] = [int(item) for item in input().split()]
    for j in range(N):
        if init[i][j] == 0:
            #queue.put((i, j))
            zero = (i, j)

games = games + [(init, zero, calc_cost(init), 0)]
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]

while len(games) > 0:
    current = games.pop(0)
    zero = current[1]
    if solved(current[0]):
        print(current[3])
        break

    for d in direction :
        next_step = (zero[0] + d[0], zero[1] + d[1])
        if next_step[0] >= 0 and next_step[0] <= 2 and next_step[1] >= 0 and next_step[1] <= 2:

            tmp = copy.deepcopy(current[0])
            tmp[zero[0]][zero[1]], tmp[next_step[0]][next_step[1]] = tmp[next_step[0]][next_step[1]], tmp[zero[0]][zero[1]]
            tmp_cost = calc_cost(tmp)

            if tmp_cost <= current[2]:
                games = games + [(tmp, next_step, tmp_cost, current[3]+1)]

    games.sort(key=lambda x: x[2])

Submission status: Wrong Answer

Solution code:
import copy
import functools as ft
N = 3


def solved(game):
    for i in range(N):
        for j in range(N):
            if (game[i][j] - 1) != i * N + j and game[i][j] != 0:
                return False
    return True

def debug_game(game):
    for i in range(N):
        print(ft.reduce(lambda x,y: x + str(y) + " ", game[i], ""))

def convert_code(game):
    hash_code = ""
    for i in range(N):
        hash_code = hash_code + ft.reduce(lambda x,y: x + str(y), game[i], "")
    return hash_code

def calc_cost(game):
    cost = 0
    for i in range(N):
        for j in range(N):
            if game[i][j] != 0:
                ideal = (int((game[i][j] - 1) / N), (game[i][j] - 1) % N)
                cost += abs(i - ideal[0]) + abs(j - ideal[1])

    return cost

games = []
closed = []
init = [[] for i in range(N)]

for i in range(N):
    init[i] = [int(item) for item in input().split()]
    for j in range(N):
        if init[i][j] == 0:
            #queue.put((i, j))
            zero = (i, j)

games = games + [(init, zero, calc_cost(init), 0)]
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]

while len(games) > 0:
    current = games.pop(0)
    zero = current[1]
    print("Depth: "+str(current[3]) + " Cost: "+str(current[2]))
    debug_game(current[0])
    closed = closed + [convert_code(current[0])]

    if solved(current[0]):
        print(current[3])
        break

    for d in direction :
        next_step = (zero[0] + d[0], zero[1] + d[1])
        if next_step[0] >= 0 and next_step[0] <= 2 and next_step[1] >= 0 and next_step[1] <= 2:

            tmp = copy.deepcopy(current[0])
            tmp[zero[0]][zero[1]], tmp[next_step[0]][next_step[1]] = tmp[next_step[0]][next_step[1]], tmp[zero[0]][zero[1]]
            tmp_cost = calc_cost(tmp)
            hash_code = convert_code(tmp)

            if not hash_code in closed:
                games = games + [(tmp, next_step, tmp_cost, current[3]+1)]

    games.sort(key=lambda x: x[2]+x[3])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = 3
goal = "123456780"
def g(i, j, a):
    if i > j:
        i, j = j, i
    return a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:]
def solve():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    start = "".join(input().replace(" ", "") for _ in range(N))
    if start == goal:
        return 0
    zero = start.find("0")
    dp = deque([(0, start, zero, 1), (0, goal, 8, 0)])
    TABLE = {start:(1, 0), goal:(0, 0)}
    for _ in range(100):
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = 3
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    start = 8 - MAP.find("0")
    MAP = int(MAP)
    goal = 123456780
    dp = deque([(0, start, MAP)])
    LOG = {MAP}
    while dp:
        cnt, yx, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                dp.append((cnt, nyx, CM))
                LOG.add(CM)
def MAIN():
    print(solve())
MAIN()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if MAP == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Wrong Answer

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)


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):
        #print other

        otherMatrix = other.matrix
        thisMatrix = self.matrix

        if len(thisMatrix) != len(otherMatrix):
            print "failing here 0"
            return False
        for i in range(len(thisMatrix)):
            if len(thisMatrix[i]) != len(otherMatrix[i]):
                print "failing here 1"
                return False
            for j in range(len(thisMatrix[i])):
                if thisMatrix[i][j] != otherMatrix[i][j]:
                    #print "failing here expected"
                    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):
    if not frontier:
        return True
    else:
        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: Wrong Answer

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

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: Wrong Answer

Solution code:
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 __str__(self):
        return str(self.board)+"\nf: " + str(self.fValue)+ "\nsteps: "+ str(self.depth)+"\n"

    def __bool__(self):
        return True

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

class Board:
    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))
                return
        raise ValueError("Invalid Matrix!")

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

    def __eq__(self, other):
        if type(other) is not Board:
            return False
        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, limit, goalBoard, explored, astar):
    if not frontier:
        return True
    else:
        curNode = frontier.pop(0)
        explored.add(curNode)
        if curNode.board == goalBoard:
            print(curNode.depth)
            return curNode
        elif limit == 0:
            print("Limit Reached")
            return True
        elif astar:
            aStarExpansion(curNode, frontier, goalBoard, explored)
            return False

def fastSearchClient(board, limit, goalBoard, astar):
    if astar:
        frontier = [Node(board, None, heuristic(board, goalBoard), 0)]
    else:
        frontier = [Node(board, None, 0, 0)]
    explored = set()
    for i in range(limit):
        retval = fastSearch(frontier, limit - i, goalBoard, explored, astar)
        if retval:
            return retval
    return None

# 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):
    return manhattan(currentBoard)


def manhattan(currentBoard):
    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

def main():

    goalBoard = Board([[1, 2, 3], [4, 5, 6], [7, 8, 0]])

    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), 1000, goalBoard, True)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+HS(c_puz)) > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

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

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        k = abs(i-k)
        if(k >= 3):
            value += (int)(k/3)
        value += k - (int)(k/3)*3
    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    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,0,puz[0:])
    depth+=1

Submission status: Wrong Answer

Solution code:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz,costs):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+checkSumCost(costs)) > depth):
        return

    if(i != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i-1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i-1)*3+j] = HS(i,j,_c_puz[(i-1)*3+j])
        iterative(i-1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(i != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i+1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i+1)*3+j] = HS(i,j,_c_puz[(i+1)*3+j])
        iterative(i+1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j-1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j-1] = HS(i,j,_c_puz[i*3+j]-1)
        iterative(i,j-1,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j+1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j+1] = HS(i,j,_c_puz[i*3+j+1])
        iterative(i,j+1,c_depth+1,_c_puz[0:],_costs[0:])

def checkSumCost(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
    value = abs(i-ki)+abs(j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    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)]
costs = [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

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i
    costs[i] = HS(_i,_j,puz[i])

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