N 퀸으로 잘못된 출력

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)"행에서 코드는 단일 열에 2 개의 여왕이있을 수 없다고 가정합니다. 전화는 col + 1 대신 col을 사용해야하며 현재 열에서 멈춘 위치를 어떻게 든 고려해야합니다.

3. 여왕이없는 열을 허용하려면 solve 함수의 어딘가에 "solve (configuration, N, col + 1)"에 대한 무조건 부 호를 지정해야합니다.

4. 항목 2를 허용하면 함수 canPlace를 수정하여 열을 확인해야합니다.

5. 폰이 발견 될 때마다 canPlace의 루프가 중단되어야합니다.

Answer 2

폰이 길을 막고 있으면 같은 열에 더 많은 여왕을 배치 할 수 있기 때문에 다음 열로 넘어 가지 않아야합니다. 재실행 할 때 행과 열 모두를 전달하도록 코드를 수정하고 다음 열이 아닌 다음 사각형으로 만 이동해야합니다.

또한 알고리즘이 최상의 솔루션 대신 첫 번째 솔루션을 찾은 것처럼 보입니다. 원래의 퀸즈 문제는 약 1 개의 가능한 해결책만을 고 려했지만 수정 된 문제로 모든 솔루션을 확인하고 가장 좋은 해결책을 기억해야합니다.

또한 canPlace 함수가 잘못되었습니다. 폰을 전혀 고려하지 않습니다.