0

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

#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() 方法上。但是，我无法找到错误。请帮我识别它。

我正在采取的方法是否涉及回溯？如果不是，请提供相同的一些解释

4

4 回答 4

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。

于 2012-07-13T18:57:04.157 回答
0

你的方法不会回溯。它迭代了一些可能性，而不是全部。这个问题最好递归解决，所以我不会像你那样做。您必须为女王被其他人攻击定义规则。您使用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)是我的规则，它断言 2 个皇后不会互相攻击。
  5. 第二组for循环在约束规则内找到可以插入另一个皇后的条件。
  6. 然后我再次调用 find 函数。回溯就是这样完成的。
  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. 回溯的基础是，如果其中一个分支不起作用，您可以向上一级搜索另一个分支，依此类推，直到所有树都被搜索完。同样，递归是要走的路。
于 2012-07-13T18:57:21.560 回答
0

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

女王可能受到威胁的条件可以表述为 1) ColumnForRow[i] == ColumnForRow[j] - 它们将在同一列 2) (ColumnForRow[i] - ColumnForRow[j] ) == ( i- j) 或 (ColumnForRow[j] - ColumnForRow[i]) == (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();
}

}

于 2016-02-17T13:38:40.467 回答
0

您的代码没有递归方法，这是设计回溯算法时首先想到的。因此，您在这里没有实施任何回溯策略。

您的函数 isAvailable() 在许多方面都不完整。

要检查一个单元格（行、列）是否受到已经放置的皇后的攻击，您可以使用以下策略。

注意事项：

  1. 逐行放置皇后

  2. 要将皇后放置在第 i 行，我们需要检查与放置在第 0 到 (i-1) 行的皇后的冲突。

  3. 女王水平，垂直和对角线攻击。

代码（参考：Tushar Roy 的讲座/代码）

boolean isSafe = true;
for(int queen = 0; queen<row; queen++) // Checking with already placed queens
{
    // attack condition
    if(position[queen].column == column || position[queen].row + 
    position[queen].column == row + column || position[queen].row - 
    position[queen].column == row-column)
    {
        isSafe = false;
        break;
    }
}

希望这可以帮助。

于 2017-09-26T20:42:13.473 回答