Buggy python submission (verdict: Runtime Error):
#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;
}



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
#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;
}



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
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])



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
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])



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
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])


Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
#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;
}



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
#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;
}



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])

Buggy python submission (verdict: Runtime Error):
#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;
}



Fixed submission:
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 = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    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.append(v)

print(u[2])