#include <stdio.h>
#include <stdlib.h>

#define LENGTH    3			/* velikost hracího plánu */
#define SIZE      (LENGTH*LENGTH)

int count;				/* počet permutací kostiček */
char *find;				/* pole pro prohledávání do šířky -- viz text */

int perm2int(int *perm) {		/* převod permutace na číslo */
  int order[SIZE];
  int i,j,idx=0;
  for(i=0;i<SIZE;i++)			/* $i$. volné číslo je na pozici $i$ */
    order[i]=i;
  for(i=0;i<SIZE;i++) {			/* přidej další člen */
    idx=idx*(SIZE-i)+order[perm[i]];
    order[perm[i]]=-1;
    for(j=perm[i]+1;j<SIZE;j++)		/* sniž o 1 pořadí následujících cifer */
      order[j]--;
  }
  return idx;
}

void int2perm(int idx,int *perm) {	/* převod čísla na permutaci */
  int order[SIZE];
  int i,j,divide=count;
  for(i=0;i<SIZE;i++)			/* $i$. volné číslo je na pozici $i$ */
    order[i]=i;
  for(i=0;i<SIZE;i++) {
    divide /= SIZE-i;
    perm[i]=order[j=idx/divide];
    idx %= divide;
    for(j++;j<SIZE;j++)			/* na daném místě v pořadí budou vyšší cifry */
      order[j-1]=order[j];
  }
}

void init() {				/* alokace pole */
  int i;
  count=1;
  for(i=0;i<SIZE;i++)			/* celkový počet permutací */
    count *= i+1;
  if(!(find=(char*)calloc(count,1)))	/* alokovat paměť na permutace, vymazat ji */
    exit(1);				/* předpokládáme 32-bitový kompilátor */
  find[0]=1+4;				/* začínáme hledat z uspořádaného stavu */
}

void done() {				/* uvolnění paměti */
  free(find);
}

int move(int *perm,int vect) {		/* provede na permutaci daný tah 1--4 */
  int where,i;

  switch(vect) {
  case 1:				/* dolů */
    if(perm[SIZE-1]>=6) return 1;	/* kontrola: není díra ve spodní řadě? */
    else where=perm[SIZE-1]+3;
    break;
  case 2:				/* nahoru */
    if(perm[SIZE-1]<3) return 1;	/* kontrola: není díra v horní řadě? */
    else where=perm[SIZE-1]-3;
    break;
  case 3:				/* doprava */
    if(perm[SIZE-1]%3==2) return 1;	/* kontrola: není díra v pravém sloupci? */
    else where=perm[SIZE-1]+1;
    break;
  case 4:				/* doleva */
    if(perm[SIZE-1]%3==0) return 1;
    else where=perm[SIZE-1]-1;		/* kontrola: není díra v levém sloupci? */
    break;
  default:				/* chybný tah */
    return 2;
  }
  /* nyni prohodíme díru s danou kostičkou, číslo díry je 8,
  permutace obsahuje pro každou kostičku pozici, na níž je uložena */
  i=0;					/* najdeme, s čím to teda prohazujeme */
  while(i<SIZE && perm[i]!=where) i++;
  perm[i]=perm[8];			/* kostka je tam, kde byla díra */
  perm[8]=where;			/* díra je na novém místě */
  return 0;
}

void search() {
  int added,sum,level;			/* přidaných v posledním kole, celkem a hladina */
  int p[SIZE],r[SIZE];			/* pracovní permutace */
  int n;				/* číslo nové permutace */
  int i,j;

  level=0;
  added=sum=1;
  while(added) {			/* dokud jsme posledně nalezli aspoň 1 tah */
    printf("%2d.level: added=%6d, all=%06d\n",level++,added,sum);
    added=0;				/* další kolo: */
    for(i=0;i<count;i++)		/* vyzkoušíme všechny permutace */
    if(find[i]>4 && find[i]<=8) {	/* ááá, tu jsme nalezli teprve minule */
      int2perm(i,p);
      for(j=1;j<=4;j++) {		/* zkusme postupně všechny tahy */
        memcpy(r,p,SIZE*sizeof(int));
        if(!move(r,j)) {		/* provedeme jej, testujeme, zda je tah korektní */
          n=perm2int(r);
          if(!find[n]) {		/* vede na ještě nezpracovanou pozici? */
            find[n]=j+8;		/* označíme na zpracování */
            added++;
          }
        }
      } /* tahy */
    } /* permutace */
    for(i=0;i<count;i++)		/* označit zpracované permutace */
      if(find[i]>4)			/* zpracována v tomto tahu nebo je nová? */
        find[i] -= 4;
    sum+=added;
  }
}

void animate(int nr) {			/* `animuje' ve zpětném průchodu nalezenou cestu */
  const char ch[SIZE+1] = {"12345678."}; /* výpis nalezé cesty */
  int p[SIZE],p1[SIZE];			/* permutace a její inverze */
  int i,j,level;
  if(!find[nr]) {			/* nevede-li tam cesta */
    printf("there's no way\n");
    return;
  }
  int2perm(nr,p);			/* hledáme zpětně z rozeskládané situace */
  level=0;
  do {
    getchar();
    printf("%2d. %6d\n\n",level++,nr);
    for(i=0;i<SIZE;i++)			/* inverzní permutace říká pro každou pozici, */
      p1[p[i]]=i;			/* co na ní je */
    for(i=0;i<LENGTH;i++) {
      for(j=0;j<LENGTH;j++)
        printf("%c ",ch[p1[i*LENGTH+j]]);
      printf("\n");
    }
    if(!nr)				/* už jsme to poskládali? */
      break;
    printf("\nmoving %d\n",find[nr]);
    /* odkud jsme sem došli? potřebujeme provést opačný pohyb,
    což nejlépe uděláme negací $0$. bitu, \hfil\break ale po odečtení 1 */
    i=((find[nr]-1)^1)+1;
    move(p,i);
    nr=perm2int(p);
  }while(1);
}

int main() {
  int i;
  init();
  search();
  do {
    printf("perm? "); scanf("%d",&i);
    animate(i);
  } while(i);
  done();
  return 0;
}