#define ABS(x) (((x)<0)?-(x):(x))

int bittable1[84];
int bittable2[512];
int table[1680]; //84*20

int
countbits(int x) {
  int count=0, i;
  for(i=0;i<9;i++)
    if(1<<i & x)
      count++;
  return count;
}

int
pos2int(int *pos) {
  int i,j, color, posno=0;
  for(color=1;color<=2;color++) {
    j=0;
    for(i=8;i>=0;i--)
      j = (j<<(color==1||pos[i]!=1)) | (color==pos[i]);
    posno=posno*20+bittable2[j];
  }
  return posno;
}

void
int2pos(int posno, int *pos) {
  int i,j,k,m=0;
  j=posno/20;
  k=bittable1[j];
  for(i=0;i<9;i++) {
    pos[i]=((1<<i & k)!=0);
  }
  j=posno%20;
  k=bittable1[j];
  for(i=0;i<9;i++) {
    if(!pos[i]) {
      pos[i] = (((1<<m++)&k)!=0)*2;
    }
  }
}

void
printpos(int *pos) {
  int i;
  for(i=0;i<9;i++) {
    printf("%d", pos[i]);
    if(!((i+1)%3)) 
      printf("\n");
  }
  printf("\n");
}

int
move(int from, int num) {
  int i,n=0,board[9],r1,c1,r2,c2,dr,dc,count;
  int2pos(from,board);
  for(r1=0;r1<3;r1++)
    for(c1=0;c1<3;c1++) {
      count=0;
      for(dr= -1;dr<=1;dr++) 
	for(dc= -1;dc<=1;dc++) 
	  if(dc && dr != dc) {
	    r2=r1+dr;
	    c2=c1+dc;
	    if(r2>=0 && r2<=2 &&
	       c2>=0 && c2<=2 &&
	       board[r1*3+c1] &&
	       board[r1*3+c1] == board[r2*3+c2]) {
	      // count how many pieces we are next to at the required places
	      count++;
	    }
	  }
      if(!count) {
	continue;
      }
      for(r2=0;r2<3;r2++) 
	for(c2=0;c2<3;c2++) 
	  if(board[r1*3+c1] != 0 &&
	     board[r2*3+c2] == 0 &&
	     (ABS(r1-r2)<2&&ABS(c1-c2)<2)) {
	    board[r2*3+c2]=board[r1*3+c1];
	    board[r1*3+c1]=0;
	    if(num == n++) 
	      return pos2int(board);
	    int2pos(from,board);
	  }
    }
  return -1;
}

int end;
int start=19;
//int start=248; // this would be a harder start position

void
solve(int posno) {
  int i,j,k,board[9];
  for(i=0;i<1680;i++) 
    if(table[i]+1 == table[posno]) 
      for(j=0;;j++) {
	k=move(i,j);
	if(k<0) 
	  break;
	if(k==posno) {
	  solve(i);
	  int2pos(k,board);
	  printf("step %d\n", table[k]);
	  printpos(board);
	  return;
	}
      }
}

main() {
  int i,j=0,k,m,board[9],count,solved=0;
  for(i=0;i<512;i++)
    if(countbits(i) == 3) {
      //printf("%d\n", i);
      bittable1[j] = i;
      bittable2[i] = j++;
    }

  int2pos(start,board);
  for(i=0;i<9;i++)
    switch(board[i]) {
    case 1:
      board[i]=2;
      break;
    case 2:
      board[i]=1;
      break;
    }
  end=pos2int(board);
  solved=0;
  for(i=0;i<1680;i++)
    table[i]=(i==start)-1;
  count=1;
  for(j=0;count!=0;j++) {
    count=0;
    for(i=0;i<1680;i++)
      if(table[i]==j)
	for(k=0;;k++) {
	  if((m=move(i,k))<0)
	    break;
	  if(table[m]<0) {
	    table[m]=j+1;
	    count++;
	    if(m==end) {
	      printf("%d %d %d solution is %d steps\n",j+1, start, end, j+1);
	      solved=1;
	      if(j+1==21) {
		int2pos(start,board);
		printpos(board);
	      }
	    }
	  }
	}
    //printf("%d at depth %d\n", count, j);
  }
  solve(end);
}