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