c - N Queen 的输出错误

Question

所以我必须做 N 皇后问题的修改版本，其中我们给出了充满棋子的棋盘的初始配置，并且我们需要找到我们可以拥有的皇后的最大数量，这样他们就不会'不要互相攻击。输入由第一行中的一个整数组成，该整数给出了棋盘的尺寸(NxN)，并且 n 行定义了棋盘的设置。字符将是“p”(意味着该位置已经有一个棋子)或“e”(表示该位置为空)。

例如，对于此输入，

5
epepe
ppppp
epepe
ppppp
epepe

输出将为 9。

这是我的代码，一切似乎都很清楚，但我不明白为什么它没有给出正确的输出

#include <stdio.h>
#include <malloc.h>

/* function headers */
void do_case(int);
int solve(char **,int,int);
int canPlace(char **,int,int,int);

/* Global vars */
int queens;

int main(void)
{
int n;
scanf("%d",&n);
getchar();
while( n != 0 )
{
    do_case(n);
    scanf("%d",&n);
    getchar();
}
return 0;
}

void do_case(int n)
{
int i,j; //counters for input

//board configuration allocation
char **configuration = (char **)malloc(n*sizeof(char *));
for(i = 0 ; i < n ;i++ ) 
    configuration[i] =(char *)malloc(n*sizeof(char));

queens = 0;

//get input
for( i = 0; i < n; i++ )
{

    for( j = 0; j < n; j++ )
    {
        scanf("%c",&configuration[i][j]);
    }
    getchar();
}

//solve
solve(configuration,n,0);
printf("%d \n",queens);




}

//recursive solver 
int solve(char **configuration,int N,int col)
{
int i,j;
//base case
if( col >= N )
    return 1;

//consider this column
//try placing queen in non blocked spot in all rows 
for(i = 0; i < N; i++)
{

    if ( configuration[i][col] == 'e' && canPlace(configuration,N,i,col) )
    {
        //Place queen in configuration[i][col]
        configuration[i][col] = 'q';
        queens++;

        //recursion on the rest
        if( solve(configuration,N,col + 1) == 1 )
        {
            return 1;
        }

        //backtrack
        configuration[i][col] = 'e'; 
        queens--;

    }
}

return 0;

}


//this function check if  queen can be placed
int canPlace(char **configuration,int N, int row, int col)
{
int i, j;

/* Check this row on left side */
for (i = 0; i < col; i++)
{
    if (configuration[row][i] == 'q')
    {
        return 0;
    }
}

/* Check upper diagonal on left side */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
    if ( configuration[i][j] == 'q')
    {

        return 0;
    }
}

/* Check lower diagonal on left side */
for (i = row, j = col; j >= 0 && i < N; i++, j--)
{
    if (configuration[i][j] == 'q')
    {

        return 0;
    }
}
return 1;
}

Answer 1

基本上，您的代码输出 0，因为它要求我们在每一列中放置一个皇后，但您的示例中并非如此。

也就是说，该算法存在多个问题(我并不认为该列表是完整的，尽管它可能是完整的):

1. 代码不会考虑所有可能性:它只会找到第一个可能的排列，然后在单个“if( col >= N ) return 1;”后退出搜索。相反，它应该像“if( col >= N ) 在单独的变量中更新皇后的最佳可能值，然后返回 0 继续搜索”。

2. 在“if(solve(configuration,N,col + 1) == 1)”行中，代码假定单个列中不能有两个皇后。该调用应使用 col 而不是 col + 1，并以某种方式说明我们在当前列处停止的位置。

3. 要允许没有皇后的列，应在求解函数中的某个位置放置对“solve(configuration,N,col + 1)”的无条件调用。

4. 当我们允许第 2 项时，应修改函数 canPlace 以同时检查该列。

5. 只要找到 pawn，canPlace 的循环就应该中断。