


Thread Tools  Display Modes 
Aug 31st, 2011, 2:39 PM  #1 
Newbie
Join Date: Aug 2011
Posts: 11
Rep Power: 0

Knights Tour problem
I posted this on Daniweb and no one helped me there so if it looks familiar that's why. Maybe someone here can help me.
I've been having some trouble making the knights tour (getting a knight to go around a chessboard without touching the same square twice) work correctly. Right now the max amount of moves I can get out of it is 59. I can't figure out any reason why it shouldn't go to 64 moves (which means it's completed). I just learned about multidimensional arrays, so if you're solution is even slightly advanced it probably won't help me. Please help me! Here's my code: #include <iostream> using std::cout; using std::endl; using std::cin; const int horizontal[8]={2,1,1,2,2,1,1,2}; const int vertical[8]={1,2,2,1,1,2,2,1}; int moveKnight(int board[][8]); bool check( int board[][8]); bool anyValid(int board[][8],int row, int column); void printArray(int [], int size); void resetArrayOneD(int [], int); void resetArrayTwoD(int [][8],int); int main() { int board[8][8]; int status=0; resetArrayTwoD(board,8); status=moveKnight(board); system("pause"); return 0; } int moveKnight(int board[][8]) { int currentRow=0; int currentColumn=0; int moves[64]; int counter=0; for (int i=0;i<64;i++) moves[i]=1; for (int i=0; i<=7;i++) for (int j=0;j<=7;j++) { //reset starting point and board resetArrayTwoD(board,8); resetArrayOneD(moves,64); counter=0; currentRow=i; currentColumn=j; board[i][j]=1; for (int k=0;k<=7;k++) //cycle through the moves possible if (currentRow+vertical[k]<8 && currentRow+vertical[k]>=0 && currentColumn+horizontal[k]<8 && currentColumn+horizontal[k]>=0 && board[currentRow+vertical[k]][currentColumn+horizontal[k]]==0 ) { //if it's not off the board and the spot wasn't taken currentRow+=vertical[k]; currentColumn+=horizontal[k]; board[currentRow][currentColumn]=1; moves[counter]=k; counter++; //reset moves to 1, the for will increment it to 0 k=1; } else if ((currentRow+vertical[k]<8 && currentRow+vertical[k]>=0 && currentColumn+horizontal[k]<8 && currentColumn+horizontal[k]>=0 && anyValid(board,currentRow, currentColumn)==0)k==7) { //if it's not off the board but there are no valid moves; we need to backtrack //we are taking away the PREVIOUS move do { counter; board[currentRow][currentColumn]=0; currentRow=vertical[moves[counter]]; currentColumn=horizontal[moves[counter]]; //have to reset some moves k=moves[counter]+1; //get rid of the last move recorded moves[counter]=1; }while (k>7); } else if (counter==63)// && check(board)) { //did it cout<<"Start at row "<<i<<" column "<<j<<endl; printArray(moves, 64); return 1; } } } void printArray(int a[], int size) { for (int i=0; i<size;i++) cout<<a[i]<<endl; } //see if it completed the tour bool check (int board[][8]) { for (int i=0;i<8;i++) for (int j=0;j<8;j++) if (board[i][j]==0) return 0; return 1; } //check if there are any valid moves to be made by cycling through the moves array //0 means no moves left bool anyValid(int board[][8],int row, int column) { for (int i=0;i<7;i++) { if (row+vertical[i]<8 && row+vertical[i]>=0 && column+horizontal[i]<8 && column+horizontal[i]>=0 && board[row+vertical[i]][column+horizontal[i]]==0) return 1; } return 0; } void resetArrayOneD(int a[], int size) //resets to 1 { for (int i=0;i<size1;i++) { a[i]=1; } } void resetArrayTwoD(int a[][8], int size) { for (int i=0;i<8;i++) for (int j=0;j<8;j++) a[i][j]=0; } 
Aug 31st, 2011, 3:50 PM  #2 
Programming Guru

Re: Knights Tour problem
You need to decrement k after backtracking, to account for the fact that the for loop is going to increment k to where it should be.
... }while (k>7); k = 1; ... This kind of nonsense is the sort of reason you shouldn't try to use a for loop for any purpose other than iterating over some sequence in a predetermined manner. It would be easier to reason and to read if you used a while loop. Incidentally, I think you could eliminate 'k' completely by using your 'moves' array. Also, you shouldn't really need your "anyValid" function (aside: it should be i<8 in this method, not i<7), if you're careful about how you handle your three cases. This is because there won't be a valid move if you've managed to try each k and the counter is less than 63, since you've now tested every other move from this board setup in previous iterations. Similarly, k will eventually get past 7 if there aren't any valid moves, so you don't need to make your backtrack condition so eager.
__________________
PFO's Folding@Home Team  Sane's Monthly Algorithms Challenges Rules  How to Post a Question  How to Post Code Becoming a good programmer requires foresight of your code's execution. Becoming an excellent programmer requires foresight of your code's modification. 
Sep 2nd, 2011, 2:29 AM  #3  
Newbie
Join Date: Aug 2011
Posts: 11
Rep Power: 0

Re: Knights Tour problem
Thank you for your help, I really do appreciate it. I went through your suggestions in my code, and really feel I gained from your advice.
Quote:


Sep 2nd, 2011, 1:29 PM  #4 
Programming Guru

Re: Knights Tour problem
Basically, instead of keeping moves[counter] at 1 until you find a valid k, you would do away with k and increment moves[counter] instead. Then moves[counter] can be substituted for k. To backtrack, you would decrement moves[counter]. You might need to make some other subtle changes in order to keep your backtracking loop correct, but that's the gist of it. The hope is that the code should become easier to follow because you will have fewer variables that are dependent on each other.
__________________
PFO's Folding@Home Team  Sane's Monthly Algorithms Challenges Rules  How to Post a Question  How to Post Code Becoming a good programmer requires foresight of your code's execution. Becoming an excellent programmer requires foresight of your code's modification. 
Bookmarks 
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)  
Thread Tools  
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Knight's Tour program need help  fistpunch  Java  16  Feb 7th, 2011 4:30 PM 
Serious RichTextBox problem  most hacker  C#  0  Feb 27th, 2010 4:23 AM 
How to develop problem analysis skills to enable one to decipher a given problem before coding in C++  Man G  C++  7  Apr 16th, 2009 4:49 AM 
Knights Tour Probelm  budder8818  Java  13  Feb 13th, 2009 5:14 AM 
Problem solving  ReggaetonKing  Software Design and Algorithms  7  Jan 4th, 2008 1:49 PM 