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:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz,costs):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+checkSumCost(costs)) > depth):
        return

    if(i != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i-1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i-1)*3+j] = HS(i,j,_c_puz[(i-1)*3+j])
        iterative(i-1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(i != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i+1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i+1)*3+j] = HS(i,j,_c_puz[(i+1)*3+j])
        iterative(i+1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j-1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j-1] = HS(i,j,_c_puz[i*3+j]-1)
        iterative(i,j-1,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j+1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j+1] = HS(i,j,_c_puz[i*3+j+1])
        iterative(i,j+1,c_depth+1,_c_puz[0:],_costs[0:])

def checkSumCost(costs):
    value = 0
    for i in range(len(costs)):
        value+=costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki
    value = abs(i-ki)+abs(j-kj) 
    return value


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

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

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

i_start = 0
j_start = 0

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

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i
    costs[i] = HS(_i,_j,puz[i])

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

Submission status: Wrong Answer

Solution code:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz,costs):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+checkSumCost(costs)) > depth):
        return

    if(i != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i-1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i-1)*3+j] = HS(i,j,_c_puz[(i-1)*3+j])
        iterative(i-1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(i != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i+1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i+1)*3+j] = HS(i,j,_c_puz[(i+1)*3+j])
        iterative(i+1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j-1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j-1] = HS(i,j,_c_puz[i*3+j]-1)
        iterative(i,j-1,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j+1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j+1] = HS(i,j,_c_puz[i*3+j+1])
        iterative(i,j+1,c_depth+1,_c_puz[0:],_costs[0:])

def checkSumCost(costs):
    value = 0
    for i in range(len(costs)):
        value+=costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj) 
    return value


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

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

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

i_start = 0
j_start = 0

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

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i
    costs[i] = HS(_i,_j,puz[i])

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

Submission status: Wrong Answer

Solution code:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz,costs):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+checkSumCost(costs)) > depth):
        return

    if(i != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i-1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i-1)*3+j] = HS(i,j,_c_puz[(i-1)*3+j])
        iterative(i-1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(i != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i+1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i+1)*3+j] = HS(i,j,_c_puz[(i+1)*3+j])
        iterative(i+1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j-1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j-1] = HS(i,j,_c_puz[i*3+j]-1)
        iterative(i,j-1,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j+1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j+1] = HS(i,j,_c_puz[i*3+j+1])
        iterative(i,j+1,c_depth+1,_c_puz[0:],_costs[0:])

def checkSumCost(costs):
    value = 0
    for i in range(len(costs)):
        value+=costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj) 
    return value


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

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

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

i_start = 0
j_start = 0

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

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

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

Submission status: Wrong Answer

Solution code:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz,costs):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+checkSumCost(costs)) > depth):
        return

    if(i != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i-1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i-1)*3+j] = HS(i-1,j,_c_puz[(i-1)*3+j])
        iterative(i-1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(i != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i+1,j)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[(i+1)*3+j] = HS(i+1,j,_c_puz[(i+1)*3+j])
        iterative(i+1,j,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 0 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j-1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j-1] = HS(i,j-1,_c_puz[i*3+j]-1)
        iterative(i,j-1,c_depth+1,_c_puz[0:],_costs[0:])
    if(j != 2 and finding != 1):
        _c_puz = swapPuz(c_puz[0:],i,j,i,j+1)
        _costs = costs[0:]
        _costs[i*3+j] = HS(i,j,_c_puz[i*3+j])
        _costs[i*3+j+1] = HS(i,j+1,_c_puz[i*3+j+1])
        iterative(i,j+1,c_depth+1,_c_puz[0:],_costs[0:])

def checkSumCost(costs):
    value = 0
    for i in range(len(costs)):
        value+=costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj) 
    return value


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

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

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

i_start = 0
j_start = 0

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

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

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

Submission status: Wrong Answer

Solution code:
def iterative(i,j):
    q = []
    q.append((simpleHS(puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop(0)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_depth+c_dWithH) > depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),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)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

Submission status: Wrong Answer

Solution code:
import sys;
import heapq

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

    while len(q):
        c_dWithH, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        print(c_depth)
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),(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)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),(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(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


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

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

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

i_start = 0
j_start = 0

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

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

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

Submission status: Wrong Answer

Solution code:
import sys;
import heapq

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

    while len(q):
        items = q.pop(0)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        print(c_depth)
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),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)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),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(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


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

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

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

i_start = 0
j_start = 0

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

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

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

print(len(bfs(puzzle)))

Submission status: Wrong Answer

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

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


def manhattan(value, pairs):
    h = 0

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

def flag_array(flag, input):

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


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

# print(s_h)

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

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

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

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

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

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

    if state == goal:
        break

Submission status: Wrong Answer

Solution code:
import queue

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]

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
)

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev  = prev


def bf_search(start):
    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:
                print_answer(c)
                return

            q.put(c)
            table[key] = True


# 手順の表示
def print_answer(x):
    count = 0

    while x.prev != None:
        x = x.prev
        count += 1

    print(count)



if(__name__ == '__main__'):
    p = []
    for i in range(3):
        p.extend([int(x) for x in input().split()])

    print(p)
    bf_search(p)

Submission status: Wrong Answer

Solution code:
import queue

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]

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
)

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev  = prev


def bf_search(start):
    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:
                print_answer(c)
                return

            q.put(c)
            table[key] = True


# 手順の表示
def print_answer(x):
    count = 0

    while x.prev != None:
        x = x.prev
        count += 1

    print(count)



if(__name__ == '__main__'):
    p = []
    for i in range(3):
        p.extend([int(x) for x in input().split()])

    bf_search(p)

Submission status: Wrong Answer

Solution code:
import heapq


def check_goal(p):
    return p == [1, 2, 3, 4, 5, 6, 7, 8, 0]


def up(p):
    q = p.copy()
    zero = p.index(0)
    q[zero] = q[zero - 3]
    q[zero - 3] = 0
    return q


def low(p):
    q = p.copy()
    zero = p.index(0)
    q[zero] = q[zero + 3]
    q[zero + 3] = 0
    return q


def right(p):
    q = p.copy()
    zero = p.index(0)
    q[zero] = q[zero + 1]
    q[zero + 1] = 0
    return q


def left(p):
    q = p.copy()
    zero = p.index(0)
    q[zero] = q[zero - 1]
    q[zero - 1] = 0
    return q


def cost(p, n_mov):
    c = n_mov
    for i in range(9):
        if p[i] != (i + 1) % 9:
            c += 1
    return c


def solve(p):
    ans = 0
    zero = p.index(0)
    will = list()
    done = [p]
    while not check_goal(p):
        ans += 1
        if zero >= 3 and up(p) not in done:
            done.append(up(p))
            heapq.heappush(will, (up(p), ans))
        if zero <= 5 and low(p) not in done:
            done.append(low(p))
            heapq.heappush(will, (low(p), ans))
        if zero % 3 <= 1 and right(p) not in done:
            done.append(right(p))
            heapq.heappush(will, (right(p), ans))
        if zero % 3 >= 1 and left(p) not in done:
            done.append(left(p))
            heapq.heappush(will, (left(p), ans))
        p, ans = heapq.heappop(will)
        zero = p.index(0)
    return ans


p = list(map(int, input().split()))
p.extend(list(map(int, input().split())))
p.extend(list(map(int, input().split())))
print(solve(p))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from itertools import chain
from operator import mul

exp10 = [10 ** a for a in range(8, -1, -1)]
movables = [{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}]

destination = 123456780


def swap(board, move_from, move_to):
    return board + (exp10[move_to] - exp10[move_from]) * (board // exp10[move_from] % 10)


board0 = sum(map(mul, exp10, chain.from_iterable(map(int, input().split()) for _ in range(3))))
p0 = ('0' + str(board0))[-9:].index('0')

appeared = {board0}
queue = list((0, move_from, p0, board0) for move_from in movables[p0])
heapq.heapify(queue)

while True:
    total_cost, move_from, move_to, board = heapq.heappop(queue)
    if board == destination:
        print(total_cost)
        break
    new_board = swap(board, move_from, move_to)
    if new_board in appeared:
        continue
    for move_from2 in movables[move_from]:
        if move_from2 != move_to:
            heapq.heappush(queue, (total_cost + 1, move_from2, move_from, new_board))

Submission status: Time Limit Exceeded

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)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    for q in queue:
        state, zero_x, zero_y = 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 not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    trial += 1
print(trial)