8 Queens Variation-排列数回溯实现-错误输出

Question

我正在尝试编写一个程序，在给定初始输入的情况下，将计算 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;
}

Answer 1

只要您的 row < 8 and col < 8 得到的输出是正确的。您给出的预期输出是错误的。

当 row = 8 or col = 8 数组索引超出范围并尝试将值分配给一些未分配给您的数组的内存。

如果其他内存是空闲的，它将存储在其中并且不会有任何错误，但是您的输出将是错误的，因为您的第一个女王在董事会之外，但您告诉您的 solveNQUtil 有一个董事会中的皇后。
但是如果其他内存已经分配给其他内存，您将遇到分段错误。

Answer 2

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

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

8 Queens Variation-排列数回溯实现-错误输出

8 Queens Variation- Number of Arrangements Backtracking Implementation- Wrong Output

c++

algorithm

backtracking

n-queens