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: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = tuple(sum([input().split() for _ in range(N)], []))
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = {MAP}
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for ny, nx in ((y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)):
            if 0 <= ny < N and 0 <= nx < N:
                CM = list(deepcopy(M))
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                CM = tuple(CM)
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.add(CM)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
import queue
board = []
for i in range(3):
    board.extend(list(map(int, input().split())))

q = queue.PriorityQueue()
q.put((0, board))

while True:
    entry = q.get()
    step = entry[0]
    b = entry[1]
    if b == [1, 2, 3, 4, 5, 6, 7, 8, 0]:
        print(step)
        break
    i = b.index(0)
    step += 1

    if i != 0:
        b_new = list(b)
        b_new[i - 1], b_new[i] = 0, b_new[i - 1]
        q.put((step, b_new))
    if i != len(b) - 1:
        b_new = list(b)
        b_new[i], b_new[i + 1] = b_new[i + 1], 0
        q.put((step, b_new))
    if i > 2:
        b_new = list(b)
        b_new[i - 3], b_new[i] = 0, b_new[i - 3]
        q.put((step, b_new))
    if i < 6:
        b_new = list(b)
        b_new[i], b_new[i + 3] = b_new[i + 3], 0
        q.put((step, b_new))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        #self[:] = [None] * size
        self.space = None
        self.path = ""

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    def isTarget(p):
        for i in range(N2):
            if p[i] != i+1:
                return False
        return True

    def bfs(s):
        cnt = 0
        Q = deque()
        V = []
        Q.append(s)
        V.append(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.append(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    def isTarget(p):
        for i in range(N2):
            if p[i] != i+1:
                return False
        return True

    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.deepcopy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    def isTarget(p):
        for i in range(N2):
            if p[i] != i+1:
                return False
        return True

    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]
        
    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = copy.copy(u)
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy


def get_completed_board(height, width):
    return [[str((y * width + x + 1) % (width * height)) for x in range(width)] for y in range(height)]


def serialize_board(board):
    return ":".join(list(map(lambda cell: ",".join(cell), board)))


def get_empty_pos(board):
    for y, row in enumerate(board):
        for x, cell in enumerate(row):
            if cell == "0":
                return (x, y)


def get_all_possible_next_boards(board, height, width, empty_pos=None):
    if empty_pos is None:
        empty_pos = get_empty_pos(board)
    next_boards = []
    # 左との入れ替え
    if empty_pos[0] > 0:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0] - 1] = \
            next_board[empty_pos[1]][empty_pos[0] - 1], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0] - 1, empty_pos[1])))
    # 右との入れ替え
    if empty_pos[0] < width - 1:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0] + 1] = \
            next_board[empty_pos[1]][empty_pos[0] + 1], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0] + 1, empty_pos[1])))
    # 上との入れ替え
    if empty_pos[1] > 0:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1] - 1][empty_pos[0]] = \
            next_board[empty_pos[1] - 1][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0], empty_pos[1] - 1)))
    # 下との入れ替え
    if empty_pos[1] < height - 1:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1] + 1][empty_pos[0]] = \
            next_board[empty_pos[1] + 1][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0], empty_pos[1] + 1)))
    return next_boards


def resolve(board, height, width):
    # 既知の盤面を保存
    known_serialized_boards = set([])
    # 正解の盤面を保存
    completed_serialized_board = serialize_board(get_completed_board(width, height))
    step_count = 0
    current_boards = [(board, None)]
    while step_count <= 45:
        next_boards = []
        for board, empty_pos in current_boards:
            serialized_board = serialize_board(board)
            # 正答があった場合はステップ数を返して終了
            if serialized_board == completed_serialized_board:
                return step_count
            # 既知の盤面は後続の処理対象としない
            if serialized_board in known_serialized_boards:
                continue
            else:
                known_serialized_boards.add(serialized_board)
            # 次のステップでの現れ得る局面を全て取得
            next_boards.extend(get_all_possible_next_boards(board, height, width, empty_pos))
        current_boards = next_boards
        step_count = step_count + 1
        # print((step_count, len(known_serialized_boards), len(current_boards)))
    return None


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    lines = filter(lambda line: line, lines)
    board = list(map(lambda line: line.split(" "), lines))
    height = len(board)
    width = len(board[0])
    step_count = resolve(board, height, width)
    print(step_count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 > 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 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(8)]
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: Time Limit Exceeded

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+simpleHS(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
    if(c_puz[8] == 0):
        count+=1
    return count

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(8)]
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: Time Limit Exceeded

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])
        _i = (int)(i/3)
        _j = i - _i
        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)]

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: Time Limit Exceeded

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])
        _i = (int)(i/3)
        _j = i - _i
        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)]

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 = HS(puz)
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1

Submission status: Time Limit Exceeded

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(finding == 1):
            return
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
        if(finding == 1):
            return
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
        if(finding == 1):
            return
    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])
        _i = (int)(i/3)
        _j = i - _i
        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)]

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: Time Limit Exceeded

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 or (c_depth+simpleHS(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])
        _i = (int)(i/3)
        _j = i - _i
        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)]

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: Time Limit Exceeded

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 or (c_depth+simpleHS(c_puz)) > depth):
        return

    if(i != 0 and finding != 1):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2 and finding != 1):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0 and finding != 1):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2 and finding != 1):
        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])
        _i = (int)(i/3)
        _j = i - _i
        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)]

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: Time Limit Exceeded

Solution code:
import sys;
import heapq

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

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

        if((c_depth+simpleHS(c_puz)) > depth):
            continue

        if(_i != 0):
            heapq.heappush(q,(c_depth+1,_i-1,_j,swapPuz(c_puz[0:],_i,_j,_i-1,_j)))
        if(_i != 2):
            heapq.heappush(q,(c_depth+1,_i+1,_j,swapPuz(c_puz[0:],_i,_j,_i+1,_j)))
        if(_j != 0):
            heapq.heappush(q,(c_depth+1,_i,_j-1,swapPuz(c_puz[0:],_i,_j,_i,_j-1)))
        if(_j != 2):
            heapq.heappush(q,(c_depth+1,_i,_j+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])
        _i = (int)(i/3)
        _j = i - _i
        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)]

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