#include #include #include 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; } }