#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int checkTable[362880];

void setNUM(int table[3][3], long long x){
    int S = 100000000;
    for(int i=0;i<3;i++){
        for(int k=0;k<3;k++){
            table[i][k] = x/S;
            x = x%S;
            S /= 10;
        }
    }
}

int getNUM(int x){
    switch(x){
    case 0:return 1;
    case 1:return 1;
    case 2:return 2;
    case 3:return 6;
    case 4:return 24;
    case 5:return 120;
    case 6:return 720;
    case 7:return 5040;
    case 8:return 40320;
    }
    return -1;
}

long long makeLong(int Table[3][3]){
    return 100000000*Table[0][0]+10000000*Table[0][1]+1000000*Table[0][2]+
            100000*Table[1][0]+10000*Table[1][1]+1000*Table[1][2]+ 100*Table[2][0]+
            10*Table[2][1]+Table[2][2];
}

int translateORDER(int Table[3][3]){
    long long x = makeLong(Table);
    int checkTable[9] = {0};
    long long S = 100000000;
    int ret = 0,small_num_appear_count,limit;
    for(int i=8; i >= 0; i--){
        small_num_appear_count=0;
	limit = x/S;
        for(int k = 0; k < limit;k++){
            if(checkTable[k] == 1)small_num_appear_count++;
        }
        ret += ((x/S)-small_num_appear_count)*getNUM(i);
        checkTable[(x/S)]=1;
        x %= S;
        S /= 10;
    }

    return ret;
}


int zeroLoc(int table[3][3]){
    int zero_loc;
    for(int i=0;i<3;i++){
        for(int k=0;k<3;k++){
            if(table[i][k]==0){
                zero_loc=10*i+k;
            }
        }
    }
    return zero_loc;
}

struct Info{
    Info(){ zero_loc=data = count = 0;}
    Info(long long arg_data,int arg_count,short arg_loc){
        data = arg_data;
        count = arg_count;
        zero_loc = arg_loc;
    }
    long long data;
    int count;
    short zero_loc;
};

class LongQ{
public:
    LongQ(){
        Q = new Info[362880];
        head = tail = num_of_data=0;
    }

    void enqueue(long long arg_data,int arg_count,short arg_loc){
        Q[tail].count = arg_count;
        Q[tail].data = arg_data;
        Q[tail].zero_loc = arg_loc;
        num_of_data++;
        tail = (tail+1)%362880;
    }

    Info dequeue(){
        Info ret = Q[head];
        head = (head+1)%362880;
        num_of_data--;
        return ret;
    }

    bool isEmpty(){
        return num_of_data == 0;
    }

private:
    Info* Q;
    int head,tail,num_of_data;
};

LongQ func(LongQ queue,int table[3][3],Info tmpInfo,short zero_loc){
    if(checkTable[translateORDER(table)] == -1){
        checkTable[translateORDER(table)]=tmpInfo.count;
        queue.enqueue(makeLong(table),tmpInfo.count+1,zero_loc);
    }
    return queue;
}

int main(){

    for(int i = 0; i < 362880;i++)checkTable[i]=-1;

    int table[3][3];

    for(int i=0;i<3;i++){
        scanf("%d %d %d",&table[i][0],&table[i][1],&table[i][2]);
    }

    checkTable[translateORDER(table)]=0;
    LongQ queue;

    queue.enqueue(makeLong(table),0,zeroLoc(table));

    Info tmpInfo;

    while(queue.isEmpty()==false){
        tmpInfo=queue.dequeue();

        int tmpTable[3][3];
        setNUM(tmpTable,tmpInfo.data);
        if(tmpTable[0][0]==1&&tmpTable[0][1]==2&&tmpTable[0][2]==3&&tmpTable[1][0]==4&&
        		tmpTable[1][1]==5&&tmpTable[1][2]==6&&tmpTable[2][0]==7&&tmpTable[2][1]==8){
            printf("%d\n",tmpInfo.count);
            break;
        }

        int next_table[4][3][3];

        for(int a=0;a<4;a++){
            for(int b=0;b<3;b++){
                for(int c=0;c<3;c++){
                    next_table[a][b][c] = tmpTable[b][c];
                }
            }
        }

        switch(tmpInfo.zero_loc){
        case 0:
            swap(next_table[0][0][0],next_table[0][0][1]);
            queue = func(queue,next_table[0],tmpInfo,1);

            swap(next_table[1][0][0],next_table[1][1][0]);
            queue = func(queue,next_table[1],tmpInfo,10);
            break;
        case 1:
            swap(next_table[0][0][1],next_table[0][0][0]);
            queue = func(queue,next_table[0],tmpInfo,0);

            swap(next_table[1][0][1],next_table[1][0][2]);
            queue = func(queue,next_table[1],tmpInfo,2);

            swap(next_table[2][0][1],next_table[2][1][1]);
            queue = func(queue,next_table[2],tmpInfo,11);
            break;
        case 2:
            swap(next_table[0][0][2],next_table[0][0][1]);
            queue = func(queue,next_table[0],tmpInfo,1);

            swap(next_table[1][0][2],next_table[1][1][2]);
            queue = func(queue,next_table[1],tmpInfo,12);

            break;
        case 10:
            swap(next_table[0][1][0],next_table[0][0][0]);
            queue = func(queue,next_table[0],tmpInfo,0);

            swap(next_table[1][1][0],next_table[1][1][1]);
            queue = func(queue,next_table[1],tmpInfo,11);

            swap(next_table[2][1][0],next_table[2][2][0]);
            queue = func(queue,next_table[2],tmpInfo,20);

            break;
        case 11:
            swap(next_table[0][1][1],next_table[0][0][1]);
            queue = func(queue,next_table[0],tmpInfo,1);

            swap(next_table[1][1][1],next_table[1][1][0]);
            queue = func(queue,next_table[1],tmpInfo,10);

            swap(next_table[2][1][1],next_table[2][1][2]);
            queue = func(queue,next_table[2],tmpInfo,12);

            swap(next_table[3][1][1],next_table[3][2][1]);
            queue = func(queue,next_table[3],tmpInfo,21);
            break;
        case 12:
            swap(next_table[0][1][2],next_table[0][0][2]);
            queue = func(queue,next_table[0],tmpInfo,2);

            swap(next_table[1][1][2],next_table[1][1][1]);
            queue = func(queue,next_table[1],tmpInfo,11);

            swap(next_table[2][1][2],next_table[2][2][2]);
            queue = func(queue,next_table[2],tmpInfo,22);
            break;
        case 20:
            swap(next_table[0][2][0],next_table[0][1][0]);
            queue = func(queue,next_table[0],tmpInfo,10);

            swap(next_table[1][2][0],next_table[1][2][1]);
            queue = func(queue,next_table[1],tmpInfo,21);
            break;
        case 21:
            swap(next_table[0][2][1],next_table[0][2][0]);
            queue = func(queue,next_table[0],tmpInfo,20);

            swap(next_table[1][2][1],next_table[1][1][1]);
            queue = func(queue,next_table[1],tmpInfo,11);

            swap(next_table[2][2][1],next_table[2][2][2]);
            queue = func(queue,next_table[2],tmpInfo,22);
            break;
        case 22:
            swap(next_table[0][2][2],next_table[0][1][2]);
            queue = func(queue,next_table[0],tmpInfo,12);

            swap(next_table[1][2][2],next_table[1][2][1]);
            queue = func(queue,next_table[1],tmpInfo,21);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 10312