Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

8 Puzzle

  The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space. 

  In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.

1 3 0
4 2 5
7 8 6

  You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).

1 2 3
4 5 6
7 8 0

  Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Input

  The $3 \times 3$ integers denoting the pieces or space are given.

Output

  Print the fewest steps in a line.

Constraints

There is a solution.

Sample Input 

1 3 0
4 2 5
7 8 6

Sample Output

4



Sample input:
1 3 0
4 2 5
7 8 6


Sample output:
4

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

    #初期盤面から1手ずつ表示
    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

#h1を用いたヒューリスティック探索
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')

#Puzzleオブジェクトの作成
initialPuzzle=Puzzle(initialBoard,space)

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

Submission status: Accepted

Solution code:
N = 3
#f = [input().split() for _ in range(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 = {f: True}
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
        # swap
        if n1 > n2:
            n1, n2 = n2, n1
        # swaped string
        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[new[0]] = True
            T.add(hashstr)
            new[2] += 1
            Q.append(new)

print(board[2])

Submission status: Accepted

Solution code:
import queue



"""
start : スタートの盤面を表す配列
# bf_search([8, 6, 7, 2, 5, 4, 3, 0, 1])
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 = (
        # 0のコマから1or3へ移動できる
        (1, 3),  # 0
        # 1のコマから0or2or4へ移動できる
        (0, 2, 4),  # 1
        (1, 5),  # 2
        (0, 4, 6),  # 3
        (1, 3, 5, 7),  # 4
        (2, 4, 8),  # 5
        (3, 7),  # 6
        (4, 6, 8),  # 7
        (5, 7)  # 8
    )
    # 最終的に至りたい形
    GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    # 初期値の時点でゴールだったら
    if start == GOAL:
        print(0)
        return
    

    q = queue.Queue()
    
    # キューにStateオブジェクトを追加する
    q.put(State(start, start.index(0), None))
    
    # table:同一局面があるかチェックするための辞書（ハッシュ）
    table = {}
    
    # 配列をタプル型に変換してそれをキーとする
    # Trueなら一度見たことがある状態
    table[tuple(start)] = True

    # ゴールにたどり着くまでループ
    # キューが空になってループが終了　-> goalにたどり着けなかった
    while not q.empty():
        # キューから局面を取り出してaに格納
        a = q.get()
        #print(a.board)
        # adjacent[a.space]: 動かせるコマの位置
        """
        完成形から考えて
        空白0のインデックスが7だったら隣接リストより4,6,8の方向へを動かすことができるので
        
        最初のループでxに4が入る
        """
        #print("a.apace="+str(a.space))
        for x in adjacent[a.space]:
            #print("x="+str(x))
            # 元の局面をコピー(State型でなく状態のみ「startと同じ」)
            b = a.board[:]

            b[a.space] = b[x]
            # 0: 空き場所を表す
            b[x] = 0
            key = tuple(b)
            # 同一局面がないかチェック　あればcontinueでループをスキップ
            if key in table: continue
            # 同一局面がなければ新しい局面を生成
            c = State(b, x, a)
            if b == GOAL:
                # print("answer")
                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
        # ひとつ前の局面（Stateオブジェクト）
        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)
            # print(x.board)



def main():
    p = []  ##appendのために宣言が必要
    # 入力受付
    i = 0
    while i < 3:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;
    # ↓この形に変形したい
    # start =[1,3,0,4,2,5,7,8,6]
    start = sum(p,[])

    bf_search(start)

    return








if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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

    # パネルの0を左右上下に移動させたときのパネル配置を返すジェネレーター
    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()

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush


adjacent = (
    (1, 3),        # 位置 0 に 0が存在したときに入れ替え可能な位置
    (0, 2, 4),     # 位置 1 に 0が存在したときに入れ替え可能な位置
    (1, 5),        # 位置 2 に 0が存在したときに入れ替え可能な位置
    (0, 4, 6),     # 位置 3 に 0が存在したときに入れ替え可能な位置
    (1, 3, 5, 7),  # 位置 4 に 0が存在したときに入れ替え可能な位置
    (2, 4, 8),     # 位置 5 に 0が存在したときに入れ替え可能な位置
    (3, 7),        # 位置 6 に 0が存在したときに入れ替え可能な位置
    (4, 6, 8),     # 位置 7 に 0が存在したときに入れ替え可能な位置
    (5, 7)         # 位置 8 に 0が存在したときに入れ替え可能な位置
)


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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = 3
#f = [input().split() for _ in range(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 = {f: True}
T = set(f)

while len(Q) > 0:
    board = Q.pop(0)
    if board[0] == ["1", "2", "3", "4", "5", "6", "7", "8", "0"]:
        break
    # int//int = int
    # location of zero
    x, y = board[1]//N, board[1]%N
    for dx, dy in dd:
        tx, ty = x+dx, y+dy
        # 0とswap後boardの範囲外に出たら除外
        if tx<0 or ty<0 or tx>=N or ty>=N:
            continue
        new = board[:]
        # n1 is location of zero on string
        # n2 is location of zero after moving on string
        n1, n2 = board[1], tx*N+ty
        new[1] = n2
        # swap
        if n1 > n2:
            n1, n2 = n2, n1
        # swaped string
        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:
        #if new[0] not in T.keys():
        #if not T.get(new[0], False):
            #T[new[0]] = True
            T.add(hashstr)
            new[2] += 1
            Q.append(new)

print(board[2])

Submission status: Accepted

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

Submission status: Accepted

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

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
# グリッドを最初から文字列として1次元で保持する
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)
    # 4方向見る
    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])

Submission status: Accepted

Solution code:
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)
    # Never reaches here.
    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
    # Never reaches here.
    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):
            # if 0 == input_nums[col]:
            #     zero_pos = (row, col)
            board[row][col] = input_nums[col]

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

Submission status: Accepted

Solution code:
import heapq


N = 3
FORE = 1
BACK = 0

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


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


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))

Submission status: Accepted

Solution code:
adjacent = (
    (1, 3),       # 0
    (0, 2, 4),    # 1
    (1, 5),       # 2
    (0, 4, 6),    # 3
    (1, 3, 5, 7), # 4
    (2, 4, 8),    # 5
    (3, 7),       # 6
    (4, 6, 8),    # 7
    (5, 7)        # 8
)
 
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]
 
# Bidirectional search using breadth-first search
def solve(start):
    if start == GOAL:
        return 0
    # 0: forward, 1: backward
    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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
			# print(current_state)
			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)

Submission status: Accepted

Solution code:
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]
# space index
si = 0

# move
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))

Submission status: Accepted

Solution code:
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()
    # init
    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]))

        # kkkkkusso jikan kakaru
        # for cmd in cmds:
        #     next_p = current_p.copy()
        #     next_p = get_next_states(cmd,next_p,current_z,prev_move)#eval(cmd)(next_p, current_z, prev_move)
        #     if(next_p is not None):
        #         print(current_d+1)
        #         q.put((next_p, current_d+1, cmd))

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

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

Submission status: Accepted

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


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


def create(a):
    #print(a)
    a = str(a)
    place = a.find('9')
    #print(place)
    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
#print(data)
#print(tmp1)
tmp1 = str(tmp1)
count = 0
kariokiba.append(int(tmp1))

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

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