рыцарский тур с использованием стека

Передо мной стоит задача итеративного решения тура Рыцарей с использованием стека для хранения предыдущих ходов, чтобы я мог выскочить, если конь застрял. Моя программа, кажется, делает несколько POPS, но, кажется, никогда не решает загадку.
Он использует правило warnsdorffs для первых 32 ходов, а затем использует стек для решения оставшихся пробелов.

Что-то не так с моей логикой, чтобы она никогда не решала головоломки?

Это законная функция перемещения

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

Вот решаемая функция

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

0

Решение

Вероятно, это SIGSEGV (ошибка сегментации), потому что вы пытаетесь записать размер больше arr.

Как объявляется обр? Вы уверены, что когда вы делаете это:

arr[nextMoveX][nextMoveY] = counter;

nextMoveX и nextMoveY находятся в пределах значений измерения массива, как объявлено (или malloc’d)?

0

Другие решения


По вопросам рекламы [email protected]