N皇后区问题

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中；这样更容易预防和跟踪错误(特别是当缩进不一致时)

。

这只是我的想法，我希望它们能有所帮助:)