Problem:
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

Solution (Python):
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)}
    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()

Solution (Python):
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))
    start = 8 - MAP.find("0")
    MAP = int(MAP)
    if MAP == goal:
        return 0
    dp = deque([(0, start, MAP)])
    LOG = {MAP}
    while dp:
        cnt, yx, M = dp.popleft()
        if M == goal:
            return cnt
        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()

Solution (Python):
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 start == 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()

Solution (Python):


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 = Puzzle()
                v[:] = u[:]
                v.path = u.path
                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))

Solution (Python):

import sys
from itertools import chain


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


def serialize_board(board):
    return ":".join(board)


def get_empty_pos(board, width, height):
    for i, cell in enumerate(board):
        if cell == "0":
            return i


def get_all_possible_next_boards(board, height, width, empty_pos=None):
    if empty_pos is None:
        empty_pos = get_empty_pos(board, height, width)
    next_boards = []
    x, y = empty_pos % width, empty_pos // height
    
    if x > 0:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos - 1
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    
    if x < width - 1:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos + 1
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    
    if y > 0:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos - height
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    
    if y < height - 1:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos + height
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))

    return next_boards


def resolve(board, height, width):
    
    known_serialized_boards = set([serialize_board(board)])
    
    completed_board = get_completed_board(width, height)
    known_serialized_completed_boards = set([serialize_board(completed_board)])
    if known_serialized_boards & known_serialized_completed_boards:
        return 0
    current_boards = [(board, None)]
    current_completed_boards = [(get_completed_board(width, height), None)]
    step_count = 1
    while step_count <= 45:
        
        next_boards = []
        for board, empty_pos in current_boards:
            
            tmp_next_boards = get_all_possible_next_boards(board, height, width, empty_pos)
            filtered_next_board = []
            for board, empty_pos in tmp_next_boards:
                serialized_board = serialize_board(board)
                if serialized_board not in known_serialized_boards:
                    known_serialized_boards.add(serialized_board)
                    filtered_next_board.append((board, empty_pos))
            next_boards.extend(filtered_next_board)

        if known_serialized_boards & known_serialized_completed_boards:
            return step_count

        step_count = step_count + 1
        current_boards = next_boards

        
        next_completed_boards = []
        for board, empty_pos in current_completed_boards:
            
            tmp_next_boards = get_all_possible_next_boards(board, height, width, empty_pos)
            filtered_next_board = []
            for board, empty_pos in tmp_next_boards:
                serialized_board = serialize_board(board)
                if serialized_board not in known_serialized_completed_boards:
                    known_serialized_completed_boards.add(serialized_board)
                    filtered_next_board.append((board, empty_pos))
            next_completed_boards.extend(filtered_next_board)

        if known_serialized_boards & known_serialized_completed_boards:
            return step_count
        step_count = step_count + 1
        current_completed_boards = next_completed_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])
    board = list(chain.from_iterable(board))
    print(resolve(board, height, width))


if __name__ == '__main__':
    main()

Solution (Python):
import sys;
import heapq

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

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    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

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 = sumCost(puz)

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

Solution (Python):
import sys;
import heapq

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

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(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(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    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

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 = sumCost(puz)

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

Solution (Python):
from collections import deque

MOVE = {'U': (0, -1), 'D': (0, 1), 'L': (-1, 0), 'R': (1, 0)}

def next(numbers):
    for d in 'UDLR':
        z = numbers.index(0)
        tx, ty = z % 3 + MOVE[d][0], z // 3 + MOVE[d][1]
        if 0 <= tx < 3 and 0 <= ty < 3:
            t = ty * 3 + tx
            result = list(numbers)
            result[z], result[t] = numbers[t], 0
            yield d, tuple(result)

def bfs(puzzle):
    queue = deque([(puzzle, '')])
    seen = set()
    while queue:
        numbers, route = queue.popleft()
        seen.add(numbers)
        if numbers == (1, 2, 3, 4, 5, 6, 7, 8, 0):
            return route
        for direction, new_numbers in next(numbers):
            if new_numbers not in seen:
                queue.append((new_numbers, route + direction))
    return route

puzzle = ()
for i in range(3):
    a,b,c = map(int, input().split())
    puzzle += (a,b,c)

print(len(bfs(puzzle)))

Solution (Python):

import copy
z = 0
[N, d] = [3, 0]
check_flag = [[1, 2, 3, 4,  1, 2, 3, 4,  1, 2, 3, 4],
              [2, 3, 4, 1,  2, 3, 4, 1,  2, 3, 4, 1],
              [3, 4, 1, 2,  3, 4, 1, 2,  3, 4, 1, 2],
              [4, 1, 2, 3,  4, 1, 2, 3,  4, 1, 2, 3],
              [3, 2, 1, 4,  3, 2, 1, 4,  3, 2, 1, 4],
              [2, 1, 4, 3,  2, 1, 4, 3,  2, 1, 4, 3],
              [1, 4, 3, 2,  1, 4, 3, 2,  1, 4, 3, 2],
              [4, 3, 2, 1,  4, 3, 2, 1,  4, 3, 2, 1]]

start = []
goal = [[i + j*N for i in range(1, N + 1)] for j in range(N)]
goal[2][2] = 0
for i in range(N):
    start.append(list(map(int, input().split())))


def manhattan(value, pairs):
    h = 0

    if value == 1:
        h = (pairs[0] + pairs[1])
    if value == 2:
        h = (pairs[0] + abs(pairs[1] - 1))
    if value == 3:
        h = (pairs[0] + abs(pairs[1] - 2))
    
    if value == 4:
        h = (abs(pairs[0] - 1) + pairs[1])
    if value == 5:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 1)) 
    if value == 6:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 2))
        
    if value == 7:
        h = (abs(pairs[0] - 2) + pairs[1])      
    if value == 8:
        h = (abs(pairs[0] - 2) + abs(pairs[1] - 1))
        
    return h

def flag_array(flag, input):

    flag.pop(0)
    flag.append(input)
    return flag


s_h = 0
for i in range(N):
    for j in range(N):
        s_h += manhattan(start[i][j], [i, j])



for i in range(N):
        check = start[i].count(0)
        if check != 0:
            [s_r, s_c] = [i, start[i].index(0)]
            break
        if i == 3:
            print("Error")

while True:
    d += 1
    queue = []
    flag = [0 for i in range(12)]
    queue.append([s_h, start, 0, [s_r, s_c], flag])

    
    while len(queue) != 0:
        
        short_n = queue.pop(0)
        h = short_n[0] - short_n[2]
        state = short_n[1]
        g = short_n[2]
        [r, c] = short_n[3]
        flag = short_n[4]
        
        
        
            
            
            

        if h == 0:
            print(short_n[2])
            
            break
        """
        if flag in check_flag:
            z += 1
            continue
        """
        if r - 1 >= 0 and flag[len(flag) - 1] != 3:
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            h = short_n[0] - short_n[2] - manhattan(temp[r - 1][c], [r - 1, c]) + manhattan(temp[r - 1][c], [r, c])
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            
            
            
            
            
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r - 1, c], flag_array(temp_array, 1)])
        
        if c + 1 < N and flag[len(flag) - 1] != 4:
            
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            
            h = short_n[0] - short_n[2] - manhattan(temp[r][c + 1], [r, c + 1]) + manhattan(temp[r][c + 1], [r, c])
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            
            
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c + 1], flag_array(temp_array, 2)])

        if r + 1 < N and flag[len(flag) - 1] != 1:
            
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            
            h = short_n[0] - short_n[2] - manhattan(temp[r + 1][c], [r + 1, c]) + manhattan(temp[r + 1][c], [r, c])
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            
            
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r + 1, c], flag_array(temp_array, 3)])
        
        if c - 1 >= 0 and flag[len(flag) - 1] != 2:
            
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            h = short_n[0] - short_n[2] - manhattan(temp[r][c - 1], [r, c - 1]) + manhattan(temp[r][c - 1], [r, c])
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c - 1], flag_array(temp_array, 4)])
                
        queue.sort(key = lambda data:data[0])
        queue.sort(key = lambda data:data[2], reverse = True)

        data = []
        g_data = []
        
        """
        for i in range(len(queue)):
            data.append(str(queue[i][0]))
            g_data.append(str(queue[i][2]))
            
        print("g+h: ",' '.join(data))
        print("g: ",' '.join(g_data))
        """
        
        

    if state == goal:
        break

Solution (Python):

import copy
[N, d] = [3, 0]
start = []
goal = [[i + j*N for i in range(1, N + 1)] for j in range(N)]
goal[2][2] = 0
for i in range(N):
    start.append(list(map(int, input().split())))


def manhattan(value, pairs):
    h = 0

    if value == 1:
        h = (pairs[0] + pairs[1])
    if value == 2:
        h = (pairs[0] + abs(pairs[1] - 1))
    if value == 3:
        h = (pairs[0] + abs(pairs[1] - 2))
    
    if value == 4:
        h = (abs(pairs[0] - 1) + pairs[1])
    if value == 5:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 1)) 
    if value == 6:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 2))
        
    if value == 7:
        h = (abs(pairs[0] - 2) + pairs[1])      
    if value == 8:
        h = (abs(pairs[0] - 2) + abs(pairs[1] - 1))
        
    return h

s_h = 0
for i in range(N):
    for j in range(N):
        s_h += manhattan(start[i][j], [i, j])

for i in range(N):
        check = start[i].count(0)
        if check != 0:
            [s_r, s_c] = [i, start[i].index(0)]
            break
        if i == 3:
            print("Error")

while True:
    d += 1
    flag = 0
    queue = [[s_h, start, 0, [s_r, s_c], flag]]
    
    while len(queue) != 0:
        short_n = queue.pop(0)
        h = short_n[0] - short_n[2]
        state = short_n[1]
        g = short_n[2]
        [r, c] = short_n[3]
        flag = short_n[4]
        
        if h == 0:
            print(short_n[2])
            break
       
        if r - 1 >= 0 and flag != 3:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r - 1][c], [r - 1, c]) + manhattan(temp[r - 1][c], [r, c])
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r - 1, c], 1])
        
        if c + 1 < N and flag != 4:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r][c + 1], [r, c + 1]) + manhattan(temp[r][c + 1], [r, c])
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c + 1], 2])

        if r + 1 < N and flag != 1:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r + 1][c], [r + 1, c]) + manhattan(temp[r + 1][c], [r, c])
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r + 1, c], 3])
        
        if c - 1 >= 0 and flag != 2:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r][c - 1], [r, c - 1]) + manhattan(temp[r][c - 1], [r, c])
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c - 1], 4])
                
        queue.sort(key = lambda data:data[0])
        queue.sort(key = lambda data:data[2], reverse = True)

        data = []
        g_data = []

    if state == goal:
        break

Solution (Python):
 
goal = ((1, 2, 3), (4, 5, 6), (7, 8, 0))

parents = {}
total = {}
flag = True

initial = []
position = []
for i in range(3):
	a, b, c = map(int, input().split())
	if a == 0:
		position.extend([i, 0])
	elif b == 0:
		position.extend([i, 1])
	elif c == 0:
 		position.extend([i, 2])
	initial.append( (a, b, c) )

parents[tuple(initial)] = position
total[tuple(initial)] = 1

count = 0

if tuple(initial) == goal:
	flag = False

while flag:
	count += 1
	children = {}
	for par_key in parents.keys():
		position = parents[par_key]

		if position[0] < 2:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]+1][position[1]]
			child[position[0]+1][position[1]] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0]+1, position[1]]
				total[child_tuple] = 1

		if position[0] > 0:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]-1][position[1]]
			child[position[0]-1][position[1]] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0]-1, position[1]]
				total[child_tuple] = 1

		if position[1] < 2:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]][position[1]+1]
			child[position[0]][position[1]+1] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0], position[1]+1]
				total[child_tuple] = 1

		if position[1] > 0:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]][position[1]-1]
			child[position[0]][position[1]-1] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0], position[1]-1]
				total[child_tuple] = 1

	parents = children

print(count)

Solution (Python):
 
goal = ((1, 2, 3), (4, 5, 6), (7, 8, 0))

parents = {}
total = {}
flag = True

initial = []
position = []
for i in range(3):
	a, b, c = map(int, input().split())
	if a == 0:
		position.extend([i, 0])
	elif b == 0:
		position.extend([i, 1])
	elif c == 0:
 		position.extend([i, 2])
	initial.append( (a, b, c) )

parents[tuple(initial)] = position
total[tuple(initial)] = 1

count = 0

if tuple(initial) == goal:
	flag = False

while flag:
	count += 1
	children = {}
	for par_key in parents.keys():
		position = parents[par_key]

		if position[0] < 2:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]+1][position[1]]
			child[position[0]+1][position[1]] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0]+1, position[1]]
				total[child_tuple] = 1

		if position[0] > 0:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]-1][position[1]]
			child[position[0]-1][position[1]] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0]-1, position[1]]
				total[child_tuple] = 1

		if position[1] < 2:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]][position[1]+1]
			child[position[0]][position[1]+1] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0], position[1]+1]
				total[child_tuple] = 1

		if position[1] > 0:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]][position[1]-1]
			child[position[0]][position[1]-1] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0], position[1]-1]
				total[child_tuple] = 1

	parents = children

print(count)

Solution (Python):

import sys
import queue

SPACE = 0

adjacents_list = (
    (1, 3),       
    (0, 2, 4),    
    (1, 5),       
    (0, 4, 6),    
    (1, 3, 5, 7), 
    (2, 4, 8),    
    (3, 7),       
    (4, 6, 8),    
    (5, 7)        
)

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = {}
    history[tuple(start)] = True
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if tuple(board) in history:
                 continue
            if board == goal:
                return go_back(state)
            history[tuple(board)] = True
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print(mininum_steps(initial_board, goal))