c - N-Queen 初学者回溯

Question

为了练习我所学到的回溯算法，我正在尝试解决 N-Queen 问题。

我编写了一些函数来检查移动是否合法，但我不知道如何使用回溯来实现这些函数。

bool manger_ligne (int a[][4],int i) {
    for (int j=0;j<4;j++) {
        if (a[i][j] == 1)
            return false ;
    }

    return true;
}

bool manger_col (int a[][4],int j) {
    for (int i=0;i<4;i++) {
        if (a[i][j] == 1)
            return false ;
    }
    return true ; 
}

bool isTrue (int a[][4],int i,int j,int k) {
    if (k==0) {
        return 1;
    }
    if (i > 3 && j > 3) {
        return 0;
    }

    if (manger_diagonal(a, i, j) == true && manger_col(a, j) == true &&
        manger_ligne(a, i) == true) {
        a[i][j] = 1;
        if (isTrue(a, i, j+1 ,k) == true) {
            if (isTrue(a, i+1,j ,k) == true) //backtracking problem
                return true;
        }
        a[i][j] = 0;
    }
    return false ;
}

Answer 1

几天前，我必须将这项任务作为学校任务来完成。这是一个有 8 个皇后的解决方案。我解决的方法如下:

主要我调用函数solveQn。然后程序会自己完成所有事情。

bool solveNQ:

bool solveNQ(){
int board[N][N] = { 
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0}
};
if ( solveNQUtil(board, 0) == false )
{
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}

bool 值solveNQUntil:

bool solveNQUtil(int board[N][N], int col){
if (col >= N)
    return true;
for (int i = 0; i < N; i++)
{
    if ( isSafe(board, i, col) )
    {
        board[i][col] = 1;
        if ( solveNQUtil(board, col + 1) )
            return true;
        board[i][col] = 0;
    }
}
return false;
}

bool 值是安全的:

bool isSafe(int board[N][N], int row, int col){
int i, j;

for (i = 0; i < col; 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; j>=0 && i<N; i++, j--)
    if (board[i][j])
        return false;

return true;
}

输出解:

void printSolution(int board[N][N]){
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
        printf(" %d ", board[i][j]);
    printf("\n");
}
}

在代码的开头，您需要定义一个全局变量 N，在本例中其值为 8。您还需要包含 header stdbool.h，因为在这里您将使用 bool 值。