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