kts.c (1634B)
1 /* See LICENSE file for copyright and license details. 2 * 3 * Knight's tour solver. 4 */ 5 6 #include <stdio.h> 7 #include <stdlib.h> 8 #include <time.h> 9 10 #define MOVEOK(X, Y) ((X) >= 0 && (X) < 8 && (Y) >= 0 && (Y) < 8 && !board[(X)][(Y)]) 11 #define RAND(N) (rand() / (RAND_MAX / N + 1)) 12 13 /* function declarations */ 14 void nextmove(int *p); 15 int acc(int x, int y); 16 void show(void); 17 18 /* globals */ 19 int pos[2]; 20 int board[8][8]; 21 int moves[8][2] = { 22 /* x, y */ 23 { -2, -1 }, 24 { 2, -1 }, 25 { -1, -2 }, 26 { 1, -2 }, 27 { -2, 1 }, 28 { 2, 1 }, 29 { -1, 2 }, 30 { 1, 2 } 31 }; 32 33 /* function implementations */ 34 int 35 main(void) { 36 int c, x, y, p[2]; 37 38 srand((unsigned int)time(NULL)); 39 x = pos[0] = RAND(8); 40 y = pos[1] = RAND(8); 41 board[x][y] = -1; 42 for(c = 2; c <= 64; ++c) { 43 nextmove(p); 44 x = pos[0] = p[0]; 45 y = pos[1] = p[1]; 46 board[x][y] = c; 47 } 48 show(); 49 return 0; 50 } 51 52 void 53 nextmove(int *p) { 54 int i, x, y, a, ma = 9; 55 56 for(i = 0; i < 8; ++i) { 57 x = pos[0] + moves[i][0]; 58 y = pos[1] + moves[i][1]; 59 if(MOVEOK(x, y) && (a = acc(x, y)) < ma) { 60 ma = a; 61 p[0] = x; 62 p[1] = y; 63 } 64 } 65 } 66 67 int 68 acc(int x, int y) { 69 int i, a; 70 71 for(a = i = 0; i < 8; ++i) 72 if(MOVEOK(x + moves[i][0], y + moves[i][1])) 73 ++a; 74 return a; 75 } 76 77 void 78 show(void) { 79 int x, y; 80 81 printf("%2c", ' '); 82 for(x = 0; x < 8; ++x) 83 printf("%4c", 'a' + x); 84 printf("\n"); 85 for(x = 0; x < 8; ++x) { 86 printf("\n%2d", x); 87 for(y = 0; y < 8; ++y) { 88 if(board[x][y] == -1) 89 printf("%2cS♞", ' '); 90 else if(board[x][y]) 91 if(x == y && x == 7) 92 printf("%2cE♞", ' '); 93 else 94 printf("%4.2d", board[x][y]); 95 else 96 printf("%4c", '.'); 97 } 98 printf("\n"); 99 } 100 }