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):
import heapq


N = 3
FORE = 1
BACK = 0

board_goal = [i for i in range(1, N ** 2)] + [0]


BOARD_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 slove(board_start):
    if board_start == board_goal:
        return 0

    dict_board_state = {}
    dict_board_state[tuple(board_start)] = (FORE, 0)

    heap_board = [(0, board_start, board_start.index(0), None, FORE)]

    while heap_board:
        cnt_move, board, space_now, space_prev, direction = heapq.heappop(heap_board)
        cnt_move += 1

        for board_next, space_next in next_board(board, space_now, space_prev):
            key = tuple(board_next)
            if key in dict_board_state:
                continue

            dict_board_state[key] = (direction, cnt_move)
            if board_next == board_goal:
                return cnt_move

            heapq.heappush(heap_board, (cnt_move, board_next, space_next, space_now, direction))

            
def next_board(board, space_now, space_prev):
    for space_next in BOARD_ADJACENT[space_now]:
        if space_next == space_prev:
            continue

        board_next = board[:]
        board_next[space_now], board_next[space_next] = board_next[space_next], 0
        yield board_next, space_next



board_input = []

for _ in range(N):
    board_input.extend(list(map(int, input().split())))


print(slove(board_input))

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):
N = 3
dx = [0,-1,0,1]
dy = [1,0,-1,0]
limit = 0
t = [[0 for i in range(N)] for j in range(N)]

def getH():
    sum = 0
    x = int(0)
    for i in range(N):
        for j in range(N):
            if t[i][j]==0:continue
            x=t[i][j]-1
            sum += abs(int(x/N)-i)+abs((int(x%N)-j))
    return sum

def dfs( depth, prev,py,px):
    h=getH()
    if h == 0 :return True 
    if depth+h > limit: return False
    for i in range(4):
        if abs(i-prev) == 2 : continue
        tx=px+dx[i]
        ty=py+dy[i]
        if tx<0 or ty<0 or tx>=N or ty>=N:continue
        t[ty][tx],t[py][px] = t[py][px],t[ty][tx]
        if dfs(depth+1,i,ty,tx) :return True
        t[ty][tx],t[py][px] = t[py][px],t[ty][tx]
    return False

def Solve(py, px):
    global limit
    limit =0
    while True:
        if dfs(0,99,py,px):
            print(limit)
            return 
        limit += 1
 
if __name__=='__main__':
    for i in range(N):
        tmp =list(map(int, input().split()))
        for j in range(N):
            t[i][j]=tmp[j]
            if t[i][j]==0:
                py=i
                px=j
    Solve(py,px)

Solution (Python):
from collections import deque, defaultdict

grid_size = 3

def generate_next_state(q, visited, current_state, zero_pos, dx, dy):
	r = zero_pos // grid_size
	c = zero_pos % grid_size
	next_state = current_state[:]
	next_r = r + dx
	next_c = c + dy
	if next_r < 0 or next_r >= grid_size:
		return None
	if next_c < 0 or next_c >= grid_size:
		return None
	next_state[next_r * grid_size + next_c], next_state[r * grid_size + c] = next_state[r * grid_size + c], next_state[next_r * grid_size + next_c]
	if visited.get(tuple(next_state)) is not None:
		return None
	q.append(next_state)

def bfs(initial_state, goal):
	visited = defaultdict()
	q = deque()
	q.append(initial_state)
	step = 0
	while(len(q) > 0):
		node_count = len(q)
		while(node_count > 0):
			current_state = q.popleft()
			visited[tuple(current_state)] = True
			
			node_count -= 1
			if current_state == goal:
				print(step)
				return 0
			zero_pos = current_state.index(0)
			generate_next_state(q, visited, current_state, zero_pos, 0, -1)
			generate_next_state(q, visited, current_state, zero_pos, 0, 1)
			generate_next_state(q, visited, current_state, zero_pos, -1, 0)
			generate_next_state(q, visited, current_state, zero_pos, 1, 0)


		step += 1

def init():
	initial_state = []
	goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
	for i in range(grid_size):
		input_list = input().rstrip().split()
		initial_state.extend([int(val) for val in input_list])
	return initial_state, goal

initial_state, goal = init()
bfs(initial_state, goal)

Solution (Python):
import sys
from collections import deque


class P(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""

    def __hash__(self):
        return hash(str(self[:]))


def is_target(p):
    return p[:] == ans[:]


N = 3
N2 = N*N
ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]

si = 0


dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
direction = ('u', 'l', 'd', 'r')


def bfs(p):
    Q = deque()
    Q.append(p)
    V = set()
    V.add(p)

    while Q:
        u = Q.popleft()
        if u == ans:
            return u.path
        sx = u.space // N
        sy = u.space % N
        for i in range(4):
            tx = sx + dx[i]
            ty = sy + dy[i]
            if tx < 0 or ty < 0 or tx >= N or ty >= N:
                continue
            v = P()
            v[:] = u[:]
            v.path = u.path
            c = int(tx*N+ty)
            v[u.space] = v[c]
            v[c] = 9
            v.space = c
            if v not in V:
                V.add(v)
                v.path += direction[i]
                Q.append(v)


p = P()
for i in range(N):
    line = sys.stdin.readline()
    a, b, c = map(int, line.split())
    p.append(a)
    p.append(b)
    p.append(c)
for i in range(N2):
    if p[i] == 0:
        p[i] = 9
        p.space = i

re = bfs(p)
print(len(re))

Solution (Python):
from queue import Queue
goal = [1,2,3,4,5,6,7,8,0]
SIZE = 3
cmds = ['up','down','left','right']

def puz_hash(p):
    hash = ''.join(map(str, p))
    return hash

def up(p,z,c):
    if z >= 3 and c != 'down':
        p[z], p[z - 3] = p[z - 3], p[z]
    return p

def down(p,z,c):
    if z <= 5 and c != 'up':
        p[z], p[z + 3] = p[z + 3], p[z]
    return p

def left(p,z,c):
    if z % 3 != 0 and c != 'right':
        p[z], p[z - 1] = p[z - 1], p[z]
    return p

def right(p,z,c):
    if z % 3 != 2 and c != 'left':
        p[z], p[z + 1] = p[z + 1], p[z]
    return p

def search(p):
    q = Queue()
    
    q.put((p,0,''))
    visited = set()

    while True:
        if(q.empty()):
            return None
        current_p, current_d, prev_move = q.get()
        current_z = current_p.index(0)
        current_p_hash = puz_hash(current_p)

        if(current_p_hash in visited):
            continue
        if(current_p_hash == goal_hash):
            return current_d
        visited.add(current_p_hash)

        next_p = current_p.copy()
        next_p = up(next_p, current_z, prev_move)
        if(next_p.index(0) != current_z):
            q.put((next_p, current_d+1, cmds[0]))

        next_p = current_p.copy()
        next_p = down(next_p, current_z, prev_move)
        if(next_p.index(0) != current_z):
            q.put((next_p, current_d+1, cmds[1]))

        next_p = current_p.copy()
        next_p = left(next_p, current_z, prev_move)
        if(next_p.index(0) != current_z):
            q.put((next_p, current_d+1, cmds[2]))

        next_p = current_p.copy()
        next_p = right(next_p, current_z, prev_move)
        if(next_p.index(0) != current_z):
            q.put((next_p, current_d+1, cmds[3]))

        
        
        
        
        
        
        

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

goal_hash = puz_hash(goal)
res = search(p)
print(res)

Solution (Python):
import copy
def decision(a):
    
    
    
    if a == 123456789:
        print(count)
        exit()
    if a in data:
        pass
    else:
        data[a] = 1
        kariokiba.append(a)
        
        


def str_create(i, j, h):
    h = h[:i] + h[j] + h[i+1:j] + h[i] + h[j+1:]
    
    decision(int(h))


def create(a):
    
    a = str(a)
    place = a.find('9')
    
    b = c = d = e = a
    if place == 0:
        str_create(0, 1, b)
        str_create(0, 3, c)
    elif place == 1:
        str_create(0, 1, b)
        str_create(1, 2, c)
        str_create(1, 4, d)
    elif place == 2:
        str_create(1, 2, b)
        str_create(2, 5, c)
    elif place == 3:
        str_create(0, 3, b)
        str_create(3, 4, c)
        str_create(3, 6, d)
    elif place == 4:
        str_create(1, 4, b)
        str_create(3, 4, c)
        str_create(4, 5, d)
        str_create(4, 7, e)
    elif place == 5:
        str_create(2, 5, b)
        str_create(4, 5, c)
        str_create(5, 8, d)
    elif place == 6:
        str_create(3, 6, b)
        str_create(6, 7, c)
    elif place == 7:
        str_create(6, 7, b)
        str_create(4, 7, c)
        str_create(7, 8, d)
    elif place == 8:
        str_create(5, 8, b)
        str_create(7, 8, c)



tmp0 = [list(map(int, input().split())) for _ in range(3)]
data = {}
tmp1 = 0
kariokiba = []
kariokiba1 = []
for i in tmp0:
    for j in i:
        if j == 0:
            j = 9
        tmp1 *= 10
        tmp1 += j
data[tmp1] = 1


tmp1 = str(tmp1)
count = 0
kariokiba.append(int(tmp1))

if tmp1 == '123456789':
    print(0)
    exit()
'''
create(tmp1)
print(kariokiba)


'''
while True:
    
    kariokiba1 = copy.deepcopy(kariokiba)
    kariokiba.clear()
    count += 1
    
    
    for i in kariokiba1:
        create(i)

Solution (Python):
from collections import deque

N = 3
M = 3
board = []
expected = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

queue = deque()
bqueue = deque()

history = set()




def swap(x1, y1, x2, y2, b):
    
    t = [x[:] for x in b]
    t[x1][y1], t[x2][y2] = t[x2][y2], t[x1][y1]
    return t


def p2i(b):
    tmp = 0
    for i in range(N):
        for j in range(M):
            tmp += b[i][j] * 10**(3*i+j)
    return tmp


def bfs():
    if expected == board:
        print(0)
        exit(0)

    while len(queue):
        pazzle = queue.popleft()
        cost = bqueue.popleft()
        
        xz = None
        yz = None
        for i in range(N):
            for j in range(M):
                if pazzle[i][j] == 0:
                    xz, yz = i, j
        
        xm = [1, 0, 0, -1]
        ym = [0, -1, 1, 0]
        for k in range(4):
            if 0 <= xz + xm[k] < N and 0 <= yz + ym[k] < N:
                
                t = swap(xz, yz, xz + xm[k], yz + ym[k], pazzle)
                ipz = p2i(t)
                if 87654321 == ipz:
                    print(cost+1)
                    exit(0)
                
                if ipz not in history:
                    queue.append(t)
                    history.add(ipz)
                    bqueue.append(cost+1)


for i in range(N):
    board.append(list(map(int, input().split())))
queue.append(board)
bqueue.append(0)
bfs()

Solution (Python):
from collections import deque
CORRECT_STATE = "123456780"


class PuzzleState:
    __slots__ = ['state', 'spc_x', 'spc_y', 'depth']

    def __init__(self, state: str, depth=0):
        self.state = state
        index = state.find('0')
        self.spc_x = index % 3
        self.spc_y = index // 3
        self.depth = depth

    def swap_state(self, ch_x, ch_y):
        conv_char = self.state[ch_y * 3 + ch_x]
        self.state = self.state.replace('0', 'X')
        self.state = self.state.replace(conv_char, '0')
        self.state = self.state.replace('X', conv_char)
        self.spc_x, self.spc_y = ch_x, ch_y

    def is_correct(self):
        return self.state == CORRECT_STATE

    def __repr__(self):
        return f'{self.state}'


move = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def puzzle8_breadth_first_search(puzzle: PuzzleState):
    mem_state = {puzzle.state: ''}
    p_queue = deque()
    p_queue.append(puzzle)

    while len(p_queue) != 0:
        u = p_queue.popleft()
        if u.is_correct():
            
            return u.depth
        for mx, my in move:
            sp_new_x = u.spc_x + mx
            sp_new_y = u.spc_y + my
            if not(0 <= sp_new_x <= 2 and 0 <= sp_new_y <= 2):
                continue
            new_puzzle = PuzzleState(u.state, depth=u.depth+1)
            new_puzzle.swap_state(sp_new_x, sp_new_y)

            if new_puzzle.state not in mem_state:
                mem_state[new_puzzle.state] = ''
                p_queue.append(new_puzzle)
    return False


def main():
    input_text = ""
    for i in range(3):
        input_text += "".join(input().split())

    
    ans_puzzle = puzzle8_breadth_first_search(PuzzleState(input_text))
    print(ans_puzzle)
    return

main()

Solution (Python):
from heapq import heappush, heappop
N = 3
M = []
for i in range(N):
    M.append(list(map(int, input().split())))

A = (1, 2, 3, 4, 5, 6, 7, 8, 0)
def h(M):
    c = 0
    it = iter(A).__next__
    for i in range(N):
        for v in M[i]:
            if v != it():
                c += 1
    return c
def f(M):
    M0 = []
    for m in M:
        M0.extend(m)
    return tuple(M0)


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
ci = cj = -1
for i in range(N):
    for j in range(N):
        if M[i][j] == 0:
            ci = i; cj = j
que = [(h(M), 0, ci, cj, M)]
U = set(f(M))
while que:
    hc, c, cr, cc, M = heappop(que)
    if hc == c:
        print(c)
        break
    for dr, dc in dd:
        nr = cr+dr; nc = cc+dc
        if not 0 <= nr < N or not 0 <= nc < N:
            continue
        MM = [m[:] for m in M]
        MM[cr][cc] = MM[nr][nc]
        MM[nr][nc] = 0
        s = f(MM)
        if s in U:
            continue

        U.add(s)
        heappush(que, (h(MM)+c+1, c+1, nr, nc, MM))

Solution (Python):
from collections import deque, OrderedDict

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

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

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

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

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

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

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

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

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

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

Solution (Python):
from collections import deque
board = [int(s) for _ in range(3) for s in input().split()]
end = [1, 2, 3, 4, 5, 6, 7, 8, 0]
table = set()
def print_board(board):
    for i in range(0, 9, 3):
        print(*board[i:i + 3])

def swap(q, step_q, step, board):
    key = tuple(board)
    if key in table:
        return
    else:
        table.add(key)

    empty = board.index(0)
    def _swap(q, step_q, step, board, k, s):
        b = board.copy()
        b[k], b[s] = b[s], b[k]
        q.append(b)
        step_q.append(step + 1)

    if empty % 3 != 2:
        _swap(q, step_q, step, board, empty, empty + 1)
    if empty % 3 != 0:
        _swap(q, step_q, step, board, empty, empty - 1)
    if empty // 3 < 2:
        _swap(q, step_q, step, board, empty, empty + 3)
    if empty // 3 > 0:
        _swap(q, step_q, step, board, empty, empty - 3)


q = deque([board])
step_q = deque([0])

while q[0] != end:
    b = q.popleft()
    step = step_q.popleft()
    swap(q, step_q, step, b)

print(step_q.popleft())

Solution (Python):
start =  list(map(int, [n for a in [input().split() for i in range(3)] for n in a]))
goal = [1, 2, 3, 4, 5 ,6, 7, 8, 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)
)

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

def main():
    if start == goal:
        return 0

    queue = [State(start[:], start.index(0), 0)]
    stateList = {"".join(map(str, start)) : True}

    while len(queue) != 0:
        state = queue.pop(0)
        for i in adjacent[state.space]:
            next_state = State(state.board[:], i, state.path + 1)
            next_state.board[i], next_state.board[state.space] = next_state.board[state.space], next_state.board[i]
            state_str = "".join(map(str, next_state.board))
            if stateList.get(state_str) :
                continue
            stateList[state_str] = True
            if next_state.board == goal:
                return next_state.path
            queue.append(next_state)

if __name__ == '__main__':
    result = main()
    print(result)

Solution (Python):
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
t = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]


def get_heuri():
    res = 0
    for i in range(3):
        for j in range(3):
            if t[i][j] == 0:
                continue
            a = t[i][j] - 1
            res += abs(a // 3 - i) + abs(a % 3 - j)
    return res


def check(depth, prev, py, px, limit):
    heuri = get_heuri()
    if heuri + depth > limit:
        return False
    if heuri == 0:
        return True
    for i in range(4):
        if abs(i - prev) == 2:
            continue
        ny = py + dy[i]
        nx = px + dx[i]
        if ny < 0 or nx < 0 or ny >= 3 or nx >= 3:
            continue
        t[ny][nx], t[py][px] = t[py][px], t[ny][nx]
        if check(depth + 1, i, ny, nx, limit):
            return True
        t[ny][nx], t[py][px] = t[py][px], t[ny][nx]
    return False

for i in range(3):
    s = list(map(int, input().split()))
    for j in range(3):
        if s[j] == 0:
            py = i
            px = j
        t[i][j] = s[j]
limit = 0
while True:
    if check(0, 99, py, px, limit):
        print(limit)
        break
    limit += 1