training

Code I wrote during training
git clone git://git.bitsmanent.org/training
Log | Files | Refs | README

toth_d.c (2958B)

      1 /* Exercise 6.24 (d) */
      2 
      3 #include <stdio.h>
      4 
      5 #define BSIZE 8 /* board size */
      6 
      7 int main(void)
      8 {
      9    int board[BSIZE][BSIZE] = { { 0 } };
     10 			   /* 0   1   2   3   4   5  6  7 */
     11    int horizontal[BSIZE] = {  2,  1, -1, -2, -2, -1, 1, 2 };
     12    int vertical[BSIZE]   = { -1, -2, -2, -1,  1,  2, 2, 1 };
     13 
     14    /* Method "heuristic of accessibility" */
     15    int accessibility[BSIZE+1][BSIZE] = {
     16       { 2, 3, 4, 4, 4, 4, 3, 2 },
     17       { 3, 4, 6, 6, 6, 6, 4, 3 },
     18       { 4, 6, 8, 8, 8, 8, 6, 4 },
     19       { 4, 6, 8, 8, 8, 8, 6, 4 },
     20       { 4, 6, 8, 8, 8, 8, 6, 4 },
     21       { 4, 6, 8, 8, 8, 8, 6, 4 },
     22       { 3, 4, 6, 6, 6, 6, 4, 3 },
     23       { 2, 3, 4, 4, 4, 4, 3, 2 },
     24       { BSIZE } /* extra value */
     25    };
     26 
     27    int nr, nc; /* next position according with the "accessibility" matrix */
     28    int pass = 0; /* write permission checker :-) */
     29    int v1, v2, mn;
     30 
     31    int moveNumber = 0, i, r, c;
     32    int currentRow = 0, currentColumn = 0;
     33    board[currentRow][currentColumn] = -1; /* current position */
     34    /* current accessibility position */
     35    --accessibility[currentRow][currentColumn];
     36 
     37    for(i = 1; i <= BSIZE*BSIZE; i++) {
     38       nr = BSIZE;
     39       nc = 0;
     40       for(moveNumber = 0; moveNumber < BSIZE; moveNumber++) {
     41 
     42          /* read next potential position */
     43          r = currentRow + vertical[moveNumber];
     44          c = currentColumn + horizontal[moveNumber];
     45 
     46          /* it's not out of chessboard */
     47          if( (r >= 0 && r < BSIZE) && (c >= 0 && c < BSIZE) && !board[r][c] ) {
     48 	    pass = 1; /* write access granted :-) */
     49 
     50 	    /* check accessibility level */
     51 	    if(accessibility[r][c] < accessibility[nr][nc]) {
     52 	       nr = r;
     53 	       nc = c;
     54 	    }  
     55 	    else if(accessibility[r][c] == accessibility[nr][nc]) {
     56 	       /* check *one* sublevel (r, c) */
     57 	       for(mn = 0, v1 = BSIZE; mn < BSIZE; mn++) {
     58 		  if((accessibility[r+vertical[mn]][c+horizontal[mn]]<v1) &&
     59                   (r >= 0 && r < BSIZE) && (c >= 0 && c < BSIZE) &&
     60 		  !board[r][c])
     61 		     v1 = accessibility[r + vertical[mn]][c + horizontal[mn]];
     62 	       }
     63 
     64 	       /* check *one* sublevel (nr, nc) */
     65 	       for(mn = 0, v2 = BSIZE; mn < BSIZE; mn++) {
     66 		  if((accessibility[nr+vertical[mn]][nc+horizontal[mn]]<v2) &&
     67 		  (nr >= 0 && r < BSIZE) && (nc >= 0 && c < BSIZE) &&
     68 		  !board[nr][nc])
     69 		     v2 = accessibility[nr + vertical[mn]][nc + horizontal[mn]];
     70 	       }
     71 
     72 	       /* check'n set */
     73 	       if(v1 < v2) {
     74 		  nr = r;
     75 		  nc = c;
     76 	       }
     77 	    }
     78 	 } /* end if */
     79       } /* end for (moveNumber) */
     80 
     81       if(pass) {
     82 	 currentRow = nr;
     83 	 currentColumn = nc;
     84 	 --accessibility[nr][nc];
     85          board[currentRow][currentColumn] = i;
     86 	 pass = 0;
     87       }
     88       else /* stalled */
     89 	 break;
     90    } /* end for (i) */
     91 
     92    mn = 0;
     93    for(r = 0; r < BSIZE; r++) {
     94       for(c = 0; c < BSIZE; c++) {
     95 	 if(board[r][c]) {
     96 	    printf(" + ");
     97 	    ++mn;
     98 	 }
     99 	 else
    100 	    printf(" - ");
    101       }
    102       printf("\n");
    103    }
    104    printf("Moves: %d\n", mn);
    105 
    106    return 0;
    107 } /* E0F main */
    108