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; }



LinkBack URL
About LinkBacks


