Hi all....
I've been makin the Knight's tour program...basically...it is finding the number of possible ways in which the knight in a chess board can move and fill all the spaces in the board without visiting the same space twice......well...I have used a two dimensional array to form the board used recursion to track every move.....according to my program...the knight tries all the possible moves...and recurses the move function......but for some erason, while using a 5X5 board, my moves dont go to more than 16 moves...and on a 8X8 board, the moves dont go further than 48 moves.......I just couldnt figure out why it is doing this....can somebody please help me with this!!!!
Here is a copy of my code:
Code:#include <iostream.h> #include <cctype> #include <cstdlib> //To Change the size of the board, Simply change this: const int max_num=8; const int dispnum=1;//change this to change num of free holes int numove=max_num*max_num; int mover=1; int count=0; int count1=0; struct chess { int board[9][9]; int x; int y; int move; }; void draw(chess board); bool movepossible(chess board); void moving(chess board); void main() { chess board; board.x=0; board.y=0; board.move=0; for (int i=0; i<max_num+1; i++) { for (int j=0; j<max_num; j++) board.board[i][j]=0; } //Test For Convergence board.board[0][0]=1; board.x=0; board.y=0; draw(board); moving(board); cout<<"Final Count is: "<<count<<endl; } void draw(chess board) { for (int i=0; i<max_num;i++) cout<<"-----"; cout<<endl; for (i=0; i<max_num; i++) { cout<<"|"; for (int j=0;j<max_num; j++) { cout<<" "; if (board.board[i][j] ==0) cout<<" "; else { cout<<board.board[i][j]; if (board.board[i][j]<10) cout<<" "; } cout<<" |"; } cout<<endl; for(int i=0; i<max_num; i++) cout<<"-----"; cout<<endl; } } void moving(chess board) { /* //USE THIS TO TRACK THE NUMBER MF MOVES if (mover>47) { draw(board); cout<<"MOVE NO: "<<mover<<endl; } */ //Case #1 if((board.x-2)>0 && (board.y+1)<max_num && board.board[board.x-2][board.y+1]==0) { board.x=board.x-2; board.y=board.y+1; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x+2; board.y=board.y-1; mover--; } //Case #2 if((board.x-1)>0 && (board.y+2)<max_num && board.board[board.x-1][board.y+2]==0) { board.x=board.x-1; board.y=board.y+2; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x+1; board.y=board.y-2; mover--; } //Case #3 if((board.x+1)<max_num && (board.y+2)<max_num && board.board[board.x+1][board.y+2]==0) { board.x=board.x+1; board.y=board.y+2; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x-1; board.y=board.y-2; mover--; } //Case #4 if((board.x+2)<max_num && (board.y+1)<max_num && board.board[board.x+2][board.y+1]==0) { board.x=board.x+2; board.y=board.y+1; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x-2; board.y=board.y-1; mover--; } //Case #5 if((board.x+2)<max_num && (board.y-1)>0 && board.board[board.x+2][board.y-1]==0) { board.x=board.x+2; board.y=board.y-1; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x-2; board.y=board.y+1; mover--; } //Case #6 if((board.x+1)<max_num && (board.y-2)>0 && board.board[board.x+1][board.y-2]==0) { board.x=board.x+1; board.y=board.y-2; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x-1; board.y=board.y+2; mover--; } //Case #7 if((board.x-1)>0 && (board.y-2)>0 && board.board[board.x-1][board.y-2]==0) { board.x=board.x-1; board.y=board.y-2; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x+1; board.y=board.y+2; mover--; } //Case #8 if((board.x-2)>0 && (board.y-1)>0 && board.board[board.x-2][board.y-1]==0) { board.x=board.x-2; board.y=board.y-1; board.move++; mover++; board.board[board.x][board.y]=mover; if(mover<numove) { moving(board); } board.board[board.x][board.y]=0; board.x=board.x+2; board.y=board.y+1; mover--; } if (mover==numove) { draw(board); count++; cout<<"Total Count is: "<<count <<endl; }