Какая ошибка в моем коде для головоломки n queen?

Question

#include <stdio.h> 
#include <math.h> 
char a[10][10]; 
int n; 
int feasible(int row,int col) 
{ 
    int i,j,tcol; 
    for(i=0;i<n;i++) 
    { 
     for(j=0;j<n;j++) 
     { 
      if(a[i][j]=='Q') 
       break; 
     } 
     tcol=j; 
     if(col==tcol || abs(row-i)==abs(col-tcol)) 
      return 0; 
    } 
    return 1; 
} 
void nqueen(int row) 
{ 
    int i,j; 
    if(row<n) 
    { 
     for(i=0;i<n;i++) 
     { 
      if(feasible(row,i)) 
      { 
       a[row][i]='Q'; 
       nqueen(row+1); 
       a[row][i]='.'; 
      } 
     } 
    } 
    else 
    { 
     printf("\nThe solution is:\n"); 
     for(i=0;i<n;i++) 
     { 
      for(j=0;j<n;j++) 
      { 
       printf("%c\t",a[i][j]); 
      } 
      printf("\n\n"); 
     } 
    } 
} 
      int main() 
{ 
    int i,j; 
    printf("Enter the number of queens:"); 
    scanf("%d",&n); 
    for(i=0;i<n;i++) 
    { 
     for(j=0;j<n;j++) 
     { 
      a[i][j]='.'; 
     } 
    } 
    nqueen(0); 
    getch(); 
    return 0; 
} 

Функция доступна, чтобы проверить, может ли королева быть помещена в строку & пройденный столбец.

Функция nqueen дает все возможные решения проблемы. Я не получаю никакого вывода на экране. Пожалуйста помоги!

Answer 1

Когда вы проверяете доску для осуществимости, вы должны проверить только те строки, которые вы уже разместили матка в:

int feasible(int row, int col) 
{ 
    int i, j, tcol; 

    for (i = 0; i < row; i++) { 
     for (j = 0; j < n; j++) { 
      if (a[i][j] == 'Q') break; 
     } 
     tcol = j; 

     if (col==tcol || abs(row - i) == abs(col - tcol)) 
      return 0; 
    } 
    return 1; 
} 

Для каждой строки i с i < row, есть матка. Все остальные ряды еще не имеют королев, а tcol equans n - значение, которое оно имело, когда оно выпало из цикла. Я предполагаю, что диагональная проверка иногда бывает случайной, разрезая совершенно правильное размещение королевы.

Вместо того чтобы найти королеву в каждой строке, вы можете проверить три пути - прямо вверх, левая диагональ (l) и вправо по диагонали (r) для всех строк:

int feasible(int row, int col) 
{ 
    int l = col; 
    int r = col; 

    while (row--) { 
     l--; r++; 

     if (a[row][col] == 'Q') return 0; 
     if (l >= 0 && a[row][l] == 'Q') return 0; 
     if (r < n && a[row][r] == 'Q') return 0; 
    } 

    return 1; 
} 

Другой способ представления доски заключается в том, чтобы сохранить ранг королевы для каждого файла, так что вам не нужно искать. Тем не менее, это сделает печать платы немного более сложной.