8皇后问题的变化——排列数量回溯实现——输出错误

Question

8皇后问题的变化——排列数量回溯实现——输出错误

3

我正在尝试编写一个程序，给定一个初始输入，将计算在8X8的棋盘上放置8个皇后的不同排列数量。但是，我的测试数据并没有给我适当的输出。我想知道你们能否指点我方向。虽然我的编译器没有错误，但我在最后一个数据集上得到了分段错误。

我已经尝试过调试，但我认为我只是看着我的代码太久，开始困惑自己了。如果有人能给我一些帮助，我会非常感激。谢谢。我认为我的问题可能要么在isSafe函数中，要么在solveNQUtil方法中的停止条件。

我的测试数据（每行是单独的行、列、我的输出和期望结果）：

r    c    Output      Expected output
1    2       14         8
6    7       8          14
7    8       312        8
8    8       312        4
2    2       4          16
2    4       12         8
1    7       8          8
8    3    Seg Fault     16

我的代码：

#include <iostream>
#include<stdio.h>
using namespace std;
int arrangements = 0;
int column_start = 0;
/* A utility function to print solution */
void printSolution(int board[8][8])
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
            if( board[i][j] ) {
                printf(" Q ");
            }else{
                printf(" . ");
            }
            //printf(" %d ", board[i][j]);
        printf("\n");
    }
}
bool isSafe(int board[8][8], int row, int col)
{
    int i, j;
    for (i = 0; i < 8; i++){
        if (board[row][i]){
            return false;
        }
    }
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--){
        if (board[i][j]){
            return false;
        }
    }
    for (i = row, j = col; i < 8 && j < 8; i++, j++){
        if (board[i][j]){
            return false;
        }
    }
    for (i = row, j = col; j >= 0 && i < 8; i++, j--) {
        if (board[i][j]){
            return false;
        }
    }
    for( i = row, j = col; j < 8 && i >= 0; i--, j++){
        if (board[i][j]){
            return false;
        }
    }
    return true;
}
void solveNQUtil(int board[8][8], int queens, int col)
{
    if (queens >= 8){
        printSolution(board);
        cout << "---------------------------------------------" << endl;
        arrangements++;
    }else{
        for (int i = 0; i < 8; i++){
            if ( isSafe(board, i, col) ){
                board[i][col] = 1;
                int tempCol = (col + 1) % 8;
                solveNQUtil(board, queens + 1, tempCol );
                //backtrack
                board[i][col] = 0; 
            }
        }  
    }
}
bool solveNQ(){
    int row = 0;
    int col = 0;
    int board[8][8];
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            board[i][j] = 0;
        }
    }
    cin >> row >> col;
    board[row][col] = 1;
    column_start = col;
    solveNQUtil(board, 1, (col + 1) % 8);
    //solveNQUtil(board,0,0);
    if(arrangements == 0){
        printf("Solution does not exist");
        return false;
    }
    return true;
}
int main(){
    solveNQ();
    cout << "Arrangements: " << arrangements << endl;
    return 0;
}

- GiH

当您使用调试器时，哪些行导致了问题？ - Thomas Matthews

我不理解这个游戏的规则。第一行和第一列在哪里？如果初始值为r=1和c=2，那么该位置应该有一个Q吗？ - Barmak Shemirani

2个回答

1

您将其编程为从零索引开始，因此您只需要将输入减少一。所有输出都将与预期结果匹配。

cin >> row >> col;
row--;
col--;
if (row < 0 || row >= 8 || col < 0 || col >= 8) return false;

- Barmak Shemirani

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- halbs · Accepted Answer

只要你的row < 8 and col < 8，那么你得到的输出是正确的。你给出的期望输出是错误的。

当row = 8 or col = 8时，数组索引越界并尝试将值分配给未分配给数组的某些内存。

如果其他内存是空闲的，它将存储在其中，并且不会有任何错误，但是您的输出将是错误的，因为您的第一个皇后在棋盘外，但您告诉您的solveNQUtil在棋盘上有一位皇后。
但是，如果该其他内存已分配给其他内容，则会发生分段错误。