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 heapq import heappop, heappush
from copy import deepcopy


class Board:
    def __init__(self, size, nums):
        self.size = size
        self.nums = nums
        self.code = self._code()

    def __eq__(self, other):
        return self.code == other.code

    def __lt__(self, other):
        return self.code < other.code

    def __gt__(self, other):
        return self.code > other.code

    def __hash__(self):
        nums = tuple(self.nums[i][j]
                     for i in range(self.size)
                     for j in range(self.size))
        return hash(nums)

    def same(self, other):
        if other is None:
            return False
        if self.__class__ != other.__class__:
            return False

        for i in range(self.size):
            for j in range(self.size):
                if self.nums[i][j] != other.nums[i][j]:
                    return False
        return True

    def solved(self):
        for i in range(self.size):
            for j in range(self.size):
                if (i, j) != self._validpos(self.nums[i][j]):
                    return False
        return True

    def _validpos(self, num):
        if num > 0:
            return ((num-1) // self.size, (num-1) % self.size)
        else:
            return (self.size-1, self.size-1)

    def _code(self):
        code = 0
        for i in range(self.size):
            for j in range(self.size):
                if self.nums[i][j] != 0:
                    vi, vj = self._validpos(self.nums[i][j])
                    code += abs(vi - i) + abs(vj - j)
        return code

    def find(self, num):
        for i in range(self.size):
            for j in range(self.size):
                if self.nums[i][j] == num:
                    return (i, j)
        raise IndexError()

    def move(self, p1, p2):
        i1, j1 = p1
        i2, j2 = p2
        nums = deepcopy(self.nums)
        nums[i1][j1], nums[i2][j2] = nums[i2][j2], nums[i1][j1]
        return self.__class__(self.size, nums)

    def moves(self):
        i, j = self.find(0)
        if i > 0:
            yield self.move((i, j), (i-1, j))
        if j > 0:
            yield self.move((i, j), (i, j-1))
        if i < self.size-1:
            yield self.move((i, j), (i+1, j))
        if j < self.size-1:
            yield self.move((i, j), (i, j+1))

    def __str__(self):
        s = ''
        for i in range(self.size):
            for j in range(self.size):
                s += ' {}'.format(self.nums[i][j])
            s += '\n'
        return s


class EightPuzzle:
    def __init__(self, board):
        self.board = Board(3, board)
        self.steps = 0

        if not self.board.solved():
            self._solve()

    def _solve(self):
        bs = []
        checked = {}
        heappush(bs, (self.board.code, self.board, 0))

        while len(bs) > 0:
            w, b, step = heappop(bs)
            if 0 < self.steps <= step:
                continue
            checked[b] = step
            for nb in b.moves():
                if nb.solved():
                    self.steps = step+1
                    return
                elif nb in checked and checked[nb] <= step:
                    continue
                else:
                    heappush(bs, (nb.code + step + 1, nb, step+1))


def run():
    board = []
    for i in range(3):
        board.append([int(i) for i in input().split()])

    eight_puzzle = EightPuzzle(board)
    print(eight_puzzle.steps)


if __name__ == '__main__':
    run()

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):
import sys
from collections import deque
input = sys.stdin.readline


def gen_hash(panel):
    _hash = ""
    for i in range(3):
        for j in range(3):
            _hash += str(panel[i][j])
    return _hash


def get_matchings(_hash):
    ans = "123456780"
    cnt = 0
    for i in range(9):
        if _hash[i] == str(ans[i]):
            cnt += 1
    return cnt


def bfs(panel):
    swap_candidates = {
        0: (1, 3),
        1: (0, 2, 4),
        2: (1, 5),
        3: (0, 4, 6),
        4: (1, 3, 5, 7),
        5: (2, 4, 8),
        6: (3, 7),
        7: (4, 6, 8),
        8: (5, 7)
    }
    dq = deque()
    dq.append((gen_hash(panel), 0))
    seen = set()
    seen.add(gen_hash(panel))
    while dq:
        _hash, cnt = dq.popleft()
        if get_matchings(_hash) == 9:
            return cnt
        z_ptr = _hash.index("0")
        for n_ptr in swap_candidates[z_ptr]:
            next_hash = list(_hash)
            next_hash[z_ptr], next_hash[n_ptr] = next_hash[n_ptr], next_hash[z_ptr]
            next_hash = "".join(next_hash)
            if next_hash not in seen:
                seen.add(next_hash)
                dq.append((next_hash, cnt + 1))


panel = []
for _ in range(3):
    panel.append([int(i) for i in input().split()])

ans = bfs(panel)
print(ans)

Solution (Python):
import sys
import copy
from collections import deque

def main():
    s = []
    for _ in range(3):
        s += list(map(int,input().split()))
    goal = [1,2,3,4,5,6,7,8,0]
    st = set()
    inf = 1000000007
    move = [[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 bfs():
        k = 0
        for i in range(9):
            if s[i] == 0: k = i 
        dq = deque()
        dq.append([s, k, 0]) 
        st.add(''.join(map(str, s)))
        while dq:
            state = dq.popleft()
            t, i, steps = state[0], state[1], state[2]
            if t == goal: return steps
            for j in move[i]:
                u = copy.copy(t)
                u[i], u[j] = u[j], u[i] 
                if ''.join(map(str, u)) in st:continue 
                dq.append([u, j, steps+1])
                st.add( ''.join(map(str, u)))

    print (bfs())

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

class Puzzle:
    def __init__(self, ls, answer_flag=False):
        self.piece_vec = list(ls)
        self.update_value = [-3, 3, -1, 1]
        for idx, piece in enumerate(ls):
            if piece == 0:
                self.space_idx = idx
        
        self.space_idx_before_slide = deque()
        self.manhattan_distance = list()
        if answer_flag:
            for i in range(9):
                self.manhattan_distance.append([(abs(i % 3 - j % 3) + abs(i // 3 - j // 3)) for j in range(9)])
                    
        
    def GetManhattanDistance(self, ans_idx, idx):
        return self.manhattan_distance[ans_idx][idx]
        
    def SumManhattanDistance(self, answer_board):
        sum_MD = 0
        for idx, piece in enumerate(self.piece_vec):
            if piece == 0:
                continue
            answer_idx = piece - 1
            sum_MD += answer_board.GetManhattanDistance(answer_idx, idx)
        return sum_MD
    
    def SlideSpace(self, command):
        is_frame = [self.space_idx < 3, self.space_idx >= 6, self.space_idx % 3 == 0, self.space_idx % 3 == 2]
        if is_frame[command]:
            return False
        
        next_space_idx = self.space_idx + self.update_value[command]
        if len(self.space_idx_before_slide) > 0 and next_space_idx == self.space_idx_before_slide[-1]:
            return False
        
        self.piece_vec[self.space_idx], self.piece_vec[next_space_idx] = self.piece_vec[next_space_idx], self.piece_vec[self.space_idx]
        self.space_idx_before_slide.append(self.space_idx)
        self.space_idx = next_space_idx
        return True
    
    def BackState(self):
        self.piece_vec[self.space_idx], self.piece_vec[self.space_idx_before_slide[-1]] = self.piece_vec[self.space_idx_before_slide[-1]], self.piece_vec[self.space_idx]
        self.space_idx = self.space_idx_before_slide.pop()

def SolvePuzzleByDFS(board, answer_board, limit, depth = 0):
    if board.SumManhattanDistance(answer_board) == 0:
        return True
    
    if depth + board.SumManhattanDistance(answer_board) > limit:
        return False
    
    for command in range(4):
        if board.SlideSpace(command) == False:
            continue
        
        if SolvePuzzleByDFS(board, answer_board, limit, depth+1):
            return True
        board.BackState()
    
    return False

def CalcMinStepOf15Puzzle(board, answer_board):
    for limit in range(board.SumManhattanDistance(answer_board), 35):
        if SolvePuzzleByDFS(board, answer_board, limit):
            return limit
    
    return -1

def main():
    inputLs = list()
    answerLs = [ 1, 2, 3,
                 4, 5, 6, 
                 7, 8, 9]
    for _ in range(3):
        inputLs += list(map(int, input().split()))

    start_board = Puzzle(inputLs)
    answer_board = Puzzle(answerLs, True)
    
    min_step = CalcMinStepOf15Puzzle(start_board, answer_board);
    
    print(min_step)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict,deque
import sys


M = [list(map(int,input().split())) for _ in range(3)]

start = 0
for i in range(3):
    for j in range(3):
        start += M[i][j]*10**((2-i)*3 + (2-j))
start = "{:0>9}".format(start)

def make_next_states(h,w,s):
    ret = []
    x = [-1,0,1,0]
    y = [0,-1,0,1]
    for i in range(4):
        nh,nw = h+y[i],w+x[i]
        if (0<=nh<=2) and (0<=nw<=2):
            swap_ind = nh*3 + nw
            char = s[swap_ind]
            next_s = s.replace(char,"x").replace("0",char).replace("x","0")
            ret.append(next_s)
    return ret

finished = defaultdict(bool)
finished[start] = True

q = deque()
q.append([start,0])
while 1:
    s,n = q.popleft()
    finished[s] = True
    if s == "123456780":
        break
    null = s.index("0")
    null_h = null//3
    null_w = null%3
    next_states = make_next_states(null_h,null_w,s)
    for next_s in next_states:
        if not finished[next_s]:
            q.append([next_s,n+1])

print(n)

Solution (Python):
from itertools import permutations
from heapq import heappop, heappush


def main():
    *A, = map(int, open(0).read().split())
    initial = get_hash(A)
    goal = get_hash([1, 2, 3, 4, 5, 6, 7, 8, 0])

    ans = search(initial, goal)
    print(ans)


def get_hash(A):
    board = 0
    for i, a in enumerate(A):
        board += a << i*4
    return board


def gen_move_table():
    mask = 0b1111
    dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]
    ret = [[] for _ in [0]*9]
    for y in range(3):
        for x in range(3):
            i = 3*y+x
            for dy, dx in dirs:
                dr = 3*dy+dx
                if 0 <= y+dy < 3 and 0 <= x+dx < 3:
                    sqmask = mask << (i+dr)*4
                    ret[i].append((dr, sqmask))
    return ret


def gen_next_board(board, move_table):
    mask = 0b1111
    ret = []
    for i in range(9):
        piece = board >> 4*i & mask
        if piece == 0:
            for move in move_table[i]:
                ret.append(do_move(board, move))
    return ret


def do_move(board, move):
    dr, sqmask = move

    sq = board & sqmask
    board ^= sq
    if dr > 0:
        board ^= sq >> dr*4
    else:
        board ^= sq << -dr*4

    return board


def heuristic(board):
    mask = 0b1111
    h = 0
    for i in range(9):
        y, x = divmod(i, 3)

        piece = board >> 4*i & mask
        if piece == 0:
            py, px = 2, 2
        else:
            py, px = divmod(piece-1, 3)
        h += abs(py-y)+abs(px-x)

    return h


def search(initial, goal):
    move_table = gen_move_table()

    dist = {}
    q = []

    dist[initial] = 0
    heappush(q, (heuristic(initial), 0, initial))
    while q:
        _, d, board = heappop(q)

        if board == goal:
            return d

        if board in dist and d > dist[board]:
            continue
        dist[board] = d

        for nboard in gen_next_board(board, move_table):
            nd = d + 1
            if (
                nboard not in dist or
                nboard in dist and nd < dist[nboard]
            ):
                heappush(q, (nd+heuristic(nboard), nd, nboard))


if __name__ == '__main__':
    main()

Solution (Python):
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = []
    SOLVED = (1, 2, 3, 4, 5, 6, 7, 8, 0)
    for _ in range(3):
        S += LI()

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

    dist = dict()
    que = collections.deque()
    S = tuple(S)
    que.append((S, S.index(0)))
    dist[S] = 0
    while que:
        c, idx_0 = que.popleft()
        if c == SOLVED:
            break
        for i in neighbor[idx_0]:
            c_l = list(c)
            c_l[idx_0], c_l[i] = c_l[i], c_l[idx_0]
            n = tuple(c_l)
            if not n in dist:
                que.append((n, i))
                dist[n] = dist[c] + 1

    print(dist[SOLVED])

if __name__ == '__main__':
    resolve()

Solution (Python):
import queue
import time

N=3
N2=9
diry=[0,1,0,-1]
dirx=[1,0,-1,0]
pos=[[2,2],[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1]]
move=[[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 Puzzle:
    board=""
    space=0

    def __init__(self,board,space):
        self.board=board
        self.space=space

    
    def showBoard(self):
        for i in range(N2):
            if self.board[i]!=0:
                print(self.board[i],end=' ')
            else:
                print('  ',end='')
            if i%3==2:
                print()
        print()

class State:
    pz=None
    g=0
    h=0
    f=0
    pr=None

    def __init__(self,pz,g,h=0,pr=None):
        self.pz=pz
        self.g=g
        self.h=h
        self.f=g+h
        self.pr=pr

    
    def showRoot(self):
        if self.pr!=None:
            self.pr.showRoot()
        self.pz.showBoard()

    def __lt__(self,other):
        if self.f==other.f:
            return self.g>other.g
        return self.f<other.f


def h2(p):
    count=0
    for i in range(N2):
        n=int(p.board[i])
        count+=abs(pos[n][0]-i//N)+abs(pos[n][1]-i%N)
    return count


def heuristic(pz,h):
    closedList=set()
    s=State(pz,0,h(pz),None)
    q=queue.PriorityQueue()
    q.put(s)
    while not q.empty():
        s=q.get()
        if s.pz.board in closedList:
            continue
        if s.pz.board=='123456780':
            return s.g
        space=s.pz.space
        for next in move[space]:
            nb=list(s.pz.board)
            nb[space],nb[next]=nb[next],nb[space]
            newb=''.join(nb)
            if not newb in closedList:
                np=Puzzle(newb,next)
                ns=State(np,s.g+1,h(np),s)
                q.put(ns)
        closedList.add(s.pz.board)
    return -1


s=''
for i in range(3):
    s+=input()
initialBoard=s.replace(' ','')


space=initialBoard.find('0')


initialPuzzle=Puzzle(initialBoard,space)

if initialBoard=='123456780':
    print(0)
else:
    print(heuristic(initialPuzzle,h2))

Solution (Python):
N = 3

f = input().split()
f += input().split()
f += input().split()
dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = [[f, f.index("0"), 0]]

T = set(f)

while len(Q) > 0:
    board = Q.pop(0)
    if board[0] == ["1", "2", "3", "4", "5", "6", "7", "8", "0"]:
        break
    x, y = int(board[1]/N), board[1]%N
    for dx, dy in dd:
        tx, ty = x+dx, y+dy
        if tx<0 or ty<0 or tx>=N or ty>=N:
            continue
        new = board[:]

        n1, n2 = board[1], tx*N+ty
        new[1] = n2
        
        if n1 > n2:
            n1, n2 = n2, n1
        
        new[0] = new[0][0:n1] + list(new[0][n2]) + new[0][n1+1:n2] + list(new[0][n1]) + new[0][n2+1:]
        hashstr = "".join(new[0])
        if hashstr not in T:
            
            T.add(hashstr)
            new[2] += 1
            Q.append(new)

print(board[2])

Solution (Python):
import queue



"""
start : スタートの盤面を表す配列

bf_search([1,2,3,4,5,0,7,8,6])
bf_search([1,3,0,4,2,5,7,8,6])
"""


def bf_search(start):
    
    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]
    
    if start == GOAL:
        print(0)
        return
    

    q = queue.Queue()
    
    
    q.put(State(start, start.index(0), None))
    
    
    table = {}
    
    
    
    table[tuple(start)] = True

    
    
    while not q.empty():
        
        a = q.get()
        
        
        """
        完成形から考えて
        空白0のインデックスが7だったら隣接リストより4,6,8の方向へを動かすことができるので
        
        最初のループでxに4が入る
        """
        
        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:
                
                min = Min()
                min.print_answer(c)
                min.result()
                return
            
            q.put(c)
            table[key] = True


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

class Min:
    def __init__(self):
        self.min = 0
    def increment(self):
        self.min = self.min + 1
    def result(self):
        print(self.min - 1)

    
    def print_answer(self,x):
        if x is not None:
            self.increment()
            self.print_answer(x.prev)
            



def main():
    p = []  
    
    i = 0
    while i < 3:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;
    
    
    start = sum(p,[])

    bf_search(start)

    return








if __name__ == '__main__':
    main()

Solution (Python):
class Queue:
    '''
    パズルオブジェクトを格納するキュークラス
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)

    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    def dequeue(self):
        return self.puzzle_list.pop(0)
    def is_empty(self):
        return len(self.puzzle_list) == 0


class _8Puzzle:
    def __init__(self, panel_list, state_list, size):
        self.panel_list = panel_list

        self.state_list = state_list
        self.state_list.append(panel_list)

        self.size = size

    
    def gene_next_panel(self, puzzle):
        zero_pos = puzzle.panel_list.index(0)
        col = zero_pos // self.size
        raw = zero_pos % self.size

        def __get_next_panel():
            panel_list = puzzle.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            return panel_list

        if self.size > col + 1:
            next_pos = (col + 1) * self.size + raw
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if col - 1 >= 0:
            next_pos = (col - 1) * self.size + raw
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if self.size > raw + 1:
            next_pos = col * self.size + raw + 1
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if raw - 1 >= 0:
            next_pos = col * self.size + raw - 1
            panel_list = __get_next_panel()
            yield tuple(panel_list)

    def result_print(self):
        i = 0
        for s in self.state_list:
            i += 1

        print(i-1)

def breadth_first(size, goal, panel_list):
    puzzle = _8Puzzle(panel_list, [], size)
    queue = Queue(puzzle)
    checked_dict = {}

    while queue.is_empty() is False:
        puzzle = queue.dequeue()
        num = 0
        for next_panel in puzzle.gene_next_panel(puzzle):
            next_puzzle = _8Puzzle(list(next_panel), puzzle.state_list[:], size)

            if next_panel in checked_dict:
                continue

            if list(next_panel) == goal:

                return next_puzzle

            checked_dict[next_panel] = True
            queue.enqueue(next_puzzle)

if __name__ == '__main__':
    size = 3
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    input_puzzle = []
    for i in range(3):
        _in1, _in2, _in3 = (int(z) for z in input().split())
        input_puzzle.append(_in1)
        input_puzzle.append(_in2)
        input_puzzle.append(_in3)

    if goal == input_puzzle:
        print(0)
        exit()

    puzzle = breadth_first(size, goal, input_puzzle)

    puzzle.result_print()

Solution (Python):
import sys
from heapq import heappop, heappush


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 move(board, space, prev_space):
    for next_space in adjacent[space]:
        if next_space == prev_space:
            continue
        next_board = board[:]
        next_board[space], next_board[next_space] = next_board[next_space], 0
        yield next_board, next_space


end = [1, 2, 3, 4, 5, 6, 7, 8, 0]
discovered_state = set()  


def search(start):
    discovered_state.add(tuple(start))
    heap = [(0, start, start.index(0), None)]  

    while heap:
        i, board, space, prev = heappop(heap)

        if board == end:
            return i

        i += 1
        for next_board, next_space in move(board, space, prev):
            if tuple(next_board) in discovered_state:
                continue
            discovered_state.add(tuple(next_board))
            heappush(heap, (i, next_board, next_space, space))


def main():
    start = []
    for _ in range(3):
        start.extend(list(map(int, sys.stdin.readline().strip().split())))
    ans = search(start)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import copy
from collections import deque

def main():
    s = []
    for _ in range(3):
        s+=list(map(int,input().split()))
    g = [1,2,3,4,5,6,7,8,0]
    st = set()
    inf = 1000000007
    move = [[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 bfs():
        k = 0
        for i in range(9):
            if s[i]==0:k = i
        dq = deque()
        dq.append([s,k,0])
        st.add(''.join(map(str,s)))
        while dq:
            state = dq.popleft()
            t,i,steps = state[0],state[1],state[2]
            if t==g:return steps
            for j in move[i]:
                u = copy.copy(t)
                u[i],u[j] = u[j],u[i]
                if ''.join(map(str,u)) in st:continue
                dq.append([u,j,steps+1])
                st.add( ''.join(map(str,u)))

    print (bfs())

if __name__ == '__main__':
    main()

Solution (Python):
N = 3

f = input().split()
f += input().split()
f += input().split()
dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = [[f, f.index("0"), 0]]

T = set(f)

while len(Q) > 0:
    board = Q.pop(0)
    if board[0] == ["1", "2", "3", "4", "5", "6", "7", "8", "0"]:
        break
    
    
    x, y = board[1]//N, board[1]%N
    for dx, dy in dd:
        tx, ty = x+dx, y+dy
        
        if tx<0 or ty<0 or tx>=N or ty>=N:
            continue
        new = board[:]
        
        
        n1, n2 = board[1], tx*N+ty
        new[1] = n2
        
        if n1 > n2:
            n1, n2 = n2, n1
        
        new[0] = new[0][0:n1] + list(new[0][n2]) + new[0][n1+1:n2] + list(new[0][n1]) + new[0][n2+1:]
        hashstr = "".join(new[0])
        if hashstr not in T:
        
        
            
            T.add(hashstr)
            new[2] += 1
            Q.append(new)

print(board[2])

Solution (Python):
from sys import stdin
from collections import deque
from copy import deepcopy


class State:
    def dup(self):
        ns = State()
        ns.b = self.b[:]
        ns.z = self.z
        ns.c = self.c
        return ns


def read_board():
    s = State()
    s.b = [int(x) for x in stdin.read().split()]
    s.z = s.b.index(0)
    s.c = 0
    return s


def move_zero(s, h):
    ns = s.dup()
    ns.z += h
    ns.b[s.z], ns.b[ns.z] = ns.b[ns.z], ns.b[s.z]
    ns.c += 1
    return ns


def push_hands(q, s):
    if s.z % 3 != 0:
        q.append(move_zero(s, -1))
    if s.z % 3 != 3 - 1:
        q.append(move_zero(s, 1))
    if s.z // 3 != 0:
        q.append(move_zero(s, -3))
    if s.z // 3 != 3 - 1:
        q.append(move_zero(s, 3))


def solve(s):
    hist = set()
    q = deque([])
    while True:
        t = tuple(s.b)
        if t == (1, 2, 3, 4, 5, 6, 7, 8, 0):
            return s.c
        if t not in hist:
            push_hands(q, s)
            hist.add(t)
        s = q.popleft()


def main():
    b = read_board()
    print(solve(b))


main()

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = 3

grid = '*' * (N+2)
for i in range(N):
    grid += '*' + input().replace(' ', '') + '*'
grid += '*' * (N+2)
start = grid.find('0')


goal = '******123**456**780******'
que = deque()
que.append((grid, 0, start))

memo = {}
while len(que):
    grid, cost, cur = que.popleft()
    if grid in memo:
        continue
    memo[grid] = cost
    grid = list(grid)
    
    for direction in (-1, 1, -(N+2), N+2):
        nxt = cur + direction
        if grid[nxt] != '*':
            grid[cur], grid[nxt] = grid[nxt], grid[cur]
            que.append((''.join(grid), cost+1, nxt))
            grid[cur], grid[nxt] = grid[nxt], grid[cur]

print(memo[goal])

Solution (Python):
import copy
from typing import List, Tuple


def _generate_goal() -> List[List[int]]:
    goal = [[0] * 3 for _ in range(3)]
    for row in range(3):
        for col in range(3):
            if 9 == 3 * row + col + 1:
                goal[row][col] = 0
            else:
                goal[row][col] = 3 * row + col + 1
    return goal


def _find_zero_pos(board: List[List[int]]) -> Tuple[int, int]:
    for row in range(3):
        for col in range(3):
            if 0 == board[row][col]:
                return (row, col)
    
    return (-1, -1)


def _swappable_cand(zero_pos: Tuple[int, int]) -> List[Tuple[int, int]]:
    row, col = zero_pos[0], zero_pos[1]
    cand_pos_list: List[Tuple[int, int]] = []
    if 0 != row:
        cand_pos_list.append((row - 1, col))
    if 2 != row:
        cand_pos_list.append((row + 1, col))
    if 0 != col:
        cand_pos_list.append((row, col - 1))
    if 2 != col:
        cand_pos_list.append((row, col + 1))

    return cand_pos_list


def solve_8puzzle(board: List[List[int]]) -> int:
    goal = _generate_goal()
    if board == goal:
        return 0
    generated_boards = {tuple(sum(board, [])): 0, tuple(sum(goal, [])): 1}
    steps = {tuple(sum(board, [])): 0, tuple(sum(goal, [])): 0}
    step = 0
    state = [(board, 0), (goal, 1)]
    while state:
        state_copied = copy.deepcopy(state)
        state = []
        step += 1
        for s2, d in state_copied:
            zero_row, zero_col = _find_zero_pos(s2)
            cand_pos_list = _swappable_cand((zero_row, zero_col))
            for (row, col) in cand_pos_list:
                s1 = copy.deepcopy(s2)
                s1[zero_row][zero_col], s1[row][col] = s1[row][col], 0
                key = tuple(sum(s1, []))
                if key in generated_boards:
                    if generated_boards[key] != d:
                        return step + steps[key]
                    continue
                state.append((s1, d))
                generated_boards[key] = d
                steps[key] = step
    
    return -1


if __name__ == "__main__":
    board = [[0] * 3 for _ in range(3)]

    for row in range(3):
        input_nums = list(map(lambda x: int(x), input().split()))
        for col in range(3):
            
            
            board[row][col] = input_nums[col]

    print(f"{solve_8puzzle(board)}")