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

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

Submission status: Wrong Answer

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):
    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:
                    print(table[key][1] + i)
                    return
                continue
            table[key] = (direction, i)
            if b == end:
                print(i)
                return
            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]
    search(start)
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
#coding:utf-8

def _downheap(buff, n):
	size = len(buff)
	while True:
		c = 2 * n + 1
		if c >= size: break
		if c + 1 < size:
			if buff[c] > buff[c + 1]: c += 1
		if buff[n] <= buff[c]: break
		temp = buff[n]
		buff[n] = buff[c]
		buff[c] = temp
		n = c

# ???????????????
def _upheap(buff, n):
	while True:
		p = (n - 1) / 2
		if p < 0 or buff[p] <= buff[n]: break
		temp = buff[n]
		buff[n] = buff[p]
		buff[p] = temp
		n = p

class PQueue:
	def __init__(self, buff = []):
		self.buff = buff[:]   # ?????????
		for n in xrange(len(self.buff) / 2 - 1, -1, -1):
			_downheap(self.buff, n)

	# ??????????????????
	def push(self, data):
		self.buff.append(data)
		_upheap(self.buff, len(self.buff) - 1)

	# ????°???????????????????
	def pop(self):
		if len(self.buff) == 0: raise IndexError
		value = self.buff[0]
		last = self.buff.pop()
		if len(self.buff) > 0:
			# ????????????????§????
			self.buff[0] = last
			_downheap(self.buff, 0)
		return value

	# ????°????????±???????
	def peek(self):
		if len(self.buff) == 0: raise IndexError
		return self.buff[0]

	# ??????
	def isEmpty(self): return len(self.buff) == 0


import time

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

# ?????°
OPEN = 0
CLOSE = 1
FORE = 0
BACK = 1

# ?????¢??¨?????????
def make_distance_table(board, wide):
	size = len(board)
	table = [[0] * size for _ in xrange(size)]
	for i in xrange(size):
		p = board[i]
		if p == 0: continue
		x1 = i / wide
		y1 = i % wide
		for j in xrange(size):
			x2 = j / wide
			y2 = j % wide
			table[p][j] += max(x1 - x2, x2 - x1)
			table[p][j] += max(y1 - y2, y2 - y1)
	return table

# ?????¢????±???????
def get_distance(board, distance):
	v = 0
	for x in xrange(9):
		p = board[x]
		if p == 0: continue
		v += distance[p][x]
	return v

# ?±???¢?????????
class State:
	def __init__(self, board, space, prev, move, dir, kind = OPEN):
		self.board = board
		self.space = space
		self.prev = prev
		self.move = move
		self.dir = dir
		self.kind = kind
		if dir == FORE:
			dt = start_distance
		else:
			dt = goal_distance
		if prev is None:
			self.cost = move + get_distance(board, dt)
		else:
			p = board[prev.space]
			self.cost = prev.cost + 1 - dt[p][space] + dt[p][prev.space]

	def __cmp__(x, y):
		return x.cost - y.cost

# ???????????? A* ??¢?????´?????????
def a_star_search(start, goal):
	global start_distance, goal_distance
	q = PQueue()
	table ={}
	# ?????????????????????
	start_distance = make_distance_table(goal, 3)
	a = State(start, start.index(0), None, 0, FORE)
	q.push(a)
	table[tuple(start)] = a
	# ??´???????????????
	goal_distance = make_distance_table(start, 3)
	a = State(goal, goal.index(0), None, 0, BACK)
	q.push(a)
	table[tuple(goal)] = a
	while not q.isEmpty():
		a = q.pop()
		if a.kind == CLOSE: continue   # ????£????????????§??????
		for x in adjacent[a.space]:
			b = a.board[:]
			b[a.space] = b[x]
			b[x] = 0
			key = tuple(b)
			if key in table:
				# ???????±???¢?????????
				c = table[key]
				if a.dir != c.dir:
					# ??????
					if a.dir == FORE:
						print print_answer(a)+print_answer_goal(c)-1
					else:
						print print_answer(c)+print_answer_goal(a)-1
					return
				# ?????¢???????????????????????°?????????????????°??????
				if c.move > a.move + 1:
					# ??´??°??????
					if c.kind == OPEN:
						c.kind = CLOSE
						c = State(b, x, a, a.move + 1, a.dir)
						table[key] = c
					else:
						c.prev = a
						c.cost = c.cost - c.move + a.move + 1
						c.move = a.move + 1
						c.kind = OPEN
					# ??????????????????
					q.push(c)
			else:
				c = State(b, x, a, a.move + 1, a.dir)
				q.push(c)
				table[key] = c
		# a ???????????????????±??????????
		a.kind = CLOSE

# ???????????¨???
def print_answer(x):
	if x is not None:
		return 1+print_answer(x.prev)
		#print x.board
	return 0

def print_answer_goal(x):
	r=0
	while x is not None:
		#print x.board
		x = x.prev
		r+=1
	return r

# ??????
goal = [1,2,3,4,5,6,7,8,0]
a = []
try:
	while True:
		a+=[int(e) for e in raw_input().split()]
except EOFError:
	pass

#s = time.clock()
a_star_search(a, goal)
#e = time.clock()
#print "%.3f" % (e - s)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
#coding:utf-8

def _downheap(buff, n):
	size = len(buff)
	while True:
		c = 2 * n + 1
		if c >= size: break
		if c + 1 < size:
			if buff[c] > buff[c + 1]: c += 1
		if buff[n] <= buff[c]: break
		temp = buff[n]
		buff[n] = buff[c]
		buff[c] = temp
		n = c

# ???????????????
def _upheap(buff, n):
	while True:
		p = (n - 1) / 2
		if p < 0 or buff[p] <= buff[n]: break
		temp = buff[n]
		buff[n] = buff[p]
		buff[p] = temp
		n = p

class PQueue:
	def __init__(self, buff = []):
		self.buff = buff[:]   # ?????????
		for n in xrange(len(self.buff) / 2 - 1, -1, -1):
			_downheap(self.buff, n)

	# ??????????????????
	def push(self, data):
		self.buff.append(data)
		_upheap(self.buff, len(self.buff) - 1)

	# ????°???????????????????
	def pop(self):
		if len(self.buff) == 0: raise IndexError
		value = self.buff[0]
		last = self.buff.pop()
		if len(self.buff) > 0:
			# ????????????????§????
			self.buff[0] = last
			_downheap(self.buff, 0)
		return value

	# ????°????????±???????
	def peek(self):
		if len(self.buff) == 0: raise IndexError
		return self.buff[0]

	# ??????
	def isEmpty(self): return len(self.buff) == 0

# ?????°
OPEN = 0
CLOSE = 1
FORE = 0
BACK = 1

X=3
Y=3

adjacent=[]
for coor in range(X*Y):
	lst=[]
	x=coor%X
	y=coor/X
	if 0<x: lst.append(coor-1)
	if x<X-1: lst.append(coor+1)
	if 0<y: lst.append(coor-X)
	if y<Y-1: lst.append(coor+X)
	adjacent.append(lst)

# ?????¢??¨?????????
def make_distance_table(board, wide):
	size = len(board)
	table = [[0] * size for _ in xrange(size)]
	for i in xrange(size):
		p = board[i]
		if p == 0: continue
		x1 = i / wide
		y1 = i % wide
		for j in xrange(size):
			x2 = j / wide
			y2 = j % wide
			table[p][j] += max(x1 - x2, x2 - x1)
			table[p][j] += max(y1 - y2, y2 - y1)
	return table

# ?????¢????±???????
def get_distance(board, distance):
	v = 0
	for x in xrange(X*Y):
		p = board[x]
		if p == 0: continue
		v += distance[p][x]
	return v

# ?±???¢?????????
class State:
	def __init__(self, board, space, prev, move, dir, kind = OPEN):
		self.board = board
		self.space = space
		self.prev = prev
		self.move = move
		self.dir = dir
		self.kind = kind
		if dir == FORE:
			dt = start_distance
		else:
			dt = goal_distance
		if prev is None:
			self.cost = move + get_distance(board, dt)
		else:
			p = board[prev.space]
			self.cost = prev.cost + 1 - dt[p][space] + dt[p][prev.space]

	def __cmp__(x, y):
		return x.cost - y.cost

# ???????????? A* ??¢?????´?????????
def a_star_search(start, goal):
	global start_distance, goal_distance
	q = PQueue()
	table ={}
	# ?????????????????????
	start_distance = make_distance_table(goal, X)
	a = State(start, start.index(0), None, 0, FORE)
	q.push(a)
	table[tuple(start)] = a
	# ??´???????????????
	goal_distance = make_distance_table(start, X)
	a = State(goal, goal.index(0), None, 0, BACK)
	q.push(a)
	table[tuple(goal)] = a
	while not q.isEmpty():
		a = q.pop()
		if a.kind == CLOSE: continue   # ????£????????????§??????
		for x in adjacent[a.space]:
			b = a.board[:]
			b[a.space] = b[x]
			b[x] = 0
			key = tuple(b)
			if key in table:
				# ???????±???¢?????????
				c = table[key]
				if a.dir != c.dir:
					# ??????
					if a.dir == FORE:
						print print_answer(a)+print_answer_goal(c)-1
					else:
						print print_answer(c)+print_answer_goal(a)-1
					return
				# ?????¢???????????????????????°?????????????????°??????
				if c.move > a.move + 1:
					# ??´??°??????
					if c.kind == OPEN:
						c.kind = CLOSE
						c = State(b, x, a, a.move + 1, a.dir)
						table[key] = c
					else:
						c.prev = a
						c.cost = c.cost - c.move + a.move + 1
						c.move = a.move + 1
						c.kind = OPEN
					# ??????????????????
					q.push(c)
			else:
				c = State(b, x, a, a.move + 1, a.dir)
				q.push(c)
				table[key] = c
		# a ???????????????????±??????????
		a.kind = CLOSE

# ???????????¨???
def print_answer(x):
	if x is not None:
		return 1+print_answer(x.prev)
		#print x.board
	return 0

def print_answer_goal(x):
	r=0
	while x is not None:
		#print x.board
		x = x.prev
		r+=1
	return r

# ??????
goal = [1,2,3,4,5,6,7,8,0]
a = []
try:
    while True:
        a+=[int(e) for e in raw_input().split()]
except EOFError:
    pass

a_star_search(a, goal)

Submission status: Wrong Answer

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]

print(bf_search(start, GOAL))

Submission status: Wrong Answer

Solution code:
# coding=utf-8
import heapq as hq

def next_board(board, space, prev):
    for nxt in adjacent[space]:
        if nxt == prev:
            continue
        b = board.copy()
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt

def search(start):
    FORE = 1
    BACK = -1

    table = {}
    table[tuple(start)] = (FORE, 0)
    table[tuple(goal)] = (BACK, 0)

    heap = [(0, start, start.index(0), None, FORE), (0, goal, goal.index(0), None, BACK)]

    while heap:
        i, board, space, prev, direction = hq.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
            table[key] = (direction, i)
            hq.heappush(heap, (i, b, b.index(0), nxt, direction))

adjacent = (
    (1, 3),
    (0, 2, 4),
    (1, 5),
    (0, 4, 6),
    (1, 3, 5, 7),
    (2, 4, 8),
    (3, 7),
    (4, 6, 8),
    (5, 7),
)
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
start = []

for _ in range(3):
    x = list(map(int, input().split()))
    start += x

print(search(start))

Submission status: Wrong Answer

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:
                print(s)
                break

bfs(init)

Submission status: Wrong Answer

Solution code:
import sys

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

# Bidirectional search using breadth-first search
def solve(start, goal):
    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: Wrong Answer

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 = {}
visited[hashnum(ini_state)] = [0, 0]
visited[answer] = [0, 1]
trial = 0
while answer not in visited:
    new_queue = []
    trial += 1
    for q in queue:
        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])
                    exit()
                if perm not in visited:
                    visited[perm] = [trial, direction]
                    new_queue.append([new_state, new_x, new_y, direction])
    queue = new_queue

Submission status: Wrong Answer

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 = {}
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: Wrong Answer

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x = (i+1)%3
        y = (i+1)//3
        if y == 3:
            y = 0
        dx = abs(node_list[i]%3 - x)
        dy = abs(node_list[i]//3 - y)
        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.append(b_now.node)
    for b_new in b_now.makeBoard():
        if 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: Wrong Answer

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x = (i+1)%3
        y = (i+1)//3
        if y == 3:
            y = 0
        dx = abs(node_list[i]%3 - x)
        dy = abs(node_list[i]//3 - y)
        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.append(b_now.node)
    for b_new in b_now.makeBoard():
        if 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.node, b_goal.g)

Submission status: Wrong Answer

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x = (i+1)%3
        y = (i+1)//3
        if y == 3:
            y = 0
        dx = abs(node_list[i]%3 - x)
        dy = abs(node_list[i]//3 - y)
        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.append(b_now.node)
    for b_new in b_now.makeBoard():
        if 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: Wrong Answer

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

print(b_start.node, b_start.f)

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close.append(b_now.node)
    for b_new in b_now.makeBoard():
        if 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)