/* knight.c: knight's tour of a chess board. */ /* Takes about an hour to find the 8 by 8 circuit. */ /* knight 8 8 - - */ #include #include #include #include static char circuit = 0; static char leftright = 0; static char width, height; static char x0, y0; // starrt position static char mx[200], my[200]; // knight moves static int level; static char board[16][8]; // this is only for the 8 by 8 board static char range[8][8] = { {2,3,4,4,4,4,3,2}, {3,4,7,7,7,7,4,3}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {4,6,8,8,8,8,6,4}, {3,4,7,7,7,7,4,3}, {2,3,4,4,4,4,3,2}, }; static void makemove(void) { int i, m; char lx, ly; // last xy position char nx, ny; // next xy position static const char jx[8] = {2,1,-1,-2,-2,-1,1,2}; static const char jy[8] = {1,2,2,1,-1,-2,-2,-1}; char cx[8], cy[8]; int choices, c1; if(level == width * height - 1) { for(i=0; i<=level; ++i) printf("%c%d ", "abcdefghijklmnop"[mx[i]], my[i]+1); printf("\n"); exit(0); return; } lx = mx[level], ly = my[level]; choices = 0, c1 = -1; for(m=0; m<8; ++m) { nx = lx + jx[m]; ny = ly + jy[m]; if(nx < 0 || nx >= width || ny < 0 || ny >= height) continue; if(board[nx][ny]) continue; if(height == 8 && width == 8 && range[nx][ny] == 1) { if(c1 >= 0) return; c1 = choices; } if(height == 4) { char gg = 0; if((ly == 1 || ly == 2) && (ny == 1 || ny == 2)) gg = 1; if(gg ^ (level == width*height/2-1)) continue; } cx[choices] = nx, cy[choices] = ny; ++choices; } if(!choices) return; if(c1 >= 0) cx[0] = cx[c1], cy[0] = cy[c1], choices = 1; ++level; if(width == 8 && height == 8) { for(m=0; m 16 || height <= 0 || height > 8) { fprintf(stderr, "width or height is out of range\n"); exit(1); } if(!strcmp(argv[3], "-") && !strcmp(argv[4], "-")) { x0 = y0 = 0; circuit = 1; if(width&height&1) { fprintf(stderr, "cannot have a circuit on an odd board\n"); exit(1); } } else if(!strcmp(argv[3], "-") && !strcmp(argv[4], "+")) { x0 = y0 = 0; leftright = 1; } else { x0 = atoi(argv[3]); y0 = atoi(argv[4]); if(x0 < 0 || x0 >= width || y0 < 0 || y0 >= height) { fprintf(stderr, " start point is out of range\n"); exit(1); } if(height == 4 && (y0 == 1 || y0 == 2)) exit(1); } mx[0] = x0, my[0] = y0, board[x0][y0] = 1; if(circuit) { mx[1] = 2, my[1] = 1, board[2][1] = 1; ++level; } makemove(); exit(1); }