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: Accepted

Solution code:
from collections import deque

N = 3
M = 3
board = []
expected = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

queue = deque()
bqueue = deque()

history = set()
# todo 数字で表す
# todo 2分担作にする


def swap(x1, y1, x2, y2, b):
    # 2次元配列を浅いコピーするなんて
    t = [x[:] for x in b]
    t[x1][y1], t[x2][y2] = t[x2][y2], t[x1][y1]
    return t


def p2i(b):
    tmp = 0
    for i in range(N):
        for j in range(M):
            tmp += b[i][j] * 10**(3*i+j)
    return tmp


def bfs():
    if expected == board:
        print(0)
        exit(0)

    while len(queue):
        pazzle = queue.popleft()
        cost = bqueue.popleft()
        # 0の場所を探す
        xz = None
        yz = None
        for i in range(N):
            for j in range(M):
                if pazzle[i][j] == 0:
                    xz, yz = i, j
        # 動かすことのできる方向を全て調べる
        xm = [1, 0, 0, -1]
        ym = [0, -1, 1, 0]
        for k in range(4):
            if 0 <= xz + xm[k] < N and 0 <= yz + ym[k] < N:
                # １手動かしてあったら終了。なかったら次の手に行く。
                t = swap(xz, yz, xz + xm[k], yz + ym[k], pazzle)
                ipz = p2i(t)
                if 87654321 == ipz:
                    print(cost+1)
                    exit(0)
                # 今までに出てないならキューに追加
                if ipz not in history:
                    queue.append(t)
                    history.add(ipz)
                    bqueue.append(cost+1)


for i in range(N):
    board.append(list(map(int, input().split())))
queue.append(board)
bqueue.append(0)
bfs()

Submission status: Accepted

Solution code:
from collections import deque
CORRECT_STATE = "123456780"


class PuzzleState:
    __slots__ = ['state', 'spc_x', 'spc_y', 'depth']

    def __init__(self, state: str, depth=0):
        self.state = state
        index = state.find('0')
        self.spc_x = index % 3
        self.spc_y = index // 3
        self.depth = depth

    def swap_state(self, ch_x, ch_y):
        conv_char = self.state[ch_y * 3 + ch_x]
        self.state = self.state.replace('0', 'X')
        self.state = self.state.replace(conv_char, '0')
        self.state = self.state.replace('X', conv_char)
        self.spc_x, self.spc_y = ch_x, ch_y

    def is_correct(self):
        return self.state == CORRECT_STATE

    def __repr__(self):
        return f'{self.state}'


move = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def puzzle8_breadth_first_search(puzzle: PuzzleState):
    mem_state = {puzzle.state: ''}
    p_queue = deque()
    p_queue.append(puzzle)

    while len(p_queue) != 0:
        u = p_queue.popleft()
        if u.is_correct():
            #print("CORRECT")
            return u.depth
        for mx, my in move:
            sp_new_x = u.spc_x + mx
            sp_new_y = u.spc_y + my
            if not(0 <= sp_new_x <= 2 and 0 <= sp_new_y <= 2):
                continue
            new_puzzle = PuzzleState(u.state, depth=u.depth+1)
            new_puzzle.swap_state(sp_new_x, sp_new_y)

            if new_puzzle.state not in mem_state:
                mem_state[new_puzzle.state] = ''
                p_queue.append(new_puzzle)
    return False


def main():
    input_text = ""
    for i in range(3):
        input_text += "".join(input().split())

    # 8 puzzle main
    ans_puzzle = puzzle8_breadth_first_search(PuzzleState(input_text))
    print(ans_puzzle)
    return

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = 3
M = []
for i in range(N):
    M.append(list(map(int, input().split())))

A = (1, 2, 3, 4, 5, 6, 7, 8, 0)
def h(M):
    c = 0
    it = iter(A).__next__
    for i in range(N):
        for v in M[i]:
            if v != it():
                c += 1
    return c
def f(M):
    M0 = []
    for m in M:
        M0.extend(m)
    return tuple(M0)


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
ci = cj = -1
for i in range(N):
    for j in range(N):
        if M[i][j] == 0:
            ci = i; cj = j
que = [(h(M), 0, ci, cj, M)]
U = set(f(M))
while que:
    hc, c, cr, cc, M = heappop(que)
    if hc == c:
        print(c)
        break
    for dr, dc in dd:
        nr = cr+dr; nc = cc+dc
        if not 0 <= nr < N or not 0 <= nc < N:
            continue
        MM = [m[:] for m in M]
        MM[cr][cc] = MM[nr][nc]
        MM[nr][nc] = 0
        s = f(MM)
        if s in U:
            continue

        U.add(s)
        heappush(que, (h(MM)+c+1, c+1, nr, nc, MM))

Submission status: Accepted

Solution code:
from collections import deque, OrderedDict

class Puzzle:
    def __init__(self, field=None, path=''):
        self.f = field
        self.space = None
        for i in range(9):
            if self.f[i] == 9:
                self.space = i
        self.path = path

    def __lt__(self, pzl): # <
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] > pzl.f[i]
        return False

    def __gt__(self, pzl): # >
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] < pzl.f[i]
        return False

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
dir = ['u', 'l', 'd', 'r']

def is_target(pzl):
    for i in range(9):
        if pzl.f[i] != i+1:
            return False
    return True

def bfs(pzl):
    queue = deque([])
    V = {}
    pzl.path = ''
    queue.append(pzl)
    V[str(pzl.f)] = True
    if is_target(pzl):
      return pzl.path

    while len(queue) != 0:
        u = queue.popleft()
        sx, sy = u.space//3, u.space%3
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= 3 or ty >= 3:
                continue
            v = Puzzle(field=[u.f[i] for i in range(9)], path=u.path)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if str(v.f) not in V:
                V[str(v.f)] = True
                v.path += dir[r]
                if is_target(v): return v.path
                queue.append(v)
    return 'unsolvable'

field = []
for i in range(3):
    field.extend(list(map(int, input().split(' '))))

for i in range(9):
    if field[i] == 0: field[i] = 9

pzl = Puzzle(field=field)
ans= bfs(pzl)
print(len(ans))

Submission status: Accepted

Solution code:
from collections import deque
board = [int(s) for _ in range(3) for s in input().split()]
end = [1, 2, 3, 4, 5, 6, 7, 8, 0]
table = set()
def print_board(board):
    for i in range(0, 9, 3):
        print(*board[i:i + 3])

def swap(q, step_q, step, board):
    key = tuple(board)
    if key in table:
        return
    else:
        table.add(key)

    empty = board.index(0)
    def _swap(q, step_q, step, board, k, s):
        b = board.copy()
        b[k], b[s] = b[s], b[k]
        q.append(b)
        step_q.append(step + 1)

    if empty % 3 != 2:
        _swap(q, step_q, step, board, empty, empty + 1)
    if empty % 3 != 0:
        _swap(q, step_q, step, board, empty, empty - 1)
    if empty // 3 < 2:
        _swap(q, step_q, step, board, empty, empty + 3)
    if empty // 3 > 0:
        _swap(q, step_q, step, board, empty, empty - 3)


q = deque([board])
step_q = deque([0])
# print_board(board)
while q[0] != end:
    b = q.popleft()
    step = step_q.popleft()
    swap(q, step_q, step, b)
# print_board(q.popleft())
print(step_q.popleft())

Submission status: Accepted

Solution code:
start =  list(map(int, [n for a in [input().split() for i in range(3)] for n in a]))
goal = [1, 2, 3, 4, 5 ,6, 7, 8, 0]

adjacent = (
    (1, 3),
    (0, 2, 4),
    (1, 5),
    (0, 4, 6),
    (1, 3, 5, 7),
    (2, 4, 8),
    (3, 7),
    (4, 6, 8),
    (5, 7)
)

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

def main():
    if start == goal:
        return 0

    queue = [State(start[:], start.index(0), 0)]
    stateList = {"".join(map(str, start)) : True}

    while len(queue) != 0:
        state = queue.pop(0)
        for i in adjacent[state.space]:
            next_state = State(state.board[:], i, state.path + 1)
            next_state.board[i], next_state.board[state.space] = next_state.board[state.space], next_state.board[i]
            state_str = "".join(map(str, next_state.board))
            if stateList.get(state_str) :
                continue
            stateList[state_str] = True
            if next_state.board == goal:
                return next_state.path
            queue.append(next_state)

if __name__ == '__main__':
    result = main()
    print(result)

Submission status: Accepted

Solution code:
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
t = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]


def get_heuri():
    res = 0
    for i in range(3):
        for j in range(3):
            if t[i][j] == 0:
                continue
            a = t[i][j] - 1
            res += abs(a // 3 - i) + abs(a % 3 - j)
    return res


def check(depth, prev, py, px, limit):
    heuri = get_heuri()
    if heuri + depth > limit:
        return False
    if heuri == 0:
        return True
    for i in range(4):
        if abs(i - prev) == 2:
            continue
        ny = py + dy[i]
        nx = px + dx[i]
        if ny < 0 or nx < 0 or ny >= 3 or nx >= 3:
            continue
        t[ny][nx], t[py][px] = t[py][px], t[ny][nx]
        if check(depth + 1, i, ny, nx, limit):
            return True
        t[ny][nx], t[py][px] = t[py][px], t[ny][nx]
    return False

for i in range(3):
    s = list(map(int, input().split()))
    for j in range(3):
        if s[j] == 0:
            py = i
            px = j
        t[i][j] = s[j]
limit = 0
while True:
    if check(0, 99, py, px, limit):
        print(limit)
        break
    limit += 1

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef char Board[10];
Board ini_board, board;
const Board target = "123456780";

Board *history;
int nhistories=0;

typedef enum { U, D, L, R } Direction;

typedef struct {
  int pos;
  Direction dir;
} Motion;

int minstep = INT_MAX;

const Motion candidate[9][5] =
  {{{1,L},{3,U},{-1}}, {{0,R},{2,L},{4,U},{-1}}, {{1,R},{5,U},{-1}},
   {{0,D},{4,L},{6,U},{-1}}, {{1,D},{5,L},{7,U},{3,R},{-1}},
   {{2,D},{8,U},{4,R},{-1}},
   {{3,D},{7,L},{-1}}, {{4,D},{8,L},{6,R},{-1}}, {{5,D},{7,R},{-1}}  };

int move(Motion m)
{
  if (m.pos==0 && board[0]=='1') return -1;
  if ((m.pos==1||m.pos==2) && board[0]=='1'&&board[1]=='2'&&board[2]=='3') return -1;

  switch (m.dir) {
  case U:
    if (m.pos<3) return -1;
    
    board[m.pos-3] = board[m.pos];
    break;
  case D:
    if (m.pos>5) return -1;

    board[m.pos+3] = board[m.pos];
    break;
  case L:
    if (m.pos%3==0) return -1;

    board[m.pos-1] = board[m.pos];
    break;
  case R:
    if (m.pos%3==2) return -1;

    board[m.pos+1] = board[m.pos];
    break;
  }
  board[m.pos] = '0';
  return m.pos;
}

void search_path(int step, int space)
{
  int i, j;
  if (strcmp(board, "123456780")==0) {
    //    printf("STEP=%d\n", step);
    if (step==1) {
      printf("1\n");
      exit(0);
    }
    if (step<minstep) minstep=step;
    
  } else {

    int s2;
    if (step>=minstep) return;
    if (step>0 && strcmp(board, ini_board)==0) return;
    
    Board board_bak;
    strcpy(board_bak, board);
    int nhistories_bak=nhistories;
    
    for (i=0; candidate[space][i].pos>=0; i++) {

      if ((s2 = move(candidate[space][i]))<0) continue;
      for (j=0; j<nhistories; j++) {
	if (strcmp(board, history[j])==0)
	  break;
      }
      if (j==nhistories) {
	strcpy(history[nhistories++], board); 
	search_path(step+1, s2);
      }
      nhistories = nhistories_bak;
      strcpy(board, board_bak);
    }
  }
}

int main()
{
  fscanf(stdin, "%c %c %c\n", &board[0],&board[1],&board[2]);
  fscanf(stdin, "%c %c %c\n", &board[3],&board[4],&board[5]);
  fscanf(stdin, "%c %c %c\n", &board[6],&board[7],&board[8]);
  strcpy(ini_board, board);
  int space = strchr(board, '0')-board;
  
  history = (Board*)malloc(sizeof(Board)*100000);
  search_path(0, space);
  printf("%d\n", minstep);
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef char Board[10];
Board ini_board, board;
const Board target = "123456780";

Board *history;
int nhistories=0;

typedef enum { U, D, L, R } Direction;

typedef struct {
  int pos;
  Direction dir;
} Motion;

int minstep = 50;

const Motion candidate[9][5] =
  {{{1,L},{3,U},{-1}}, {{0,R},{2,L},{4,U},{-1}}, {{1,R},{5,U},{-1}},
   {{0,D},{4,L},{6,U},{-1}}, {{1,D},{5,L},{7,U},{3,R},{-1}},
   {{2,D},{8,U},{4,R},{-1}},
   {{3,D},{7,L},{-1}}, {{4,D},{8,L},{6,R},{-1}}, {{5,D},{7,R},{-1}}  };

int move(Motion m)
{
  if (m.pos==0 && board[0]=='1') return -1;
  if ((m.pos==1||m.pos==2) && board[0]=='1'&&board[1]=='2'&&board[2]=='3') return -1;

  switch (m.dir) {
  case U:
    if (m.pos<3) return -1;
    board[m.pos-3] = board[m.pos];
    break;
  case D:
    if (m.pos>5) return -1;
    board[m.pos+3] = board[m.pos];
    break;
  case L:
    if (m.pos%3==0) return -1;
    board[m.pos-1] = board[m.pos];
    break;
  case R:
    if (m.pos%3==2) return -1;
    board[m.pos+1] = board[m.pos];
    break;
  }
  board[m.pos] = '0';
  return m.pos;
}

void search_path(int step, int space)
{
  int i, j, s2;
  if (strcmp(board, "123456780")==0) {
    if (step==1) {
      printf("1\n");
      exit(0);
    }
    if (step<minstep) minstep=step;
  } else {
    if (step>=minstep) return;
    if (step>0 && strcmp(board, ini_board)==0) return;
    
    Board board_bak;
    strcpy(board_bak, board);
    int nhistories_bak=nhistories;

    for (i=0; candidate[space][i].pos>=0; i++) {
      if ((s2 = move(candidate[space][i]))<0) continue;
      for (j=0; j<nhistories; j++) {
	if (strcmp(board, history[j])==0) // 前と同じ配置になったので次の手を試す
	  break;
      }
      if (j==nhistories) {
	strcpy(history[nhistories++], board); 
	search_path(step+1, s2);
      }
      nhistories = nhistories_bak;
      strcpy(board, board_bak);
    }
  }
}

int main()
{
  fscanf(stdin, "%c %c %c\n", &board[0],&board[1],&board[2]);
  fscanf(stdin, "%c %c %c\n", &board[3],&board[4],&board[5]);
  fscanf(stdin, "%c %c %c\n", &board[6],&board[7],&board[8]);
  strcpy(ini_board, board);
  history = (Board*)malloc(sizeof(Board)*10000);
  search_path(0, strchr(board, '0')-board);
  printf("%d\n", minstep);
  return 0;
}

Submission status: Runtime Error

Solution code:
import sys
import queue

N = 3
f= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = queue.Queue()
V = dict()

Q.put([f,f.index('0'),0])
V[f] = True

while not Q.empty():
    u = Q.get()
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
	if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1 # dir[r]                                                       
            Q.put(v)

print(u[2])

Submission status: Runtime Error

Solution code:
import sys
import queue

N = 3
f= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = queue.Queue()
V = dict()

Q.put([f,f.index('0'),0])
V[f] = True

while not Q.empty():
    u = Q.get()
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
	if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1 # dir[r]                                                       
            Q.put(v)

print(u[2])

Submission status: Runtime Error

Solution code:
#include <stdlib.h>
#include <string.h>

typedef char Board[10];
Board ini_board, board, *history;
const Board target = "123456780";
int nhistories=0;

typedef enum { U, D, L, R } Direction;

typedef struct {
  char pos;
  char dir;
} Motion;

int minstep;

const Motion motion[9][5] =
  {{{1,L},{3,U},{-1}}, {{0,R},{2,L},{4,U},{-1}}, {{1,R},{5,U},{-1}},
   {{0,D},{4,L},{6,U},{-1}}, {{1,D},{5,L},{7,U},{3,R},{-1}},
   {{2,D},{8,U},{4,R},{-1}},
   {{3,D},{7,L},{-1}}, {{4,D},{8,L},{6,R},{-1}}, {{5,D},{7,R},{-1}}  };

int search_path(int step, char space)
{
  int i, j;
  if (strcmp(board, "123456780")==0) {
    //    printf("STEP=%d\n", step);                                                 
    //printf("%d\n", step);                                                          
    if (step<minstep) minstep=step;
    printf("%d\n", step);
    exit(0);
  } else {
    if (step>=minstep) return 1;
    if (step>0 && strcmp(board, ini_board)==0) return 1;

    Board board_bak;
    strcpy(board_bak, board);
    int nhistories_bak=nhistories;

   for (i=0; motion[space][i].pos>=0; i++) {
      Motion m = motion[space][i];

      if (m.pos==0 && board[0]=='1') continue;
      if ((m.pos==1||m.pos==2) && board[0]=='1'&&board[1]=='2'&&board[2]=='3') conti\
nue;
      if ((m.pos==3||m.pos==6) && board[0]=='1'&&board[3]=='4'&&board[6]=='7')contin\
ue;
      switch (m.dir) {
      case U:
        if (m.pos<3) continue;
        board[m.pos-3] = board[m.pos];
        break;
      case D:
        if (m.pos>5) continue;
        board[m.pos+3] = board[m.pos];
        break;
      case L:
        if (m.pos%3==0) continue;
        board[m.pos-1] = board[m.pos];
        break;
      case R:
        if (m.pos%3==2) continue;
        board[m.pos+1] = board[m.pos];
        break;
      }
      board[m.pos] = '0';

      for (j=0; j<nhistories; j++) {
        if (strcmp(board, history[j])==0)     break;
      }
      if (j==nhistories) {
        strcpy(history[nhistories++], board);
        search_path(step+1, m.pos);
      }
      nhistories = nhistories_bak;
      strcpy(board, board_bak);
    }
  }
  return 1;
}

int main()
{
  fscanf(stdin, "%c %c %c\n", &board[0],&board[1],&board[2]);
  fscanf(stdin, "%c %c %c\n", &board[3],&board[4],&board[5]);
  fscanf(stdin, "%c %c %c\n", &board[6],&board[7],&board[8]);
  strcpy(ini_board, board);
  for (minstep=1; minstep<32; minstep++) {
    strcpy(board, ini_board);
    history = (Board*)malloc(sizeof(Board)*100000);
    search_path(0, strchr(board, '0')-board);
    free(history);
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char Board[10];
Board ini_board, board, *history;
const Board target = "123456780";
int nhistories=0;

typedef enum { U, D, L, R } Direction;

typedef struct {
  char pos;
  char dir;
} Motion;

int minstep;

const Motion motion[9][5] =
  {{{1,L},{3,U},{-1}}, {{0,R},{2,L},{4,U},{-1}}, {{1,R},{5,U},{-1}},
   {{0,D},{4,L},{6,U},{-1}}, {{1,D},{5,L},{7,U},{3,R},{-1}},
   {{2,D},{8,U},{4,R},{-1}},
   {{3,D},{7,L},{-1}}, {{4,D},{8,L},{6,R},{-1}}, {{5,D},{7,R},{-1}}  };

int search_path(int step, char space)
{
  int i, j;
  if (strcmp(board, "123456780")==0) {
    //    printf("STEP=%d\n", step);                                                 
    //printf("%d\n", step);                                                          
    if (step<minstep) minstep=step;
    printf("%d\n", step);
    exit(0);
  } else {
    if (step>=minstep) return 1;
    if (step>0 && strcmp(board, ini_board)==0) return 1;

    Board board_bak;
    strcpy(board_bak, board);
    int nhistories_bak=nhistories;

   for (i=0; motion[space][i].pos>=0; i++) {
      Motion m = motion[space][i];

      if (m.pos==0 && board[0]=='1') continue;
      if ((m.pos==1||m.pos==2) && board[0]=='1'&&board[1]=='2'&&board[2]=='3') conti\
nue;
      if ((m.pos==3||m.pos==6) && board[0]=='1'&&board[3]=='4'&&board[6]=='7')contin\
ue;
      switch (m.dir) {
      case U:
        if (m.pos<3) continue;
        board[m.pos-3] = board[m.pos];
        break;
      case D:
        if (m.pos>5) continue;
        board[m.pos+3] = board[m.pos];
        break;
      case L:
        if (m.pos%3==0) continue;
        board[m.pos-1] = board[m.pos];
        break;
      case R:
        if (m.pos%3==2) continue;
        board[m.pos+1] = board[m.pos];
        break;
      }
      board[m.pos] = '0';

      for (j=0; j<nhistories; j++) {
        if (strcmp(board, history[j])==0)     break;
      }
      if (j==nhistories) {
        strcpy(history[nhistories++], board);
        search_path(step+1, m.pos);
      }
      nhistories = nhistories_bak;
      strcpy(board, board_bak);
    }
  }
  return 1;
}

int main()
{
  fscanf(stdin, "%c %c %c\n", &board[0],&board[1],&board[2]);
  fscanf(stdin, "%c %c %c\n", &board[3],&board[4],&board[5]);
  fscanf(stdin, "%c %c %c\n", &board[6],&board[7],&board[8]);
  strcpy(ini_board, board);
  for (minstep=1; minstep<32; minstep++) {
    strcpy(board, ini_board);
    history = (Board*)malloc(sizeof(Board)*100000);
    search_path(0, strchr(board, '0')-board);
    free(history);
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  unsigned int b;
  char step;
} Board;

int qlen=32202;

typedef enum { U, D, L, R } Direction;

typedef struct {
  int pos;
  Direction dir;
} Motion;

const Motion motion[9][5] =
  {{{1,L},{3,U},{-1}}, {{0,R},{2,L},{4,U},{-1}}, {{1,R},{5,U},{-1}},
   {{0,D},{4,L},{6,U},{-1}}, {{1,D},{5,L},{7,U},{3,R},{-1}},
   {{2,D},{8,U},{4,R},{-1}},
   {{3,D},{7,L},{-1}}, {{4,D},{8,L},{6,R},{-1}}, {{5,D},{7,R},{-1}} };

int findzero(unsigned int b)
{
  for (int i=0; i<9; i++) {
    if (b%10==0) return 8-i;
    b/=10;
  }
  return -1;
}

unsigned int sq[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,1000000000 };

#define HISTLEN 8765432

int main()
{
  int i, j, k;
  int qhead, qtail;
  qhead = qtail = 0;
  Board board;
  fscanf(stdin, "%d %d %d\n", &i, &j, &k);
  board.b = i*sq[8]+j*sq[7]+k*sq[6];
  fscanf(stdin, "%d %d %d\n", &i, &j, &k);
  board.b += i*sq[5]+j*sq[4]+k*sq[3];
  fscanf(stdin, "%d %d %d\n", &i, &j, &k);
  board.b += i*100+j*10+k;
  short int *used = (short int*)malloc(sizeof(short int)*HISTLEN);
  for (i=0; i<HISTLEN; i++) used[i]=0;
  Board *Q = (Board*)malloc(sizeof(Board)*qlen);
  board.step=0;
  Q[qhead++] = board;
  
  while (qhead>qtail) {
    board = Q[qtail++ %qlen];
    if (board.b==123456780)   break;
    
    int space = findzero(board.b);
    for (i=0; motion[space][i].pos>=0; i++) {
      Board b = board;
      Motion m = motion[space][i];
      if (m.pos==0 && b.b/sq[8]==1) continue;
      if ((m.pos==1||m.pos==2) && b.b/sq[8]==1&&(b.b%sq[8])/sq[7]==2&&(b.b%sq[7])/sq[6]==3) continue;
      int nn=b.b%sq[8-m.pos+1]/sq[8-m.pos];
      b.b = nn*sq[8-space]+b.b-nn*sq[8-m.pos];
      b.step = board.step+1;
      k=b.b/100;
      if ((used[k] & (1<<(b.b%10)))==(1<<(b.b%10))) continue;
      used[k] |= (1<<(board.b%10));
      Q[qhead++ %qlen] = b;
    }
  }
  printf("%d\n", board.step);
  return 0;
}

Submission status: Runtime Error

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 = str(board0).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: Runtime Error

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x_goal = i%3
        y_goal = i//3
        x_now = (node_list[i] - 1)%3
        y_now = (node_list[i] - 1)//3
        if y_now == -1:
            y_now = 2
        dx = abs(x_now - x_goal)
        dy = abs(y_now - y_goal)
        s += dx + dy
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 3] = node_tmp[space - 3], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 3] = node_tmp[space + 3], node_tmp[space]
    return node_tmp

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

    def makeBoard(self):
        space = self.space
        cost_now = self.f
        x_s = space%3
        y_s = space//3
        if x_s < 2:
            node_tmp = moveNodeE(self.node, space)
            yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s < 2:
            node_tmp = moveNodeS(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
n_goal = [1,2,3,4,5,6,7,8,0]
n_start = []

for i in range(3):
    inp = list(map(int, raw_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:
from collections import deque
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def MAIN():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    start = 8 - MAP.find("0")
    MAP = int(MAP)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    goal = 123456780
    dp = deque([(0, start, MAP)])
    LOG = {MAP}
    while dp:
        cnt, yx, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                dp.append((cnt, nyx, CM))
                LOG.add(CM)
MAIN()