#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
using namespace std;

const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

struct Stat{
    int a[9];

    int zeropos() const{
        for(int i=0;i<9;i++) if(a[i]==0) return i;
    }
    int h() const {
        int ret = 0;
        for(int i=0;i<9;i++) {
            int x = i/3;
            int y = i%3;
            int ox = a[i]/3;
            int oy = a[i]%3;
            ret +=  abs(x-ox) + abs(y-oy);
        }
        return ret;
    }

    bool canmakemove(int dir) const{
        int zp = zeropos();
        int x = zp/3;
        int y = zp%3;
        x+=dx[dir];
        y+=dy[dir];
        return x>=0 && x<3 && y>=0 && y<3;
    }
    Stat makemove(int dir) const{
        int zp = zeropos();
        int x = zp/3;
        int y = zp%3;
        x+=dx[dir];
        y+=dy[dir];
        Stat ret;
        for(int i=0;i<9;i++) ret.a[i]=a[i];
        swap(ret.a[zp],ret.a[x*3+y]);
        return ret;
    }
    bool operator<(const Stat &b) const {
        for(int i=0;i<9;i++) if(a[i]!=b.a[i]) return a[i]<b.a[i];
        return false;
    }
    void print() {
        printf("[");
        for(int i=0;i<9;i++) printf(" %d",a[i]);
        printf("]\n");
    }
};

typedef pair<int,Stat>  PIS;


priority_queue<PIS,vector<PIS>,greater<PIS> > pq;
map<Stat,int> mp;


int astar(Stat start){
    while(!pq.empty()) pq.pop();
    mp.clear();
    pq.push(PIS(start.h(),start));
    mp[start]=0;
    while(!pq.empty()){
        PIS pis = pq.top();
        pq.pop();
        Stat s = pis.second;
        if(s.h()==0) {
            return mp[s];
        }

        //s.print();
        //printf("%d\n",mp[s]);
        for(int i=0;i<4;i++) if(s.canmakemove(i)){
            Stat ns = s.makemove(i);
            if((mp.find(ns)== mp.end()) || mp[s]+1<mp[ns]) {
                mp[ns]=mp[s]+1;
                pq.push(PIS(ns.h()+mp[ns],ns));
            }
        }
    }
    return 10000;
}

queue<Stat> q;
int countbfs(Stat s,int dep=27){
    while(!q.empty()) q.pop();
    q.push(s);
    mp.clear();
    mp[s]=0;
    int cnt=0;
    while(!q.empty()){
        Stat s= q.front();
        q.pop();
        for(int i=0;i<4;i++) if(s.canmakemove(i)){
            Stat ns = s.makemove(i);
            if((mp.find(ns)== mp.end())){
                mp[ns]=mp[s]+1;
                if(mp[ns]==dep) cnt++;
                if(mp[ns]>dep) return cnt;
                q.push(ns);
            }
        }
    }
    return cnt;
}

Stat start;



int main()
{
    cout<<"Input start state:  eg. [1 6 4 8 7 0 3 2 5] (without parentheses)"<<endl;
    for(int i=0;i<9;i++) cin>>start.a[i];

    //cout<<astar(start)<<endl;
    cout<<countbfs(start)<<endl;
    return 0;
}