Problem:


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

15 Puzzle

  The goal of the 15 puzzle problem is to complete pieces on $4 \times 4$ 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 15 as shown below.

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

  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
9 10 11 12
13 14 15 0

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

Input

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

Output

  Print the fewest steps in a line.

Constraints

The given puzzle is solvable in at most 45 steps.

Sample Input

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

Sample Output

8



Sample input:
1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


Sample output:
8

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht*18//17+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht*25//24+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht*23//22+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//3+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht < ans:
                heapq.heappush(e,(mht+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Wrong Answer

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, 9, 10, 11, 12, 13, 14, 15, 0)


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

d = {start:1, end:-1}
queue = set([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.pop()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.update([(b, way)])
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Wrong Answer

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, 9, 10, 11, 12, 13, 14, 15, 0)


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

d = {start:1, end:-1}
queue = set([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.pop()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.update([(b, way)])
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

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=4
Y=4

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 = list(range(1,X*Y))+[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:
#!/usr/bin/python
#coding:utf-8

import heapq

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

X=4
Y=4

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 = []
	table ={}
	# ?????????????????????
	start_distance = make_distance_table(goal, X)
	a = State(start, start.index(0), None, 0, FORE)
	heapq.heappush(q,a)
	table[tuple(start)] = a
	# ??´???????????????
	goal_distance = make_distance_table(start, X)
	a = State(goal, goal.index(0), None, 0, BACK)
	heapq.heappush(q,a)
	table[tuple(goal)] = a
	while q:
		a = heapq.heappop(q)
		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
					# ??????????????????
					heapq.heappush(q,c)
			else:
				c = State(b, x, a, a.move + 1, a.dir)
				heapq.heappush(q,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 = list(range(1,X*Y))+[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:
#!/usr/bin/python
#coding:utf-8

import sys,heapq
if sys.version_info[0]>=3: raw_input=input

OPEN = 0
CLOSE = 1
FORE = 0
BACK = 1

X=4
Y=4

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 output(a):
	print(len(a)-1)
def backtrack(x):
	if x is not None:
		return backtrack(x.prev)+[x.board]
	return []
def forwardtrack(x):
	r=[]
	while x is not None:
		r.append(x.board)
		x = x.prev
	return r

def make_distance_table(board, wide):
	size = len(board)
	table = [[0]*size for _ in range(size)]
	for i in range(size):
		p = board[i]
		if p == 0: continue
		x1 = i / wide
		y1 = i % wide
		for j in range(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 range(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 __lt__(x, y):
		return x.cost<y.cost

def a_star_search(start, goal):
	global start_distance, goal_distance
	q = []
	table ={}
	# start
	start_distance = make_distance_table(goal, X)
	a = State(start, start.index(0), None, 0, FORE)
	heapq.heappush(q,a)
	table[tuple(start)] = a
	# goal
	goal_distance = make_distance_table(start, X)
	a = State(goal, goal.index(0), None, 0, BACK)
	heapq.heappush(q,a)
	table[tuple(goal)] = a
	while q:
		a = heapq.heappop(q)
		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:
						output(backtrack(a)+forwardtrack(c))
					else:
						output(backtrack(c)+forwardtrack(a))
					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
					heapq.heappush(q,c)
			else:
				c = State(b, x, a, a.move + 1, a.dir)
				heapq.heappush(q,c)
				table[key] = c
		a.kind = CLOSE

goal = list(range(1,X*Y))+[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:
#!/usr/bin/python
#coding:utf-8

import sys,heapq
if sys.version_info[0]>=3: raw_input=input

OPEN = 0
CLOSE = 1
FORE = 0
BACK = 1

X=4
Y=4

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 output(a):
	#for i in range(1,len(a)):
	#	for j in range(len(a[i])):
	#		if a[i][j]==0:
	#			print(a[i-1][j])
	#			break
	print(len(a)-1)
def backtrack(x):
	if x is not None:
		return backtrack(x.prev)+[x.board]
	return []
def forwardtrack(x):
	r=[]
	while x is not None:
		r.append(x.board)
		x = x.prev
	return r

def make_distance_table(board, wide):
	size = len(board)
	table = [[0]*size for _ in range(size)]
	for i in range(size):
		p = board[i]
		if p == 0: continue
		x1 = i / wide
		y1 = i % wide
		for j in range(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 range(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):
		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 __lt__(x, y):
		return x.cost<y.cost

def a_star_search(start, goal):
	global start_distance, goal_distance
	q = []
	table ={}
	# start
	start_distance = make_distance_table(goal, X)
	a = State(start, start.index(0), None, 0, FORE, OPEN)
	heapq.heappush(q,a)
	table[tuple(start)] = a
	# goal
	goal_distance = make_distance_table(start, X)
	a = State(goal, goal.index(0), None, 0, BACK, OPEN)
	heapq.heappush(q,a)
	table[tuple(goal)] = a
	while q:
		a = heapq.heappop(q)
		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:
						output(backtrack(a)+forwardtrack(c))
					else:
						output(backtrack(c)+forwardtrack(a))
					return
				if c.move > a.move + 1:
					if c.kind == OPEN:
						c.kind = CLOSE
						d = State(b, x, a, a.move + 1, a.dir, OPEN)
						table[key] = d
					else:
						c.prev = a
						c.cost = c.cost - c.move + a.move + 1
						c.move = a.move + 1
						c.kind = OPEN
					heapq.heappush(q,c)
			else:
				c = State(b, x, a, a.move + 1, a.dir, OPEN)
				heapq.heappush(q,c)
				table[key] = c
		a.kind = CLOSE

goal = list(range(1,X*Y))+[0]
a = []
try:
    while True:
        a+=[int(e) for e in raw_input().replace('*','0').split()]
except EOFError:
    pass

a_star_search(a, goal)

Submission status: Wrong Answer

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

import sys,heapq
if sys.version_info[0]>=3: raw_input=input

OPEN = 0
CLOSE = 1
FORE = 0
BACK = 1

X=4
Y=4

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 output(a):
	#for i in range(1,len(a)):
	#	for j in range(len(a[i])):
	#		if a[i][j]==0:
	#			print(a[i-1][j])
	#			break
	print(len(a)-1)
def backtrack(x):
	if x is not None:
		return backtrack(x.prev)+[x.board]
	return []
def forwardtrack(x):
	r=[]
	while x is not None:
		r.append(x.board)
		x = x.prev
	return r

def make_distance_table(board, wide):
	size = len(board)
	table = [[0]*size for _ in range(size)]
	for i in range(size):
		p = board[i]
		if p == 0: continue
		x1 = i / wide
		y1 = i % wide
		for j in range(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 range(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):
		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 __lt__(x, y):
		return x.cost<y.cost

def a_star_search(start, goal):
	global start_distance, goal_distance
	q = []
	table ={}
	# start
	start_distance = make_distance_table(goal, X)
	a = State(start, start.index(0), None, 0, FORE, OPEN)
	heapq.heappush(q,a)
	table[tuple(start)] = a
	# goal
	goal_distance = make_distance_table(start, X)
	a = State(goal, goal.index(0), None, 0, BACK, OPEN)
	heapq.heappush(q,a)
	table[tuple(goal)] = a
	while q:
		a = heapq.heappop(q)
		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:
						output(backtrack(a)+forwardtrack(c))
					else:
						output(backtrack(c)+forwardtrack(a))
					return
				if c.move > a.move + 1:
					if c.kind == OPEN:
						c.kind = CLOSE
						d = State(b, x, a, a.move + 1, a.dir, OPEN)
						table[key] = d
					else:
						c.prev = a
						c.cost = c.cost - c.move + a.move + 1
						c.move = a.move + 1
						c.kind = OPEN
					#heapq.heappush(q,c)
			else:
				c = State(b, x, a, a.move + 1, a.dir, OPEN)
				heapq.heappush(q,c)
				table[key] = c
		a.kind = CLOSE

goal = list(range(1,X*Y))+[0]
a = []
try:
    while True:
        a+=[int(e) for e in raw_input().replace('*','0').split()]
except EOFError:
    pass

a_star_search(a, goal)