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

int main(int argc, char *argv[]) 
{
   unsigned short D, L, k, ant, j, i, linea, col, rr, ok, okcol;
   unsigned short map[10][10];
   unsigned short backup[10][10]; 
   unsigned short hj[100];
   unsigned short hi[100];
   unsigned short tabu[10][10];
   unsigned short opt[10];
   unsigned int mini = 999999;
   unsigned int cost, cost0;
   unsigned long long kount = 0;

   D = 10;                 /* 10x10 */
   L = D -1;
   k = D*D;
   for (i = 0; i<=L; i++){
      for (j = 0; j<=L; j++){
	 k--;
	 hj[k] = j;
	 hi[k] = i;
	 map[i][j] = k;
      }
   }
   linea = L;
   col  = L;
   srand48(time(NULL));

   rr=0;
   for (i=0; i<=L; i++){
      for (j=0; j<=L; j++){
	 tabu[i][j]=rr;
	 rr++;
	 ant = map[i][j];
	 k = (int) (drand48() * D);
	 ok = (int) (drand48() * D);
	 map[i][j] = map[k][ok];
	 map[k][ok] = ant;
	 hi[map[k][ok]] = k;
	 hj[map[k][ok]] = ok;
	 hi[map[i][j]] = i;
	 hj[map[i][j]] = j;
      }
   }
   
   while (1){
      k = 0;   
      j = hj[0];
      i = hi[0];
      if (j-1 >= 0) opt[k++]=0;
      if (i-1 >= 0) opt[k++]=1;
      if (j+1 <= col) opt[k++]=2;
      if (i+1 <= linea) opt[k++]=3;
/* repeat: */
      rr = opt[(int) ( drand48() * k )];
      switch (rr){ 
       case (0):
	 ant = map[i][j-1];
/*	 if (ant == tabu[i][j-1] && (i==linea || j-1 == col)) goto repeat; */
	 map[i][j-1] = 0; 
	 map[i][j] = ant;
	 hj[0]--;
	 hj[ant]++;
	 break;
       case (1): 
	 ant = map[i-1][j];
/*	 if (ant == tabu[i-1][j] && (i-1==linea || j == col)) goto repeat; */
	 map[i-1][j]=0; 
	 map[i][j] = ant;
	 hi[0]--;
	 hi[ant]++;
	 break;
       case (2): 
	 ant = map[i][j+1];
/*	 if (ant == tabu[i][j+1] && (i==linea || j+1 == col)) goto repeat;  honey traps in corners */
	 map[i][j+1] = 0; 
	 map[i][j] = ant;
	 hj[0]++; 
	 hj[ant]--;
	 break;
       case (3): 
	 ant = map[i+1][j];
/*	 if (ant == tabu[i+1][j] && (i+1==linea || j == col)) goto repeat;  same problem */ 
	 map[i+1][j] = 0; 
	 map[i][j] = ant;
	 hi[0]++;
	 hi[ant]--;
	 break;
       default:
	 printf("ERROR GORDO\n");
	 return 1;
      }
      cost = 0;
      k = 0;
      okcol = 0;
/*      for (i=0; i<=L; i++){ */  
/*      i= linea; */
      for (i=linea-1; i<=linea; i++)
	{	   
	 cost0 = 0;
	 for (j=0; j<=L; j++){
	    if ( /* j== col */ i==0 || i== linea ) {		 
	       cost0 += (unsigned int) abs( (int)map[i][j]-(int)tabu[i][j] ); /* *(k+1); */  /* weighted walk distance */
	       if (j == col && map[i][j] == tabu[i][j]) okcol++; 
	    }
/*	    k++;  */
	 }
	 cost += cost0;
	 if (cost == 0 && i==linea && linea>1){ linea--; mini = 999999; } /* cost0 or cost */
      }  
      if (okcol == 2 && col > 1 && linea==1){ col--; mini=999999; }     /* only */
/*      if (cost <= mini){ */
	 /* kount = 0; */ 
      if (cost <= mini){
	 printf("COST = %u\n", cost);
	 for (i=0; i<=L; i++){ 
	    for (j=0; j<=L; j++){ 
	       printf("%02u ", map[i][j]);
	       backup[i][j] = map[i][j];  
	    }
	    printf("\n");
	 } 
	 printf("lines=%d cols=%d\n\n",linea,col); 
	 if (cost>0)
	   {
	      mini = cost;
	   }
      }
      if (cost == 2 && linea==1 && col<=1) kount += 1000000;
      else if (++kount % 1000 ==0){ 
	 for (i=0; i<=L; i++){ 
	    for (j=0; j<=L; j++){
	       map[i][j] = backup[i][j];
	       hi[map[i][j]] = i;
	       hj[map[i][j]] = j;
	    }
	 }
      }      
      if ( /* cost == 2 && */ kount > 1000000000000){
	 printf("Problem without solution!\n");
	 return 2;
      }
      if (cost == 0 && linea==1 && col==1) return 0; 
   }
}