I'm tasked with solving the Knights tour iteratively using a stack to store the previous moves so I can pop if the knight is stuck. My program seems to be making multiple POPS but doesn't seem to be ever solving the puzzle. It uses Warnsdorffs rule for the first 32 moves and then uses a stack to solve the remaining spaces.
Is there something wrong with my logic so that it never solves the puzzle?
Is this a legal move function
bool safe(int row, int col) {
if (row >= 0 && row < 8 && col >= 0 && col < 8 && arr[row][col] == -1){
return true;
}
return false;
}// end safe
Here is the solve function
void solve(){
int x = 0; // initial start
int y = 0; // initial start
arr[0][0] = 0; // loading array with starting position
int nextMoveX, nextMoveY; // next move
Location top;
top.x = 0;
top.y = 0;
for(int i = 0; i < 8; i++){
top.movesArray[i] = safe(top.x+moveX[i], top.y+moveY[i]);
}
locate.push(top); // loading stack with initial position
int bestMove[8]; // array to sort best move
int counter = 0; // move counter
int count = 0;
while(counter < 63){
top = locate.top(); // check top of stack for current position
x = top.x;
y = top.y;
//loops through the 8 move choices
// using a stack to solve final steps
if( counter >= 31){
for(int i = 0; i < 8; i++){
top = locate.top();
if(top.movesArray[i]){
if(counter == 42){
cout << i;
}
//updates the top of the stack removing the
move just made from being made on a POP
top.movesArray[i] = false;
locate.pop();
locate.push(top);
counter++;
nextMoveX = x + moveX[i];
nextMoveY = y + moveY[i];
arr[nextMoveX][nextMoveY] = counter;
top.x = nextMoveX;
top.y = nextMoveY;
print();
cout << counter;
for(int j = 0; j < 8; j++){
top.movesArray[j] = safe(nextMoveX+moveX[j], nextMoveY+moveY[j]);
cout << top.movesArray[j];
}
locate.push(top);
break;
}
//if no more valid moves from this space pop off
if(i == 7){
arr[top.x][top.y]= -1;
locate.pop();
counter --;
cout << "pop";
top = locate.top();
for(int a = 0; a < 8; a++){
cout << top.movesArray[a];
}
break;
}
}
}
// heuristics for first 32 moves
else{
for(int i = 0; i < 8; i++){
bestMove[i] = -1; // resets # of potential moves at next space
print();
// test next position
nextMoveX = x + moveX[i];
nextMoveY = y + moveY[i];
//if safe count number of moves on next space
if(safe(nextMoveX,nextMoveY)){
for( int j = 0; j < 8; j++){
if(safe(nextMoveX+moveX[j],nextMoveY+moveY[j])){
bestMove[i] += 1;
}
}
}
//if on last move check for one with least moves available
if(i ==7){
int least = 8;
int pos = -1;
int L;
for(L = 0; L < 8; L++){
if(bestMove[L] < least && bestMove[L] != -1 && bestMove[L]!= 0){
least = bestMove[L];
pos = L;
}
} // end for
counter++;
nextMoveX = x + moveX[pos];
nextMoveY = y + moveY[pos];
arr[nextMoveX][nextMoveY] = counter;
top.x = nextMoveX;
top.y = nextMoveY;
for(int e = 0; e < 8; e++){
top.movesArray[e] = safe(nextMoveX + moveX[e],nextMoveY + moveY[e]);
}
locate.push(top);
} // end if (i=7)
} // end for i
} // end else
} // end while
} // end solve