N皇后输出错误

Question

所以我必须做一个修改版的N皇后问题，我们得到了棋盘的初始配置，棋盘上装满了棋子，我们需要找到我们可以拥有的最大数量的皇后，这样它们就不会互相攻击。输入由第一行中的整数组成，表示棋盘( NxN)的维数，定义国际象棋board.The字符设置的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)返回1;“。相反，应该是“如果( >= N)在单独的变量中更新皇后的最佳值，然后返回0继续搜索”。
2. 在“如果(解题，N，col + 1) == 1 )”行中，代码假定一个列中不可能有两个皇后。调用应该使用col而不是col + 1，并以某种方式说明我们在当前列中停留的位置。
3. 若要允许列不带皇后，应该将无条件的“求解(configuration，N，col + 1)”调用放在solve函数的某个位置。
4. 当我们允许第2项时，应该修改函数canPlace以检查列。
5. 每当发现典当时，canPlace的循环就会中断。

Answer 2

由于棋子阻挡了前进的道路，你不应该仅仅继续进入下一列，因为你可以在同一列中放置更多的皇后。在递归时，您应该修改代码以同时传递一行和列，并且只移动到下一个正方形，而不是下一列。

而且，看起来您的算法找到了第一个解决方案，而不是最好的解决方案。最初的皇后问题只关心一个可能的解决方案，但是对于修改后的问题，您需要确保检查所有的解并记住最好的解。

而且，您的canPlace函数是错误的。它一点也不解释典当。