Передо мной стоит задача итеративного решения тура Рыцарей с использованием стека для хранения предыдущих ходов, чтобы я мог выскочить, если конь застрял. Моя программа, кажется, делает несколько 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
Вероятно, это SIGSEGV (ошибка сегментации), потому что вы пытаетесь записать размер больше arr.
Как объявляется обр? Вы уверены, что когда вы делаете это:
arr[nextMoveX][nextMoveY] = counter;
nextMoveX и nextMoveY находятся в пределах значений измерения массива, как объявлено (или malloc’d)?