c - N皇后放置算法

Question

我正在解决 N 皇后问题，我们需要在 N X N 棋盘上放置 N 个皇后，这样任何两个皇后都不能互相攻击。

#include <stdio.h>  
#include <stdlib.h>
#include<math.h>

int size=8;
char arr[8][8];
int i,j;

void initializeBoard()
{
  for(i=0;i<size;i++)
  {
    for(j=0;j<size;j++)
    {
        arr[i][j]='.';
    }
  }
}

void printArray()
{

  for(i=0;i<size;i++)
  {

    for(j=0;j<size;j++)
    {
        printf("%c\t",arr[i][j]);
    }

    printf("\n");
  }
  printf("\n\n");
}

void placeQueen(int i,int j)
{
  arr[i][j]='Q';
}

int isAvailable(int i,int j)
{
   int m,n,flag;

   for(m=0;m<i;m++)
   {
      for(n=0;n<size;n++)
      {
        int k=abs(i-m);
        int l=abs(j-n);

        if(arr[m][j]!='Q' && arr[k][l]!='Q')
        {
            flag=1;
        }

        else
        {
            flag=0;
            break;
        }
    }
}
return flag;

}


int main(void)
{
    initializeBoard();

    for(i=0;i<size;i++)
    {
        for(j=0;j<size;j++)
        {
            if(isAvailable(i,j)==1)
            {
                // means that particular position is available
                // and so we place the queen there

                placeQueen(i,j);
                break;
            }
        }
    }

    printArray();
    return 0;
}

我认为问题出在 isAvailable() 方法上。但是，我找不到错误。请帮我鉴定一下。

我采用的方法是否涉及回溯？如果不是，请提供相同的解释

Answer 1

以前做过这个问题，并不是所有的布置都可以有效地解决这个问题。

您的解决方案涉及始终将皇后置于 (0,0) 位置，该位置始终可用。

当你遍历所有东西却找不到任何东西时，你将需要涉及回溯，或者你将需要依赖一个随机放置所有皇后的解决方案，然后检查解决方案(这种方法实际上比你会想，但与此同时，随机的因此在一般情况下效率非常低)

一个潜在的伪解决方案:

while(!AllQueensPlaced){
    for(going through the array ){
        if(isAvailable())
        {
            placeQueen();
            lastQueenPlaced = some logical location of last queen;
        }
    }
    if(!AllQueensPlaced)
    {
         backtrack(lastQueenPlaced);
    }
}

您的回溯方法应将 lastQueenPlaced 标记为脏并再次遍历数组以寻找新位置，然后再次执行 while 循环。不要忘记更改 backtrack() 中的 lastQueenPlaced，以防它也是 lastQueenPlaced。