Knight's TourTake a chess knight around an empty board landing on every square once only. I wrote this while at Nescot studying for my HND. I had a friend run it on a 16 processor Sun machine overnight and it had done the job by the morning. Spot the goto. |
// © Rob Geleit March 1998 #include <stdio.h> #include <time.h> #include <stdlib.h> typedef enum {FALSE,TRUE} boolean; struct position { int x; int y; }; struct position moves_rel[8]; struct position legal_moves_abs[8]; int board[8][8]; int max=0; void randomise(void); int random(int); void init_arrays(void); void display_board(void); void move_to(struct position,int); void main(void) { struct position initial; /* randomise(); */ init_arrays(); initial.x=random(8); initial.y=random(8); printf("Start at %d,%d\n\n",initial.x,initial.y); move_to(initial,1); display_board(); } void init_arrays(void) { int i,j; int x[8]={1,2,2,1,-1,-2,-2,-1}; int y[8]={2,1,-1,-2,-2,-1,1,2}; /* Set up relative moves array */ for(i=0;i<8;i++) { moves_rel[i].x=x[i]; moves_rel[i].y=y[i]; } /* Clear board */ for(i=0;i<8;i++) for(j=0;j<8;j++) board[i][j]=0; } void display_board(void) { int i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) printf("%2d ",board[i][j]); printf("\n\n"); } } void move_to(struct position current_pos_abs,int this_move_no) { int i,j; static boolean complete=FALSE; boolean recurred; int no_legal_moves=0; struct position this_move_abs; board[current_pos_abs.x][current_pos_abs.y]=this_move_no; if(this_move_no==64) complete=TRUE; for(i=0;i<8;i++) { this_move_abs.x=current_pos_abs.x+moves_rel[i].x; this_move_abs.y=current_pos_abs.y+moves_rel[i].y; if(this_move_abs.x>=0 && this_move_abs.x<8 && this_move_abs.y>=0 && this_move_abs.y<8 && board[this_move_abs.x][this_move_abs.y]==0) { legal_moves_abs[no_legal_moves].x=this_move_abs.x; legal_moves_abs[no_legal_moves].y=this_move_abs.y; no_legal_moves++; } } resume: recurred=FALSE; if(no_legal_moves>0) { recurred=TRUE; i=0;/*random(no_legal_moves);*/ this_move_abs.x=legal_moves_abs[i].x; this_move_abs.y=legal_moves_abs[i].y; if(board[this_move_abs.x][this_move_abs.y]!=0)printf("plop"); /* remove from list */ for(j=i;j<no_legal_moves;j++) { legal_moves_abs[j].x=legal_moves_abs[j+1].x; legal_moves_abs[j].y=legal_moves_abs[j+1].y; } no_legal_moves--; move_to(this_move_abs,this_move_no+1); } if(complete==TRUE) return; if(recurred==FALSE) return; board[this_move_abs.x][this_move_abs.y]=0; if(no_legal_moves>0) goto resume; } void randomise(void) { time_t seed; srand((unsigned)time(&seed)); } int random(int upper) {return(abs(rand()%upper));}