#include "iostream.h"

char config[362884][10];
int  lastconfig=0;

enum { UP=0, DOWN=1, LEFT=2, RIGHT=3 };

int indexhole (char* s) {
  for (int i=0;i<9;i++) {
    if (s[i]=='0') return(i);
  }
  return(-1);
}

int notnew (char* s) {
  for (int j=0; j<lastconfig; j++) {
    int ismatch=1;
    for (int i=0;i<9;i++) {
      if (s[i]!=config[j][i]) {
        ismatch=0;
        break;
      }
    }
    if (ismatch) return(1);
  }
  return(0);
}
       
int main() {
  // config[0]="123456780";  // THIS CAUSES ERROR FOR SOME COMPILERS, SO
  // THE FOLLOWING THREE LINES ARE A REPLACEMENT:
  for (int j=0; j<8; j++) config[0][j]='1'+j;
  config[0][8]='0';
  config[0][9]=0;

  int current=-1;
  
  while (current<lastconfig) {
    current++;

    // expand the current config
    int i=indexhole(config[current]);

    for (int move=UP; move<=RIGHT; move++) {
      int k=0;
      switch (move) {
        case UP:    if (i>2) k=-3;    break; // moving hole up is possible
        case DOWN:  if (i<6) k=3;     break; // moving hole down is possible
        case LEFT:  if (i%3) k=-1;    break; // moving hole left is possible
        case RIGHT: if (i%3 < 2) k=1; break; // moving hole right is possible
      };
      if (k) {
        lastconfig++;
        for (int j=0; j<9; j++) config[lastconfig][j]=config[current][j];
        config[lastconfig][i]=config[current][i+k];
        config[lastconfig][i+k]='0';
        if (notnew(config[lastconfig])) lastconfig--;
      }
    }
    if (lastconfig>362880) break;
    if (!(lastconfig%1000)) cout << lastconfig << "\n";
  }
  cout << "Number of reachable configurations: " << lastconfig+1 << "\n";
}