我的任务是使用一个堆栈来存储之前的移动,以便在骑士被卡住时弹出,以迭代方式解决骑士之旅。我的程序似乎在制作多个 POPS,但似乎从未解决过这个难题。 它对前 32 步使用 Warnsdorffs 规则,然后使用堆栈来解决剩余的空间。
是不是我的逻辑出了什么问题,以至于永远无法解决这个难题?
这是一个合法的移动函数
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 是如何声明的?你确定当你这样做时:
arr[nextMoveX][nextMoveY] = counter;
nextMoveX 和 nextMoveY 在声明的(或 malloc 的)数组维度值内?
关于c++ - 使用堆栈的骑士之旅,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28534207/