• 04-09-2010
rickster11
Anyone familiar with the Knight's tour problem? Where you have to move a knight across a chess board, reaching all squares without touching any square twice.

I've been working on this code for a week now. I'm at my limits and out of ideas. My program solves all the way up to 62 moves, but enters a never ending loop when I try and solve for the last 2 moves.

I'm guessing I have some little bug that's throwing something off. I have no idea what it could be. If anyone could look over my code and give me any sort of hint, anything at all. I would be very happy.

Thanks

Code:

``` #include <iostream> #include <vector> #include <iterator> using std::cout; using std::endl; using std::vector; const int rowMoves [8] = {-2,-2, 1, 1, 2, 2, 1,-1};//Possible moves knight can make const int colMoves [8] = {-1, 1,-2, 2, 1,-1,-2,-2}; int grid [8][8];  //The size of chessboard, keeps track of where I have been                                         //I add a '1' if I've been there. vector <int> pathRow; //vectors used to record moves vector <int> pathCol; int counter = 0; bool ktour (int,int); int display (); //Not part of logic, just displays at end. int main (void) {                int row = 0;         int col = 0;         if (ktour (row, col));  //Calls ktour, which will run recursivly         {                 cout << "done" << endl;         }         display();         system ("pause");         return 1; } bool ktour (int row, int col) {         pathRow.push_back (row);  //Starts off with adding move to vectors         pathCol.push_back (col);         grid [row] [col] = 1;                //adds a one to place in grid, so I can show I've been there         counter++;         if (pathRow.size() == 64)  //This drops the program out of the recursive, checks to see if vector is 64                 return true;                        //needs to be 64 for 8 x 8, but I can only do 62.         int possRow, possCol, moveOption;         for (moveOption = 0; moveOption < 8; moveOption++) //Cycles through the 8 possible moves         {                 possRow = row + rowMoves [moveOption];                 possCol = col + colMoves [moveOption];                                 //The below if statement tries each of the 8 moves to see if its legal                 //If it finds a good move, it call the program again, sending the move location back to the top                 //where I can add to vector and start again.                 if (possRow < 8 && possRow >= 0 && possCol < 8 && possCol >= 0 && grid [possRow] [possCol] != 1)                 {                         if (ktour (possRow, possCol))  //recursion                                 return true;                 }         }         //The below lines of code will be reached if all 8 moves have been tried, and all have failed         //This code will attempt to back up my program, by returning false to lase stack and resetting counters         grid [pathRow.back()][pathCol.back()] = 0;        //Dead end, set that spot back to 0         pathRow.pop_back ();                        //remove move history from vectors         pathCol.pop_back ();         counter--;         return false; } int display () //Displays moves after program has solved. {         for (int index=0; index<(int)pathRow.size(); ++index)                 {                                cout << "Move#: " << index+1 << " Square: ";                         cout << pathRow.at(index) << ", ";                         cout << pathCol.at(index);                         cout << endl;                 }                 return 1; }```
• 04-09-2010
tabstop
This line:
Code:

`const int rowMoves [8] = {-2,-2, 1, 1, 2, 2, 1,-1};//Possible moves knight can make`
lacks the symmetry you would expect out of a knight move listing.