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;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Submission status: Accepted

Solution code:
from collections import deque

MOVE = {'U': (0, -1), 'D': (0, 1), 'L': (-1, 0), 'R': (1, 0)}

def next(numbers):
    for d in 'UDLR':
        z = numbers.index(0)
        tx, ty = z % 3 + MOVE[d][0], z // 3 + MOVE[d][1]
        if 0 <= tx < 3 and 0 <= ty < 3:
            t = ty * 3 + tx
            result = list(numbers)
            result[z], result[t] = numbers[t], 0
            yield d, tuple(result)

def bfs(puzzle):
    queue = deque([(puzzle, '')])
    seen = set()
    while queue:
        numbers, route = queue.popleft()
        seen.add(numbers)
        if numbers == (1, 2, 3, 4, 5, 6, 7, 8, 0):
            return route
        for direction, new_numbers in next(numbers):
            if new_numbers not in seen:
                queue.append((new_numbers, route + direction))
    return route

puzzle = ()
for i in range(3):
    a,b,c = map(int, input().split())
    puzzle += (a,b,c)

print(len(bfs(puzzle)))

Submission status: Accepted

Solution code:
# 8 Puzzle
import copy
z = 0
[N, d] = [3, 0]
check_flag = [[1, 2, 3, 4,  1, 2, 3, 4,  1, 2, 3, 4],
              [2, 3, 4, 1,  2, 3, 4, 1,  2, 3, 4, 1],
              [3, 4, 1, 2,  3, 4, 1, 2,  3, 4, 1, 2],
              [4, 1, 2, 3,  4, 1, 2, 3,  4, 1, 2, 3],
              [3, 2, 1, 4,  3, 2, 1, 4,  3, 2, 1, 4],
              [2, 1, 4, 3,  2, 1, 4, 3,  2, 1, 4, 3],
              [1, 4, 3, 2,  1, 4, 3, 2,  1, 4, 3, 2],
              [4, 3, 2, 1,  4, 3, 2, 1,  4, 3, 2, 1]]

start = []
goal = [[i + j*N for i in range(1, N + 1)] for j in range(N)]
goal[2][2] = 0
for i in range(N):
    start.append(list(map(int, input().split())))


def manhattan(value, pairs):
    h = 0

    if value == 1:
        h = (pairs[0] + pairs[1])
    if value == 2:
        h = (pairs[0] + abs(pairs[1] - 1))
    if value == 3:
        h = (pairs[0] + abs(pairs[1] - 2))
    
    if value == 4:
        h = (abs(pairs[0] - 1) + pairs[1])
    if value == 5:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 1)) 
    if value == 6:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 2))
        
    if value == 7:
        h = (abs(pairs[0] - 2) + pairs[1])      
    if value == 8:
        h = (abs(pairs[0] - 2) + abs(pairs[1] - 1))
        
    return h

def flag_array(flag, input):

    flag.pop(0)
    flag.append(input)
    return flag


s_h = 0
for i in range(N):
    for j in range(N):
        s_h += manhattan(start[i][j], [i, j])

# print(s_h)

for i in range(N):
        check = start[i].count(0)
        if check != 0:
            [s_r, s_c] = [i, start[i].index(0)]
            break
        if i == 3:
            print("Error")

while True:
    d += 1
    queue = []
    flag = [0 for i in range(12)]
    queue.append([s_h, start, 0, [s_r, s_c], flag])

    #while True:
    while len(queue) != 0:
        #print("Q: ", len(queue), "depth: ", d)
        short_n = queue.pop(0)
        h = short_n[0] - short_n[2]
        state = short_n[1]
        g = short_n[2]
        [r, c] = short_n[3]
        flag = short_n[4]
        #print("left_Q: ", len(queue), "depth: ", d, "h: ", h, "g: ", g, "state: ", state, "g+h: ", short_n[0], "flag: ", flag[len(flag) - 1])
        #print("left_Q: ", len(queue), "depth: ", d, "h: ", h, "g: ", g, "flag: ", flag, "g+h: ", short_n[0])
        #if d == 1:
            #print(short_n[0])
            #print(state)
            #print(g)

        if h == 0:
            print(short_n[2])
            #print(z)
            break
        """
        if flag in check_flag:
            z += 1
            continue
        """
        if r - 1 >= 0 and flag[len(flag) - 1] != 3:
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            h = short_n[0] - short_n[2] - manhattan(temp[r - 1][c], [r - 1, c]) + manhattan(temp[r - 1][c], [r, c])
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            #if temp[r][c] != goal[r][c]:
            #[r, c] = [r - 1, c]
            #if temp
            #h = manhattan(temp)
            #print("1: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r - 1, c], flag_array(temp_array, 1)])
        
        if c + 1 < N and flag[len(flag) - 1] != 4:
            #print("2: ")
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            #temp_array = copy.deepcopy(flag)
            h = short_n[0] - short_n[2] - manhattan(temp[r][c + 1], [r, c + 1]) + manhattan(temp[r][c + 1], [r, c])
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            #print("2: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c + 1], flag_array(temp_array, 2)])

        if r + 1 < N and flag[len(flag) - 1] != 1:
            #print("3: ")
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            #temp_array = copy.deepcopy(flag)
            h = short_n[0] - short_n[2] - manhattan(temp[r + 1][c], [r + 1, c]) + manhattan(temp[r + 1][c], [r, c])
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            #print("3: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r + 1, c], flag_array(temp_array, 3)])
        
        if c - 1 >= 0 and flag[len(flag) - 1] != 2:
            #print("4: ")
            [temp, temp_array] = [copy.deepcopy(state), flag[:]]
            h = short_n[0] - short_n[2] - manhattan(temp[r][c - 1], [r, c - 1]) + manhattan(temp[r][c - 1], [r, c])
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c - 1], flag_array(temp_array, 4)])
                
        queue.sort(key = lambda data:data[0])
        queue.sort(key = lambda data:data[2], reverse = True)

        data = []
        g_data = []
        #print(queue)
        """
        for i in range(len(queue)):
            data.append(str(queue[i][0]))
            g_data.append(str(queue[i][2]))
            #print(queue[i])
        print("g+h: ",' '.join(data))
        print("g: ",' '.join(g_data))
        """
        #if d == 1:
        #print(len(queue))

    if state == goal:
        break

Submission status: Accepted

Solution code:
# 8 Puzzle
import copy
[N, d] = [3, 0]
start = []
goal = [[i + j*N for i in range(1, N + 1)] for j in range(N)]
goal[2][2] = 0
for i in range(N):
    start.append(list(map(int, input().split())))


def manhattan(value, pairs):
    h = 0

    if value == 1:
        h = (pairs[0] + pairs[1])
    if value == 2:
        h = (pairs[0] + abs(pairs[1] - 1))
    if value == 3:
        h = (pairs[0] + abs(pairs[1] - 2))
    
    if value == 4:
        h = (abs(pairs[0] - 1) + pairs[1])
    if value == 5:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 1)) 
    if value == 6:
        h = (abs(pairs[0] - 1) + abs(pairs[1] - 2))
        
    if value == 7:
        h = (abs(pairs[0] - 2) + pairs[1])      
    if value == 8:
        h = (abs(pairs[0] - 2) + abs(pairs[1] - 1))
        
    return h

s_h = 0
for i in range(N):
    for j in range(N):
        s_h += manhattan(start[i][j], [i, j])

for i in range(N):
        check = start[i].count(0)
        if check != 0:
            [s_r, s_c] = [i, start[i].index(0)]
            break
        if i == 3:
            print("Error")

while True:
    d += 1
    flag = 0
    queue = [[s_h, start, 0, [s_r, s_c], flag]]
    
    while len(queue) != 0:
        short_n = queue.pop(0)
        h = short_n[0] - short_n[2]
        state = short_n[1]
        g = short_n[2]
        [r, c] = short_n[3]
        flag = short_n[4]
        
        if h == 0:
            print(short_n[2])
            break
       
        if r - 1 >= 0 and flag != 3:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r - 1][c], [r - 1, c]) + manhattan(temp[r - 1][c], [r, c])
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r - 1, c], 1])
        
        if c + 1 < N and flag != 4:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r][c + 1], [r, c + 1]) + manhattan(temp[r][c + 1], [r, c])
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c + 1], 2])

        if r + 1 < N and flag != 1:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r + 1][c], [r + 1, c]) + manhattan(temp[r + 1][c], [r, c])
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r + 1, c], 3])
        
        if c - 1 >= 0 and flag != 2:
            temp = copy.deepcopy(state)
            h = short_n[0] - short_n[2] - manhattan(temp[r][c - 1], [r, c - 1]) + manhattan(temp[r][c - 1], [r, c])
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1, [r, c - 1], 4])
                
        queue.sort(key = lambda data:data[0])
        queue.sort(key = lambda data:data[2], reverse = True)

        data = []
        g_data = []

    if state == goal:
        break

Submission status: Accepted

Solution code:
 
goal = ((1, 2, 3), (4, 5, 6), (7, 8, 0))

parents = {}
total = {}
flag = True

initial = []
position = []
for i in range(3):
	a, b, c = map(int, input().split())
	if a == 0:
		position.extend([i, 0])
	elif b == 0:
		position.extend([i, 1])
	elif c == 0:
 		position.extend([i, 2])
	initial.append( (a, b, c) )

parents[tuple(initial)] = position
total[tuple(initial)] = 1

count = 0

if tuple(initial) == goal:
	flag = False

while flag:
	count += 1
	children = {}
	for par_key in parents.keys():
		position = parents[par_key]

		if position[0] < 2:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]+1][position[1]]
			child[position[0]+1][position[1]] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0]+1, position[1]]
				total[child_tuple] = 1

		if position[0] > 0:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]-1][position[1]]
			child[position[0]-1][position[1]] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0]-1, position[1]]
				total[child_tuple] = 1

		if position[1] < 2:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]][position[1]+1]
			child[position[0]][position[1]+1] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0], position[1]+1]
				total[child_tuple] = 1

		if position[1] > 0:
			child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
			child[position[0]][position[1]] = child[position[0]][position[1]-1]
			child[position[0]][position[1]-1] = 0
			child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
			if child_tuple == goal:
				flag = False
				break
			elif child_tuple not in total:
				children[child_tuple] = [position[0], position[1]-1]
				total[child_tuple] = 1

	parents = children

print(count)

Submission status: Accepted

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 = {}
    history[tuple(start)] = True
    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[tuple(board)] = True
            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: Accepted

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.code, self.board, 0))

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


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

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


if __name__ == '__main__':
    run()

Submission status: Accepted

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 bfs(pzl):
    queue = deque([])
    V = {}
    pzl.path = ''
    queue.append(pzl)
    V[str(pzl.f)] = True
    if is_target(pzl): return pzl.path

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


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


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


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


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

ans = bfs(panel)
print(ans)

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()))
    goal = [1,2,3,4,5,6,7,8,0]
    st = set()
    inf = 1000000007
    move = [[1,3], #0がi番目にいる時に交換できる位置
            [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]) #局面、0の位置、ステップ数
        st.add(''.join(map(str, s)))
        while dq:
            state = dq.popleft()
            t, i, steps = state[0], state[1], state[2]
            if t == goal: return steps
            for j in move[i]:
                u = copy.copy(t)
                u[i], u[j] = u[j], u[i] #0を移動
                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:
from collections import deque

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys


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

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

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

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

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

print(n)

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import heappop, heappush


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

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


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


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


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


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

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

    return board


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

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

    return h


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

    dist = {}
    q = []

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

        if board == goal:
            return d

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

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


if __name__ == '__main__':
    main()