N皇后输出错误

所以我必须做一个N皇后问题的修改版本，在这里我们给出棋子棋盘的初始配置，我们需要找到最大数量的皇后我们可以让他们不会互相攻击。输入由第一行中的一个整数给出棋盘的尺寸（NxN）和n条线来定义棋盘的设置。字符将是'p'（表示该位置已经有一个棋子）或'e'（意思是这个位置是空的）。N皇后输出错误

例如，对于这个输入，

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; 
}

来源

2014-12-06 user2977595

不检查'canPlace（）'中的列，也不检查左上角 – chux 2014-12-06 22:45:41

基本上，您的代码输出0，因为它要求我们在每列中只放置一个皇后，在您的示例中不是这样。

这就是说，有与算法（我不要求列表完成，虽然它可能是）多个问题：

代码不考虑每一种可能性：它只会找到第一个可能的安排，然后在单个“if（col> = N）return 1;”之后退出搜索。相反，它应该像“if（col> = N）在一个单独的变量中更新皇后的最佳可能值，然后返回0以继续搜索”。
在“if（solve（configuration，N，col + 1）== 1）”行中，代码假定在一列中不能有两个皇后。呼叫应使用col而不是col + 1，并以某种方式说明我们在当前列停止的位置。
若要允许没有皇后的列，应该在求解函数的某处放置无条件地调用“solve（configuration，N，col + 1）”。
当我们允许项目2时，函数canPlace应该被修改以检查列。
无论何时找到棋子，canPlace的循环都会中断。

来源

2014-12-06 22:57:55 Gassa

随着棋子挡住了路，你不应该只是移动到下一列，因为你可以在同一列中放置更多皇后。在递归时，应该修改代码以传递行和列，并且只移动到下一个正方形，而不是下一列。

此外，它看起来像你的算法找到第一个解决方案，而不是最好的解决方案。原来的皇后问题只关心1个可能的解决方案，但在修改后的问题中，您需要确保检查所有解决方案并记住最好的解决方案。

此外，您的canPlace功能是错误的。它根本不考虑兵器。

来源

2014-12-06 22:49:15 JS1

N皇后输出错误

回答

相关问题