c - N QUEENS问题

Question

我尝试解决 N 皇后解决方案的问题，并设法创建一种算法，为我提供所有可能性并将其打印出来(我试图理解所有内容，但由于回溯对我来说有点陌生，所以很难)。

我的程序查看了每一种可能性并逐个打印出皇后的位置，看起来它运行良好，即使我不理解我的停止条件。

我的问题是我需要按特定顺序打印位置(从第一个皇后位置 0 - N 开始)，但它以随机方式打印。

我可以将它存储在一个数组中并对其进行排序，但这会花费太多时间，所以我想知道是否有人可以查看我的代码并指出可能存在的问题并提供一些提示或反馈。

#include <unistd.h>
 #include <stdio.h>
#define N 10

  void  print(int tab[N][N])
 {
   int i;
   int a;
   char c;

    i = -1;
    while (++i < N)
    {
    a = -1;
    while (++a < N)
        if (tab[a][i])
        {
            c = '0' + a;
            write(1, &c, 1);
        }
     }
     write(1, "\n", 1);
 }


   int  check(int tab[N][N] , int x, int y)
   {
      int i;
      int j;

      i = 0;
      while (i < x)
       if (tab[i++][y])
          return (0);
      i = x;
      j = y;
      while (j >= 0 && i >= 0)
       if (tab[i--][j--])
          return (0);
      i = x;
      j = y;
      while (i >= 0 && j < N)
        if (tab[i--][j++])
          return (0);
     return (1);
    }


    int     backtrack(int tab[N][N],int x ,int y, int *nbr)
    {
       if (x >= N)
       {
          print(tab);
          *nbr += 1;
       }
       while (++y < N)
         if (check(tab, x, y))
         {
              tab[x][y] = 1;
              if (backtrack(tab, x + 1, -1, nbr))
                  return (1);
              tab[x][y] = 0;
         }
       return (0);
    }


    int     ft_ten_queens_puzzle(void)
    {
       int tab[N][N];
       int nbr;
       int b;

       nbr = -1;
       while(++nbr < N)
       {
          b = -1;
          while (++b < N)
           tab[nbr][b] = 0;
       }
       nbr = 0;
       backtrack(tab,0,-1, &nbr);
       return (nbr);
    }

    int main()
    { 
             printf("%d\n",ft_ten_queens_puzzle());
     }

Answer 1

由于 print 中的几个错误，您的输出是随机的功能:

a) 如果你打印出一个网格，那么每个单元格都必须被输出，但是你打印的单元格不是tab[a][i]。是0

b) 你需要在每一行的末尾换行，但是你的 write 语句在错误的地方

所以函数应该是这样的:

void  print(int tab[N][N])
{
   char c;

   for (int i=0; i < N; i++)
   {
      for (int a=0; a < N; a++)
      {
         if (tab[a][i])
         {
            c = '0' + a;
         }
         else 
         {
             c = ' ';
         }
         write(1, &c, 1);
     }
     write(1, "\n", 1);
   }
}

一些提示/反馈:

• 使用完整且易于理解的变量名称。

• 不要使用笨拙的 "int x = -1; while (++x < N) {"格式 - 标准 for (int x=0; x < N; x++) {格式更好

• 正确缩进代码。例如，在 print 中，你在它的预期循环之外写了换行符，由于缩进问题很容易错过

• 是的，该语言允许您跳过单语句循环的“{”、“}”和if声明。我强烈建议永远不要跳过它们，但始终将它们放在所有循环和 if 上。 ;预防和追踪错误要容易得多(尤其是当缩进不一致时)

只是我的想法，希望对他们有所帮助:)