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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import queue

# ??£??\?????????
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
)

# ?±???¢?????????
class State:
    def __init__(self,board,space,prev):
        self.board = board # ?????¢?????¨?????????
        self.space = space # ?????´????????????(0?????????)
        self.prev = prev   # 1??????????±???¢(State??????????????§??????)

def bf_search(start,end):
    q = queue.Queue()
    q.put(State(start,start.index(0),None)) #item???Q?????\??????
    table = {} # ??????????????????
    table[tuple(start)] = True # ???????±???¢????????§???????????????????????????

    while not q.empty(): # empty()???Q???????????´??????True????????????????????§????????´??????False?????????
        a = q.get() # Q??????item????????????????????????????????????
        for i in adjacent[a.space]: # i????????????0?????????
            b = a.board[:] # ???????????¢???b????????????
            b[a.space] = b[i] # ?¬?????????¢?????????
            b[i] = 0          # ?¬?????????¢?????????
            
            
            key = tuple(b) # b???????????¨??????table????????¨??????????¢??????????
            if key in table:
                continue # ?????¨?????????for?????????????????£?????°???????????¢b?????????

            # table????????¨???????????´????????°???????±???¢c?????????
            # b?????°???????????¢?????¨????????????i????????????0????????????a???1??????????±???¢
            c = State(b,i,a) 

            # b???end????????´?????????printAns()??§???????????°?????¨???
            if b == end:
                return printAns(c)

            # ?????´???????????£??????Q???c????????????
            q.put(c)
            # key????????£???True?????????
            table[key] = True

count = -1
def printAns(c):
    global count
    if c is not None: 
        count += 1
        printAns(c.prev) # 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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

# Bidirectional search using breadth-first search
def solve(start, goal):
    if start == goal:
        return 0
    generated_state = {start: 0, goal: 1}   # 0: foreward, 1: backward
    step = {start: 0, goal: 0}
    s = 0
    c_d = [(start, 0), (goal, 1)] # configure and direction
    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'))

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
)

import collections

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
N = 3
goal = "123456780"
def g(i, j, a):
    if i > j:
        i, j = j, i
    return a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:]
def solve():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    start = "".join(input().replace(" ", "") for _ in range(N))
    if start == goal:
        return 0
    zero = start.find("0")
    dp = deque([(0, start, zero, 1), (0, goal, 8, 0)])
    TABLE = {start:(1, 0), goal:(0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Accepted

Solution code:
from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    start = 8 - MAP.find("0")
    MAP = int(MAP)
    if MAP == goal:
        return 0
    dp = deque([(0, start, MAP)])
    LOG = {MAP}
    while dp:
        cnt, yx, M = dp.popleft()
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                dp.append((cnt, nyx, CM))
                LOG.add(CM)
def MAIN():
    print(solve())
MAIN()

Submission status: Accepted

Solution code:
from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if start == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Accepted

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

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = Puzzle()
                v[:] = u[:]
                v.path = u.path
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import chain


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


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


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


def get_all_possible_next_boards(board, height, width, empty_pos=None):
    if empty_pos is None:
        empty_pos = get_empty_pos(board, height, width)
    next_boards = []
    x, y = empty_pos % width, empty_pos // height
    # 左との入れ替え
    if x > 0:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos - 1
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    # 右との入れ替え
    if x < width - 1:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos + 1
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    # 上との入れ替え
    if y > 0:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos - height
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    # 下との入れ替え
    if y < height - 1:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos + height
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))

    return next_boards


def resolve(board, height, width):
    # 既知の盤面を保存
    known_serialized_boards = set([serialize_board(board)])
    # 正解の盤面を保存
    completed_board = get_completed_board(width, height)
    known_serialized_completed_boards = set([serialize_board(completed_board)])
    if known_serialized_boards & known_serialized_completed_boards:
        return 0
    current_boards = [(board, None)]
    current_completed_boards = [(get_completed_board(width, height), None)]
    step_count = 1
    while step_count <= 45:
        # インプット側の盤面を一つ進める
        next_boards = []
        for board, empty_pos in current_boards:
            # 次のステップでの現れ得る局面を全て取得
            tmp_next_boards = get_all_possible_next_boards(board, height, width, empty_pos)
            filtered_next_board = []
            for board, empty_pos in tmp_next_boards:
                serialized_board = serialize_board(board)
                if serialized_board not in known_serialized_boards:
                    known_serialized_boards.add(serialized_board)
                    filtered_next_board.append((board, empty_pos))
            next_boards.extend(filtered_next_board)

        if known_serialized_boards & known_serialized_completed_boards:
            return step_count

        step_count = step_count + 1
        current_boards = next_boards

        # 正解盤面側を１つ進める
        next_completed_boards = []
        for board, empty_pos in current_completed_boards:
            # 次のステップでの現れ得る局面を全て取得
            tmp_next_boards = get_all_possible_next_boards(board, height, width, empty_pos)
            filtered_next_board = []
            for board, empty_pos in tmp_next_boards:
                serialized_board = serialize_board(board)
                if serialized_board not in known_serialized_completed_boards:
                    known_serialized_completed_boards.add(serialized_board)
                    filtered_next_board.append((board, empty_pos))
            next_completed_boards.extend(filtered_next_board)

        if known_serialized_boards & known_serialized_completed_boards:
            return step_count
        step_count = step_count + 1
        current_completed_boards = next_completed_boards

    return None


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    lines = filter(lambda line: line, lines)
    board = list(map(lambda line: line.split(" "), lines))
    height = len(board)
    width = len(board[0])
    board = list(chain.from_iterable(board))
    print(resolve(board, height, width))


if __name__ == '__main__':
    main()