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
N2 = 9

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

class Puzzle:
    def __init__(self, f=None, space=None, path=None):
        if f is None:
            self.f = []
        else:
            self.f = f
        self.space = space
        self.path = path

    def __lt__(self, p):
        for i in range(N2):
            if self.f[i] == p.f[i]:
                continue
            return self.f[i] > p.f[i]
        return False


def isTarget(p):
    for i in range(N2):
        if p.f[i] != (i + 1):
            return False
    return True


def bfs(s):
    q = deque()
    dic = {}
    s.path = ''
    q.append(s)
    dic[tuple(s.f)] = True

    while len(q) != 0:
        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 = Puzzle(u.f[:], u.space, u.path)
            v.f[u.space], v.f[tx * N + ty] = v.f[tx * N + ty], v.f[u.space]
            v.space = tx * N + ty
            key = tuple(v.f)
            if key not in dic:
                dic[key] = True
                v.path += dirc[r]
                q.append(v)

    return 'unsolvable'


if __name__ == '__main__':
    p = Puzzle()
    for i in range(N):
        line = [int(v) for v in input().split()]
        for j in range(N):
            if line[j] == 0:
                line[j] = N2
                p.space = i * N + j
        p.f.extend(line)

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

Solution (Python):
from collections import deque
def move(P):
    for i in range(3):
        for j in range(3):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 2:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 2:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def dpkey(P):
    tmp = ""
    for i in P:
        for j in i:
            tmp += str(j)
    return tmp

A = [[int(i) for i in input().split()] for _ in range(3)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "123456780":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "123456780":
    ans = 0
print(ans)

Solution (Python):
import sys
import queue

N = 3
f= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = queue.Queue()
V = dict()

Q.put([f,f.index('0'),0])
V[f] = True

while not Q.empty():
    u = Q.get()
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
        if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1                                                    
            Q.put(v)

print(u[2])

Solution (Python):
import sys
import queue

N = 3

f = ''.join(sys.stdin.readline().split())
f += ''.join(sys.stdin.readline().split())
f += ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
        if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1 
            Q.append(v)

print(u[2])

Solution (Python):
import sys, itertools
f = sys.stdin

start = [line.split() for line in f]
start = tuple(int(x) for y in start for x in y)
end =(1, 2, 3, 4, 5, 6,7, 8, 0)

d = {start:0}

def next_board(b):
    brank = b.index(0)
    if brank % 3:
        yield b[:brank - 1] + (b[brank], b[brank - 1]) + b[brank + 1:]
    if brank // 3:
        yield b[:brank - 3] + (b[brank],)+ b[brank - 2:brank] +  (b[brank - 3],) + b[brank + 1:]
    if brank % 3 != 2:
        yield b[:brank] + (b[brank + 1], b[brank]) + b[brank + 2:]
    if brank // 3 != 2:
        yield b[:brank] + (b[brank + 3],)+ b[brank + 1:brank + 3] +  (b[brank],) + b[brank + 4:]

queue = set([start])
while len(queue):
    u = queue.pop()
    for b in next_board(u):
        if b not in d or d[b] > d[u] + 1:
            d[b] = d[u] + 1
            queue.update([b])
        
print(d[end])

Solution (Python):
from sys import stdin
readline = stdin.readline


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


def next_board(board, space, prev):
    for nxt in adjacent[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
from heapq import heappop, heappush

end = [1, 2, 3, 4, 5, 6, 7, 8, 0]


FORE = 1
BACK = 0


def search(start):
    if start == end:
        return 0
    table = {}

    table[tuple(start)] = (FORE, 0)
    table[tuple(end)] = (BACK, 0)

    heap = [(0, start, start.index(0), None, FORE), (0, end, end.index(0), None, BACK)]
    while heap:
        i, board, space, prev, direction = heappop(heap)
        i += 1
        for b, nxt in next_board(board, space, prev):
            key = tuple(b)
            if key in table:
                if table[key][0] != direction:
                    return table[key][1] + i
                continue
            table[key] = (direction, i)
            if b == end:
                return i
            heappush(heap, (i, b, nxt, space, direction))


def main():
    start = (map(int, readline().split()) for _ in range(3))
    start = [y for x in start for y in x]
    print(search(start))
main()

Solution (Python):


def get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 3] = C[index - 3], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 3] = C[index + 3], C[index]
    return C


boad = []
for i in range(3):
    boad.extend(map(int, input().split()))
exist_patten = set()

q = []
q.append((boad, None, 0))

while len(q) > 0:
    B, prev, count = q.pop(0)
    p = get_patten(B)
    if p in exist_patten:
        continue
    exist_patten.add(p)
    if p == '123456780':
        print(count)
        exit()

    index = B.index(0)

    if index % 3 != 0 and prev != 'right':
        C = change_left(index, B)
        q.append((C, 'left', count + 1))

    if index % 3 != 2 and prev != 'left':
        C = change_right(index, B)
        q.append((C, 'right', count + 1))

    if index >= 3 and prev != 'bottom':
        C = change_top(index, B)
        q.append((C, 'top', count + 1))

    if index <= 5 and prev != 'top':
        C = change_bottom(index, B)
        q.append((C, 'bottom', count + 1))

Solution (Python):
import heapq
from itertools import chain
from operator import mul

exp10 = [10 ** a for a in range(8, -1, -1)]
movables = [{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}]

destination = 123456780


def swap(board, move_from, move_to):
    return board + (exp10[move_to] - exp10[move_from]) * (board // exp10[move_from] % 10)


board0 = sum(map(mul, exp10, chain.from_iterable(map(int, input().split()) for _ in range(3))))
p0 = ('0' + str(board0))[-9:].index('0')

appeared = ({board0: 0}, {destination: 0})
queue = []
queue.extend((0, 0, move_from, p0, board0) for move_from in movables[p0])
queue.extend((0, 1, move_from, 8, destination) for move_from in movables[8])
heapq.heapify(queue)

while True:
    total_cost, direction, move_from, move_to, board = heapq.heappop(queue)
    if board in appeared[not direction]:
        print(total_cost + appeared[not direction][board])
        break
    new_board = swap(board, move_from, move_to)
    if new_board in appeared[direction]:
        continue
    appeared[direction][new_board] = total_cost + 1
    for move_from2 in movables[move_from]:
        if move_from2 != move_to:
            heapq.heappush(queue, (total_cost + 1, direction, move_from2, move_from, new_board))

Solution (Python):
import queue
adjacent=((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 bf_search(start, GOAL):
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    table = {}
    table[tuple(start)] = True
    while not q.empty():
        a = q.get()
        for x in adjacent[a.space]:
            b = a.board[:]
            b[a.space] = b[x]
            b[x] = 0
            key = tuple(b)
            if key in table: continue
            c = State(b,x,a)
            if b == GOAL:
                return print_answer(c)
            q.put(c)
            table[key] = True
 
cnt = -1
def print_answer(x):
    global cnt
    if x is not None:
        cnt += 1
        print_answer(x.prev)
    return str(cnt)
 
GOAL = [1,2,3,4,5,6,7,8,0]
start = []
for i in range(3):
 x,y,z = map(int, input().split())
 start += [x,y,z]

if start == GOAL:
    print("0")
else:
    print(bf_search(start, GOAL))

Solution (Python):
from sys import stdin
from heapq import heappop, heappush
FORE = 1
BACK = 0
adjacent = ((1,3), (0,2,4), (1,5), (0,4,6), (1,3,5,7), (2,4,8), (3,7), (4,6,8), (5,7))
start = [int(a) for _ in range(3) for a in stdin.readline().split()]
end = [1, 2, 3, 4, 5, 6, 7, 8, 0]
def next_board(board, space, prev):
    for nxt in adjacent[space]:
        if nxt == prev: continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
def search(start):
    if start == end: return 0
    table = {}
    table[tuple(start)] = (FORE, 0)
    table[tuple(end)] = (BACK, 0)
    heap = [(0, start, start.index(0), None, FORE), (0, end, end.index(0), None, BACK)]
    while heap:
        i, board, space, prev, direction = heappop(heap)
        i += 1
        for b, nxt in next_board(board, space, prev):
            key = tuple(b)
            if key in table:
                if table[key][0] != direction: return table[key][1] + i
                continue
            table[key] = (direction, i)
            if b == end: return i
            heappush(heap, (i, b, nxt, space, direction))
print(search(start))

Solution (Python):
from sys import stdin
import queue


adjacent =(
    (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 bf_search(start,end):
    q = queue.Queue()
    q.put(State(start,start.index(0),None)) 
    table = {} 
    table[tuple(start)] = True 

    while not q.empty(): 
        a = q.get() 
        for i in adjacent[a.space]: 
            b = a.board[:] 
            b[a.space] = b[i] 
            b[i] = 0          
            
            
            key = tuple(b) 
            if key in table:
                continue 

            
            
            c = State(b,i,a) 

            
            if b == end:
                return printAns(c)

            
            q.put(c)
            
            table[key] = True

count = -1
def printAns(c):
    global count
    if c is not None: 
        count += 1
        printAns(c.prev) 
    return count



end = [1,2,3,4,5,6,7,8,0]


start = [ int(n) for _ in range(3) for n in stdin.readline().split() ]

if start == end:
    print(0)
else:
    print(bf_search(start,end))

Solution (Python):
import sys

init = ''.join(sys.stdin.read().split())

generated_state = {init: 0}

def bfs(root):
    s = 0
    configure = [root]
    while '123456780' not in configure:
        q = iter(configure)
        configure = []
        s += 1
        for c in q:
            i = c.find('0')
            if 0 <= i <= 5:
                t = str.maketrans('0' + c[i+3], c[i+3] + '0')
                t_c = c.translate(t)
                if t_c not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            if i >= 3:
                t = str.maketrans('0' + c[i-3], c[i-3] + '0')
                t_c = c.translate(t)
                if t_c not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            if i == 0 or i == 1 or i == 3 or i == 4 or i == 6 or i == 7:
                t = str.maketrans('0' + c[i+1], c[i+1] + '0')
                t_c = c.translate(t)
                if t_c not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            if i == 1 or i == 2 or i == 4 or i == 5 or i == 7 or i == 8:
                t = str.maketrans('0' + c[i-1], c[i-1] + '0')
                t_c = c.translate(t)
                if t_c not in generated_state:
                    generated_state[t_c] = s
                    configure.append(t_c)
            if '123456780' in generated_state:
                break
    print(s)

bfs(init)

Solution (Python):
import sys

init = ''.join(sys.stdin.read().split())


def solve(start, goal):
    if start == goal:
        return 0
    generated_state = {start: 0, goal: 1}   
    step = {start: 0, goal: 0}
    s = 0
    c_d = [(start, 0), (goal, 1)] 
    while True:
        q = iter(c_d)
        c_d = []
        s += 1
        for c, d in q:
            i = c.find('0')
            if 0 <= i <= 5:
                t = str.maketrans('0' + c[i+3], c[i+3] + '0')
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))
            if i >= 3:
                t = str.maketrans('0' + c[i-3], c[i-3] + '0')
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))
            if i == 0 or i == 1 or i == 3 or i == 4 or i == 6 or i == 7:
                t = str.maketrans('0' + c[i+1], c[i+1] + '0')
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))
            if i == 1 or i == 2 or i == 4 or i == 5 or i == 7 or i == 8:
                t = str.maketrans('0' + c[i-1], c[i-1] + '0')
                t_c = c.translate(t)
                if t_c in generated_state:
                    if generated_state[t_c] != d:
                        return s + step[t_c]
                else:
                    generated_state[t_c] = d
                    step[t_c] = s
                    c_d.append((t_c, d))

print(solve(init, '123456780'))

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

import collections

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]


def solve(start):
    if start == GOAL:
        return 0
    
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s

import sys

start = list(map(int, sys.stdin.read().split()))

print(solve(start))

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

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]


def solve(start):
    if start == GOAL:
        return 0
    
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s

import sys

start = list(map(int, sys.stdin.read().split()))

print(solve(start))

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

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]


def solve(start):
    if start == GOAL:
        return 0
    
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s

import sys

start = list(map(int, sys.stdin.read().split()))

print(solve(start))

Solution (Python):
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
queue = [[ini_state, zero_x, zero_y, 0], [end_state, 2, 2, 1]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
if hashnum(ini_state) == answer:
    print(0)
else:
    visited[hashnum(ini_state)] = [0, 0]
    visited[answer] = [0, 1]
    trial = 0
    ended = 0
    while queue:
        new_queue = []
        trial += 1
        for q in queue:
            if ended:
                break
            state, zero_x, zero_y, direction = q
            for i in range(len(dx)):
                new_state = copy.deepcopy(state)
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < 3 and 0 <= new_y < 3:
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][1]:
                        print(trial + visited[perm][0])
                        ended = 1
                        break
                    elif perm not in visited:
                        visited[perm] = [trial, direction]
                        new_queue.append([new_state, new_x, new_y, direction])
        queue = new_queue

Solution (Python):
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x_goal = i%3
        y_goal = i//3
        x_now = (node_list[i] - 1)%3
        y_now = (node_list[i] - 1)//3
        if y_now == -1:
            y_now = 2
        dx = abs(x_now - x_goal)
        dy = abs(y_now - y_goal)
        s += dx + dy
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 3] = node_tmp[space - 3], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 3] = node_tmp[space + 3], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, g):
        self.node = node_list
        self.space = node_list.index(0)
        self.g = g
        self.h = d_manhattan(node_list)
        self.f = self.g + self.h

    def makeBoard(self):
        space = self.space
        cost_now = self.f
        x_s = space%3
        y_s = space//3
        if x_s < 2:
            node_tmp = moveNodeE(self.node, space)
            yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s < 2:
            node_tmp = moveNodeS(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
n_goal = [1,2,3,4,5,6,7,8,0]
n_start = []

for i in range(3):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard():
        if "".join(map(str, b_new.node)) in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Solution (Python):
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x_goal = i%3
        y_goal = i//3
        x_now = (node_list[i] - 1)%3
        y_now = (node_list[i] - 1)//3
        if y_now == -1:
            y_now = 2
        dx = abs(x_now - x_goal)
        dy = abs(y_now - y_goal)
        s += dx + dy
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 3] = node_tmp[space - 3], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 3] = node_tmp[space + 3], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, g):
        self.node = node_list
        self.space = node_list.index(0)
        self.g = g
        self.h = d_manhattan(node_list)
        self.f = self.g + self.h

    def makeBoard(self):
        space = self.space
        cost_now = self.f
        x_s = space%3
        y_s = space//3
        if x_s < 2:
            node_tmp = moveNodeE(self.node, space)
            yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s < 2:
            node_tmp = moveNodeS(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
n_goal = [1,2,3,4,5,6,7,8,0]
n_start = []

for i in range(3):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard():
        if "".join(map(str, b_new.node)) in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Solution (Python):
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def MAIN():
    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 = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    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)
MAIN()

Solution (Python):
from collections import deque
from copy import deepcopy, copy
N = 3
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 MAIN():
    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 = MAP.find("0")
    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)
MAIN()

Solution (Python):
from heapq import heapify, heappush, heappop
from collections import deque
from copy import deepcopy, copy
N = 3
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 MAIN():
    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 = MAP.find("0")
    goal = "123456780"
    dp = [(0, MAP, start)]
    LOG = {MAP}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                heappush(dp, (cnt, CM, nyx))
                LOG.add(CM)
MAIN()

Solution (Python):
from heapq import heapify, heappush, heappop
from collections import deque
from copy import deepcopy, copy
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}}
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 MAIN():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    goal = "123456780"
    if MAP == goal:
        print(0)
        return
    start = MAP.find("0")
    dp = [(0, MAP, start)]
    LOG = {MAP}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                if CM == goal:
                    print(cnt)
                    return
                heappush(dp, (cnt, CM, nyx))
                LOG.add(CM)
MAIN()

Solution (Python):
from collections import deque
N = 3
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:]
goal = "123456780"
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))
    if MAP == goal:
        return 0
    start = MAP.find("0")
    dp = deque([(0, MAP, start, 1), (0, goal, 8, 0)])
    TABLE = {MAP:(1, 0), goal:(0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if CM in TABLE:
                if TABLE[CM][0] != flg:
                    return TABLE[CM][1] + cnt
                continue
            TABLE[CM] = (flg, cnt)
            dp.append((cnt, CM, nyx, flg))
def MAIN():
    print(solve())
MAIN()