Buggy python submission (verdict: Runtime Error):
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(15):
        x_goal = i%4
        y_goal = i//4
        x_now = (node_list[i] - 1)%4
        y_now = (node_list[i] - 1)//4
        if y_now == -1:
            y_now = 3
        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%4
        y_s = space//4
        if x_s < 3:
            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 < 3:
            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,,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard():
        if "".join(map(str, b_new.node)) in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Fixed submission:
import heapq

distance = (
            (0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
            (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
            (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
            (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
            (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
            (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
            (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
            (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
            (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
            (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
            (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
            (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
            (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
            (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
            (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        j = node_list[i] - 1
        if j == -1: continue
        s += distance[i][j]
    return s

def moveNode(node_list, space, direction):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + direction] = node_tmp[space + direction], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, move):
        self.node = node_list
        self.space = node_list.index(0)
        self.move = move
        self.h = d_manhattan(node_list)
        self.f = self.move + self.h

    def makeBoard(self, node_close):
        node_now = self.node
        space = self.space
        move = self.move
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNode(node_now, space, 1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if x_s > 0:
            node_tmp = moveNode(node_now, space, -1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s < 3:
            node_tmp = moveNode(node_now, space, 4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s > 0:
            node_tmp = moveNode(node_now, space, -4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)

b_open = []
n_close =set()
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    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.add(tuple(b_now.node))
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.move)

Buggy python submission (verdict: Runtime Error):
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(15):
        x_goal = i%4
        y_goal = i//4
        x_now = (node_list[i] - 1)%4
        y_now = (node_list[i] - 1)//4
        if y_now == -1:
            y_now = 3
        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 - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], 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%4
        y_s = space//4
        if x_s < 3:
            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 < 3:
            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,,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard():
        if "".join(map(str, b_new.node)) in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Fixed submission:
import heapq

distance = (
            (0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
            (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
            (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
            (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
            (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
            (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
            (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
            (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
            (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
            (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
            (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
            (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
            (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
            (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
            (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        j = node_list[i] - 1
        if j == -1: continue
        s += distance[i][j]
    return s

def moveNode(node_list, space, direction):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + direction] = node_tmp[space + direction], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, move):
        self.node = node_list
        self.space = node_list.index(0)
        self.move = move
        self.h = d_manhattan(node_list)
        self.f = self.move + self.h

    def makeBoard(self, node_close):
        node_now = self.node
        space = self.space
        move = self.move
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNode(node_now, space, 1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if x_s > 0:
            node_tmp = moveNode(node_now, space, -1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s < 3:
            node_tmp = moveNode(node_now, space, 4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s > 0:
            node_tmp = moveNode(node_now, space, -4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)

b_open = []
n_close =set()
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    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.add(tuple(b_now.node))
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.move)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        x_goal = i%4
        y_goal = i//4
        x_now = (node_list[i] - 1)%4
        y_now = (node_list[i] - 1)//4
        if y_now == -1:
            continue
        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 - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], 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%4
        y_s = space//4
        if x_s < 3:
            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 < 3:
            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,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard():
        if "".join(map(str, b_new.node)) in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Fixed submission:
import heapq

distance = (
            (0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
            (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
            (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
            (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
            (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
            (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
            (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
            (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
            (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
            (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
            (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
            (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
            (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
            (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
            (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        j = node_list[i] - 1
        if j == -1: continue
        s += distance[i][j]
    return s

def moveNode(node_list, space, direction):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + direction] = node_tmp[space + direction], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, move):
        self.node = node_list
        self.space = node_list.index(0)
        self.move = move
        self.h = d_manhattan(node_list)
        self.f = self.move + self.h

    def makeBoard(self, node_close):
        node_now = self.node
        space = self.space
        move = self.move
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNode(node_now, space, 1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if x_s > 0:
            node_tmp = moveNode(node_now, space, -1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s < 3:
            node_tmp = moveNode(node_now, space, 4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s > 0:
            node_tmp = moveNode(node_now, space, -4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)

b_open = []
n_close =set()
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    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.add(tuple(b_now.node))
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.move)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        x_goal = i%4
        y_goal = i//4
        x_now = (node_list[i] - 1)%4
        y_now = (node_list[i] - 1)//4
        if y_now == -1:
            continue
        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 - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], 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, node_close):
        space = self.space
        cost_now = self.f
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNodeE(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s < 3:
            node_tmp = moveNodeS(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Fixed submission:
import heapq

distance = (
            (0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
            (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
            (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
            (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
            (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
            (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
            (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
            (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
            (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
            (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
            (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
            (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
            (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
            (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
            (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        j = node_list[i] - 1
        if j == -1: continue
        s += distance[i][j]
    return s

def moveNode(node_list, space, direction):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + direction] = node_tmp[space + direction], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, move):
        self.node = node_list
        self.space = node_list.index(0)
        self.move = move
        self.h = d_manhattan(node_list)
        self.f = self.move + self.h

    def makeBoard(self, node_close):
        node_now = self.node
        space = self.space
        move = self.move
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNode(node_now, space, 1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if x_s > 0:
            node_tmp = moveNode(node_now, space, -1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s < 3:
            node_tmp = moveNode(node_now, space, 4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s > 0:
            node_tmp = moveNode(node_now, space, -4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)

b_open = []
n_close =set()
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    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.add(tuple(b_now.node))
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.move)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

distance = (
            (0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
            (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
            (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
            (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
            (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
            (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
            (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
            (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
            (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
            (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
            (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
            (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
            (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
            (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
            (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    global distance
    s = 0
    for i in range(16):
        if node_list[i] == 0:
            continue
        s += distance[i][node_list[i] - 1]
    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 - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], 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, node_close):
        space = self.space
        cost_now = self.f
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNodeE(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s < 3:
            node_tmp = moveNodeS(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Fixed submission:
import heapq

distance = (
            (0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
            (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
            (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
            (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
            (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
            (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
            (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
            (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
            (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
            (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
            (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
            (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
            (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
            (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
            (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        j = node_list[i] - 1
        if j == -1: continue
        s += distance[i][j]
    return s

def moveNode(node_list, space, direction):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + direction] = node_tmp[space + direction], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, move):
        self.node = node_list
        self.space = node_list.index(0)
        self.move = move
        self.h = d_manhattan(node_list)
        self.f = self.move + self.h

    def makeBoard(self, node_close):
        node_now = self.node
        space = self.space
        move = self.move
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNode(node_now, space, 1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if x_s > 0:
            node_tmp = moveNode(node_now, space, -1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s < 3:
            node_tmp = moveNode(node_now, space, 4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s > 0:
            node_tmp = moveNode(node_now, space, -4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)

b_open = []
n_close =set()
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    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.add(tuple(b_now.node))
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.move)