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: Time Limit Exceeded

Solution code:
import copy

def movable_state(state):
    x, y = None, None
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                x, y = i, j
                break

    rsts = []
    for r, c in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if 0 <= r and r < 3 and 0 <= c and c < 3:
            rst = copy.deepcopy(state)
            rst[x][y], rst[r][c] = rst[r][c], rst[x][y]
            rsts.append(rst)
    return rsts

def hist_check(state, depth):
    for i in range(depth-1):
        for hist in state_history[i]:
            if hist == state:
                return True
    return False

puzzle = [list(map(int, input().split(' '))) for i in range(3)]
state_history = [[puzzle]]

goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
exchange_num = 0
depth = 0
still_not = True
while still_not:
    depth += 1
    state_history.append([])
    for hist in state_history[depth-1]:
        next_states = movable_state(hist)
        for next_stat in next_states:
            if hist_check(next_stat, depth): continue
            if next_stat == goal:
                still_not = False
                break
            state_history[depth].append(next_stat)
        if not still_not: break
print(depth)

Submission status: Time Limit Exceeded

Solution code:
import copy

def movable_state(state):
    x, y = None, None
    for i in range(3):
        for j in range(3):
            if state[3*i+j] == 0:
                x, y = i, j
                break

    rsts = []
    for r, c in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if 0 <= r and r < 3 and 0 <= c and c < 3:
            rst = copy.copy(state)
            rst[3*x+y], rst[3*r+c] = rst[3*r+c], rst[3*x+y]
            rsts.append(rst)
    return rsts

def hist_check(state, depth):
    for i in range(depth-2, -1, -1):
        for hist in state_history[i]:
            if hist == state:
                return True
    return False

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

goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
exchange_num = 0
depth = 0
still_not = True
while still_not:
    depth += 1
    state_history.append([])
    for hist in state_history[depth-1]:
        next_states = movable_state(hist)
        for next_stat in next_states:
            if hist_check(next_stat, depth): continue
            if next_stat == goal:
                still_not = False
                break
            state_history[depth].append(next_stat)
        if not still_not: break
print(depth)

Submission status: Time Limit Exceeded

Solution code:
# 幅優先探索 #双方向探索
import sys
import queue

SPACE = 0

adjacents_list = (
    (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
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = [start]
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if board in history:
                 continue
            if board == goal:
                return go_back(state)
            history.append(board)
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print(mininum_steps(initial_board, goal))

Submission status: Time Limit Exceeded

Solution code:
# 幅優先探索 #双方向探索
import sys
import queue

SPACE = 0

adjacents_list = (
    (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
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = [tuple(start)]
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if tuple(board) in history:
                 continue
            if board == goal:
                return go_back(state)
            history.append(tuple(board))
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

print(mininum_steps(initial_board, goal))

Submission status: Time Limit Exceeded

Solution code:

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))
        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 = []
        heappush(bs, (self.board, 0, None))

        while len(bs) > 0:
            b, step, pb = heappop(bs)
            for nb in b.moves():
                if nb.solved():
                    self.steps = step+1
                    return
                elif nb.same(pb):
                    continue
                else:
                    heappush(bs, (nb, step+1, b))


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

Submission status: Time Limit Exceeded

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

        while len(bs) > 0:
            b, step = heappop(bs)
            if 0 < self.steps <= step:
                continue
            checked[b] = step
            for nb in b.moves():
                if nb.solved():
                    if self.steps == 0 or step < self.steps:
                        self.steps = step+1
                elif nb in checked and checked[nb] <= step:
                    continue
                else:
                    heappush(bs, (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()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

row = 3
maxx = 9


class Puzzle():
    def __init__(self,f=None,space=None,path=''):
        self.f=f
        self.space=space
        self.path=path
        
    def __hash__(self):  
        ss=''
        for i in range(1,len(self.f),2):
            ss.join(str(self.f[i]))
        return hash(ss)
    
  
    def __eq__(self, other):  
        if self.f== other.f :  
            return True  
        return False      
    
    def __str__(self):
        return str(self.f)

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


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

def bfs(s): 
    global row
    global maxx
    global dx
    global dy
    global direct
    global Q
    
    V={}
    #Puzzle u, v;
    s.path = ""
    Q.append(s)
    V[s] = True

    while (len(Q)!=0): 
        u =Q.popleft()
        if (isTarget(u)):
            return u.path
        
        sx = u.space // row
        sy = u.space % row
        for r in range(4):
            tx = sx + dx[r]
            ty = sy + dy[r]

            if (tx < 0 or ty < 0 or tx >= row or ty >= row):
                continue;
            v = copy.deepcopy(u)
            v.f[u.space], v.f[tx * row + ty]=v.f[tx * row + ty],v.f[u.space]
            v.space = tx * row + ty
            
            #if v in V:
                #print(v)
                
            if  (not( v in V))  or V[v]!=True :
                   V[v] = True;
                   v.path += direct[r];
                   Q.append(v)

    return "unsolveable"

start=Puzzle()
start.f=[None for i in range(maxx)]
Q=deque()


for i in range(3) :
    start.f[i*3:i*3+3]=[int(x) for x in input().split()]
    
for i in range(maxx):
    if (start.f[i] == 0):
        start.f[i] = maxx
        start.space = i
    
ans = bfs(start)
if (ans!="unsolveable"):
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, OrderedDict
import copy

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 print_puzzle(pzl):
    for i, p in enumerate(pzl.f):
        print(p, '', end='')
        if i%3 == 2:
            print('')

def bfs(pzl):
    queue = deque([])
    V = OrderedDict()
    pzl.path = ''
    queue.append(pzl)
    V[pzl] = True

    while len(queue) != 0:
        u = queue.popleft()
        if is_target(u): return u.path
        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 = copy.deepcopy(u)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if not V.get(v, None):
                V[v] = True
                v.path += dir[r]
                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))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, OrderedDict
import copy

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 print_puzzle(pzl):
    for i, p in enumerate(pzl.f):
        print(p, '', end='')
        if i%3 == 2:
            print('')

def bfs(pzl):
    queue = deque([])
    V = OrderedDict()
    pzl.path = ''
    queue.append(pzl)
    V[pzl] = True

    while len(queue) != 0:
        u = queue.popleft()
        if is_target(u): return u.path
        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 = copy.deepcopy(u)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if v not in V.keys():
                V[v] = True
                v.path += dir[r]
                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))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, OrderedDict
import copy

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 print_puzzle(pzl):
    for i, p in enumerate(pzl.f):
        print(p, '', end='')
        if i%3 == 2:
            print('')

def bfs(pzl):
    queue = deque([])
    V = OrderedDict()
    pzl.path = ''
    queue.append(pzl)
    V[pzl] = True
    if is_target(pzl): return u.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 = copy.deepcopy(u)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if v not in V.keys():
                V[v] = 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))

Submission status: Time Limit Exceeded

Solution code:
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 print_puzzle(pzl):
    for i, p in enumerate(pzl.f):
        print(p, '', end='')
        if i%3 == 2:
            print('')

def bfs(pzl):
    queue = deque([])
    V = OrderedDict()
    pzl.path = ''
    queue.append(pzl)
    V[pzl] = True
    if is_target(pzl): return u.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 v not in V:
                V[v] = 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))

Submission status: Accepted

Solution code:
from collections import deque

N = 3
N2 = 9

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

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

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


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


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

    while len(q) != 0:
        u = q.popleft()
        if isTarget(u):
            return u.path
        sx = u.space // N
        sy = u.space % N
        for r in range(4):
            tx = sx + dx[r]
            ty = sy + dy[r]
            if tx < 0 or ty < 0 or tx >= N or ty >= N:
                continue
            v = Puzzle(u.f[:], u.space, u.path)
            v.f[u.space], v.f[tx * N + ty] = v.f[tx * N + ty], v.f[u.space]
            v.space = tx * N + ty
            key = tuple(v.f)
            if key not in dic:
                dic[key] = True
                v.path += dirc[r]
                q.append(v)

    return 'unsolvable'


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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
import queue

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

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

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

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

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

print(u[2])

Submission status: Accepted

Solution code:
import sys
import queue

N = 3

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

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

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

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

print(u[2])

Submission status: Accepted

Solution code:
import sys, itertools
f = sys.stdin

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

d = {start:0}

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

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

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline


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 next_board(board, space, prev):
    for nxt in adjacent[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
from heapq import heappop, heappush

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

# ???????????¨????????°
FORE = 1
BACK = 0


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

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

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


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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

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

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

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

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

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

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

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

    index = B.index(0)

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

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

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

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