ñ女王布局算法 [英] N Queen Placement Algorithm

问题描述

我解决N个皇后问题，我们需要把N后在NXN的国际象棋棋盘，使得没有两个皇后可以攻击对方。

I was solving the N Queen problem where we need to place N queens on a N X N chess board such that no two queens can attack each other.

#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。请帮我鉴定吧。

I think the problem is with the isAvailable() method. However, I am not able to find the bug. Please help me identify it.

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

推荐答案

您的方法不走回头路。它遍历了一些可能性，不是全部。这个问题的最好解决递归，所以我不会做它，你在做什么。你必须定义规则的女王被攻击等。你这样做使用 IFS 和递归再次应用规则和迭代。大多数的回溯算法递归写入。 我会给你一个答案，这样你就可以基于你对我的。

Your approach does not backtrack. It iterates over some possibilities, not all. This problems is best solved recursively, so I wouldn't do it as you are doing. You have to define the rules for a Queen being attacked by other. You do it using ifs, and recursion to apply the rule again and to iterate. Most of the backtracking algorithms are written recursively. I will give you an answer, so you can base yours on mine.

#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);
}

该方法在下面的回溯作品：

The way backtracking works in the following:

1. 创建约束（规则）来检查，如果条件得到满足。
2. 在考虑的问题，因为一个搜索树。花在寻找这棵树的时间是根据 N ，电路板的尺寸。寻找最好的办法是递归的，所以心里有聪明的办法来解决是一个使用递归。
3. 在code，第一套为循环只是打印板提出，并检查是否问：如果发现。
4. ＃定义攻击（I，J）（HIST [J] ==我|| ABS（HIST [J] - 我）==山坳 - J）是我的规则，它声称2皇后不互相攻击。
5. 第二套为循环找到另一个女王可以插入其中的一个条件，约束规则之内。
6. 然后我再打电话找功能。这就是回溯是如何完成的。
7. 在我的基本情况是，2皇后可以在黑板上，然后我会递归地检查了一位王后可加至8。因此，2 + 1 =（1 + 1）+ 1 = 1（1 + 1）。再次应用该规则，我们有3 + 1 =（2）+ 1 + 1 =（2）+（1 + 1），并再次4 =（3）+ 1 + 1 =（3）+（1 + 1）的
8. 在递归这是否适合你。让出了个遍应用该规则。因此， F（N + 1）= F（N）+ 1 该案例和 F（2）= 2 是我的基本情况。
9. 回溯的基础是，如果这些分支中的一个不工作了，你可以去一个级别，并搜索另一个分支，依此类推，直到树全被搜索出来。此外，递归是要走的路。

1. create a constraint (a rule) to check if the conditions are meet.
2. Consider the problem as a search tree. The time spent to search this tree is based on n, the size of the board. The best way to search is recursively, so have in mind, the smart way to solve is using recursion.
3. In that code, the first set of for loops just prints the board out, and checks if Q if found.
4. # define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j) is my rule, which asserts 2 queens are not attacking each other.
5. The second set of for loops finds a condition which another queen can be inserted, within the constraint rules.
6. Then I call find function again. That's how the backtracking is done.
7. My base case is that 2 queens can be on the board, then I'm going recursively check if another queen can be added until 8. Thus, 2 + 1 = (1+1) + 1 = 1 (1 + 1). Applying the rule again, we have 3 + 1 = (2) + 1 + 1 = (2) + (1 + 1), and again 4 = (3) + 1 + 1 = (3) + (1+1).
8. Recursion does that for you. Let out apply the rule over and over. So f(n+1) = f(n) + 1 for that case and f(2) = 2 is my base case.
9. The base of backtracking is if one of those branches don't work out, you can go one level up and search another branch, and so on, until the tree is all searched out. Again, recursion is the way to go.

这篇关于ñ女王布局算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！