N皇后布局算法

Question

我正在解决N皇后问题，我们需要将N个皇后放在一个can棋盘上，这样就没有两个皇后可以互相攻击。

#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()方法。但是，我找不到这个bug。请帮我辨认一下。

是我采用的方法，涉及回溯吗？如果没有，请提供一些解释。

Answer 1

你的方法没有倒退。它重复了一些可能性，而不是所有的可能性。这个问题最好是递归地解决，所以我不会像你这样做。你必须为女王被其他人袭击制定规则。您可以使用ifs和递归来再次应用规则并进行迭代。大多数回溯算法都是递归编写的。我会给你一个答案，这样你就可以在我的基础上。

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

int count = 0;
void solve(int n, int col, int *hist)
{
    int i, j;
    if (col == n) {
        printf("\nNo. %d\n-----\n", ++count);
        for (i = 0; i < n; i++, putchar('\n'))
            for (j = 0; j < n; j++)
                putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');

        return;
    }

#   define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
    for (int i = 0, j = 0; i < n; i++) {
        for (j = 0; j < col && !attack(i, j); j++);
        if (j < col) continue;

        hist[col] = i;
        solve(n, col + 1, hist);
    }
}

int main(int n, char **argv)
{
    if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8;
    int hist[n];
    solve(n, 0, hist);
}

回溯的工作方式如下：

1. 创建一个约束(规则)来检查条件是否满足。
2. 把这个问题看作是一个搜索树。搜索这棵树所花费的时间是基于n，即董事会的大小。最好的搜索方法是递归搜索，所以要记住，聪明的解决方法是使用递归。
3. 在该代码中，第一组for循环只打印出板，并检查是否找到Q。
4. # define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)是我的规则，它声称两个皇后没有互相攻击。
5. 第二组for循环在约束规则中找到可以插入另一个皇后的条件。
6. 然后我又打电话给find function。回溯就是这样完成的。
7. 我的基本情况是，两个皇后可以在板上，然后递归检查另一个皇后是否可以添加到8，因此，2+1= (1+1) +1=1 (1 + 1)。再次应用该规则，我们得到了3+1= (2) +1= (2) + (1+1)和4= (3) +1= (3) +(1+1)。
8. 递归为你做到了这一点。让我们一遍又一遍地应用这个规则。所以这个例子的f(n+1) = f(n) + 1和f(2) = 2是我的基本案例。
9. 回溯的基础是，如果其中一个分支不工作，你可以去一个层次上搜索另一个分支，以此类推，直到树全部被搜索出来。同样，递归也是一条路。

Answer 2

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

您的解决方案总是将皇后放置在总是可用的位置(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。

Answer 3

使用一个一维数组来跟踪可以在每一行中放置皇后的列。

女王可能受到威胁的条件可以被确定为1) ColumnForRowi == ColumnForRowj --它们将位于同一列(ColumnForRowi - ColumnForRowj ) == ( i - j)或(ColumnForRowj - ColumnForRowi) == (i- j) --它们将位于同一对角线上。

公共类NQueenSolver {

static int BOARD_SIZE = 15;
static int count = 0;
static int columnForRow[] = new int[BOARD_SIZE];

public static void main(String[] args) {
    PlaceQueen(0);
    System.out.println(count);
}

static boolean check(int row) {
    for (int i = 0; i < row; i++) {
        int diff = Math.abs(columnForRow[i] - columnForRow[row]);
        if (diff == 0 || diff == row - i)
            return false;
    }
    return true;
}

static void PlaceQueen(int row) {
    if (row == BOARD_SIZE) {
        printBoard();
        ++count;
        return;
    }
    for (int i = 0; i < BOARD_SIZE; i++) {
        columnForRow[row] = i;
        if (check(row)) {
            PlaceQueen(row + 1);
        }
    }
}

private static void printBoard() {
    //System.out.println(Arrays.toString(columnForRow));
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (columnForRow[i] == j)
                System.out.print("Q ");
            else
                System.out.print("* ");
        }
        System.out.println();
    }
    System.out.println();
}

}