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: Runtime Error

Solution code:
import queue
adjacent=(
    (1,4), 
    (0,2,5),
    (1,3,6),
    (2,7),
    (0,5,8),
    (1,4,6,9),
    (2,5,7,10),
    (3,6,11),
    (4,9,12),
    (5,8,10,13),
    (6,9,11,14),
    (7,10,15),
    (8,13),
    (9,12,14),
    (10,13,15),
    (11,14),
)
 
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),
)
 
def get_distance(board):
    v = 0
    for x in range(16):
        p = board[x]
        if p == 0: continue
        v += distance[p][x]
    return v
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,0]
 
board = []
for i in range(4):
    a,b,c,d = map(int, input().split())
    board += [a,b,c,d]
 
move_piece = [None] * 46
 
def id_lower_search(limit, move, space, lower):
    global AL
    if move == limit:
        if board == GOAL:
            global count
            count += 1
            i = move_piece[1:].index(None)
            AL.append(len(move_piece[1:i + 1]))

    else:
        for x in adjacent[space]:
            p = board[x]
            if move_piece[move] == p: continue
            board[space] = p
            board[x] = 0
            move_piece[move + 1] = p
            new_lower = lower - distance[p][x] + distance[p][space]
            if new_lower + move <= limit:
                id_lower_search(limit, move + 1, x, new_lower)
            board[space] = 0
            board[x] = p

count = 0
n = get_distance(board)
AL = []
for x in range(n, 46):
    id_lower_search(x, 0, board.index(0), n)
    if count > 0: break
print(min(AL))

Submission status: Runtime Error

Solution code:
from sys import stdin
import copy
dx = tuple(1,0,-1,0)
dy = tuple(0,1,0,-1)
dir = "ruld"
N = 4
N2 = 16
LIMIT = 50
MDT = ((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))
class Puzzle():
    def __init__(self):
        self.f = [0] * N2
        self.space, self.MD = 0, 0
state = Puzzle()
limit = 0
path = [0] * LIMIT
def dfs(depth, prev, limit, state, path):
    if state.MD == 0: return True
    if depth + state.MD > limit: return False
    sx = state.space // N
    sy = state.space % N
    tmp = Puzzle()
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N: continue
        if max(prev, r) - min(prev, r) == 2: continue
        tmp = copy.deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            path[depth] = r
            return True
        state = copy.deepcopy(tmp)
    return False
In = Puzzle()
for k in range(N2 // 4):
    for n, j in enumerate(map(int, stdin.readline().split())):
        i = k * 4 + n
        if j == 0:
            In.f[i] = N2
            In.space = i
        else:
            In.f[i] = j
for i in range(0, N2):
    if (In.f[i] == N2): continue
    In.MD += MDT[i][In.f[i] - 1]
ans = ""
for limit in range(In.MD, LIMIT + 1):
    state = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Submission status: Runtime Error

Solution code:
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def heauristic(here_x, here_y):
    return abs((WIDTH - 1) - here_x) + abs((WIDTH - 1) - here_y)
ini_state = []
for i in range(WIDTH):
    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], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [0, ini_state, zero_x, zero_y, 0, "start"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
if hashnum(ini_state) == answer:
    print(0)
else:
    trial = 0
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        here = hashnum(state)
        if here == end_hash:
            print(now_cost)
            break
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(len(dx)):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    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 not in visited:
                        estimated_cost = heauristic(zero_x, zero_y)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, "start"])
                    elif now_cost < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, "start"])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
x = input()
n = int(input())

for i in range(n):
    y = input()
    if y in x:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
x = input()
n = int(input())

print(n)
for i in range(n):
    y = input()
    if y in x:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = (a >> 4 * j) % 16
    return a - (t << 4 * j) + (t << 4 * i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            TABLE.append(key)
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Runtime Error

Solution code:
import sys;
import heapq
from collections import deque

def iterative(i,j):
    q = deque()
    q.append((sumcost,0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop()
        cost = items[0]
        
        if(cost > depth):
            continue

        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _sum_cost = cost - c_depth

        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        _i4 = _i*4
        c_cost = HS(_i,_j,c_puz[_i4+_j])
        #c2_cost = simpleHS(_i,_j,c_puz[_i*4+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+checkCost(c_cost,HS(_i-1,_j,c_puz[_i4+4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i-1,_j,swap_puz[_i4-4+_j]))
            #n_cost += checkCost(c2_cost,simpleHS(_i-1,_j,c_puz[(_i-1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+checkCost(c_cost,HS(_i+1,_j,c_puz[_i4+4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i+1,_j,swap_puz[_i4+4+_j]))
            #n_cost += checkCost(c2_cost,simpleHS(_i+1,_j,c_puz[(_i+1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= depth):
                q.append((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+checkCost(c_cost,HS(_i,_j-1,c_puz[_i4+_j-1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j-1,swap_puz[_i4+_j-1]))
            #n_cost += checkCost(c2_cost,simpleHS(_i,_j-1,c_puz[_i*4+_j-1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+checkCost(c_cost,HS(_i,_j+1,c_puz[_i4+_j+1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j+1,swap_puz[_i4+_j+1]))
            #n_cost += checkCost(c2_cost,simpleHS(_i,_j+1,c_puz[_i*4+_j+1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= depth):
                q.append((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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

def simpleHS(i,j,puz):
    if(not correctPuz[i+j] == puz):
        return 1
    return 0

def HS(i,j,num):
    k = num-1
    if(k == -1):
        k = 15
    ki = (int)(k/4)
    kj = k - ki*4
    value = abs(i-ki)+abs(j-kj)
    return value

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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)
#sum2cost = 0
#for i in range(4):
#    sum2cost += simpleHS(i*4,0,puz[i*4])
#    sum2cost += simpleHS(i*4,1,puz[i*4+1])
#    sum2cost += simpleHS(i*4,2,puz[i*4+2])
#    sum2cost += simpleHS(i*4,3,puz[i*4+3])

finding = 0
depth = 45
iterative(i_start,j_start)