#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[6][6];
/*   unsigned short backup[5][5]; */
   unsigned short hj[36];
   unsigned short hi[36];
   unsigned short opt[6];
   unsigned int mini = 999999;
   unsigned int cost, cost0;
   unsigned long long kount = 0;

   D = 6;                 /* 6x6 */
   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));

   for (i=0; i<=L; i++){
      for (j=0; j<=L; j++){
	 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;
      rr = opt[(int) ( drand48() * k )];
      switch (rr){ 
       case (0): 
	 ant = map[i][j-1];
	 map[i][j-1] = 0; 
	 map[i][j] = ant;
	 hj[0]--;
	 hj[ant]++;
	 break;
       case (1): 
	 ant = map[i-1][j];
	 map[i-1][j]=0; 
	 map[i][j] = ant;
	 hi[0]--;
	 hi[ant]++;
	 break;
       case (2): 
	 ant = map[i][j+1];
	 map[i][j+1] = 0; 
	 map[i][j] = ant;
	 hj[0]++; 
	 hj[ant]--;
	 break;
       case (3): 
	 ant = map[i+1][j];
	 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++){
	 cost0 = 0;
	 for (j=0; j<=L; j++){
	    cost0  += abs(map[i][j]-k); /* *(k+1); */  /* weighted walk distance */
	    if (j == col && map[i][j] == k) okcol++; 
	    k++; 
	  }
	 cost += cost0;
	 if (cost0 == 0 && i==linea && linea>1) linea--;
      }
      if (okcol == D && col > 1) col--;
      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++){ 
	       if (cost < mini)
		 printf("%02u ", map[i][j]);
/*	       backup[i][j] = map[i][j];     */
	    }
	    if (cost < mini)
	      printf("\n");
	 }
	 if (cost < mini){ 
	    printf("\n"); 
	    mini = cost;
	 }
	 if (cost == 2) kount += 100000000;
      }
/*      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 > 50000000000){
	 printf("Problem without solution!\n");
	 return 2;
      }
      if (cost == 0) return 0; 
   }
}