第n皇后算法的所有可能的解决方案 [英] All possible solution of the n-Queen's algorithm

问题描述

当实现一个算法的N皇后问题的所有可能的解决办法，我发现，是由许多分支得出了相同的解决方案。有没有什么好的方法来生成每一个独特的解决方案正皇后问题？如何避免由不同部门所产生的重复的解决方案（除了存储和比较）？

When implementing an algorithm for all possible solution of an n-Queen problem, i found that the same solution is reached by many branches. Is there any good way to generate every unique solutions to the n-Queens problem? How to avoid the duplicate solutions generated by the different branches (except store and compare)?

下面是我都试过了，对于第一种解决方案： http://www.ideone.com/hDpr3

Here is what i have tried, for the first solution: http://www.ideone.com/hDpr3

code：

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

/* crude */

#define QUEEN 'Q'
#define BLANK '.'

int is_valid (char **board, int n, int a, int b)
{
  int i, j;

  for (i=0; i<n; i++)
  {
    if (board[a][i] == QUEEN)
      return 0;
    if (board[i][b] == QUEEN)
      return 0;
  }

  for (i=a, j=b; (i>=0) && (j>=0); i--, j--)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }

  for (i=a, j=b; (i<n) && (j<n); i++, j++)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }

  for (i=a, j=b; (i>=0) && (j<n); i--, j++)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }

  for (i=a, j=b; (i<n) && (j>=0); i++, j--)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }
  return 1;
}

void show_board (char **board, int n)
{
  int i, j;

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

int nqdfs_all (char **board, int n, int d)
{
  int i, j, ret = 0;

  /* the last queen was placed on the last depth
   * therefore this dfs branch in the recursion 
   * tree is a solution, return 1
   */
  if (d == n)
  {
    /* Print whenever we find one solution */
    printf ("\n");
    show_board (board, n);
    return 1;
  }

  /* check all position */
  for (i=0; i<n; i++)
  {
    for (j=0; j<n; j++)
    {
      if (is_valid (board, n, i, j))
      {
    board[i][j] = QUEEN;
    nqdfs_all (board, n, d + 1);
    board[i][j] = BLANK;
      }
    }
  }

  return ret;  
}

int nqdfs_first (char **board, int n, int d)
{
  int i, j, ret = 0;

  /* the last queen was placed on the last depth
   * therefore this dfs branch in the recursion 
   * tree is a solution, return 1
   */
  if (d == n)
    return 1;

  /* check all position */
  for (i=0; i<n; i++)
  {
    for (j=0; j<n; j++)
    {
      if (is_valid (board, n, i, j))
      {
    board[i][j] = QUEEN;
    ret = nqdfs_first (board, n, d + 1);
    if (ret)
    {
      /* if the first branch is found, tell about its 
       * success to its parent, we will not look in other
       * solutions in this function.
       */
      return ret;
    }
    else
    {
      /* this was not a successful path, so replace the
       * queen with a blank, and prepare board for next
       * pass
       */
      board[i][j] = BLANK;
    }
      }
    }
  }

  return ret;
}

int main (void)
{
  char **board;
  int n, i, j, ret;

  printf ("\nEnter \"n\": ");
  scanf ("%d", &n);

  board = malloc (sizeof (char *) * n);
  for (i=0; i<n; i++)
  {
    board[i] = malloc (sizeof (char) * n);
    memset (board[i], BLANK, n * sizeof (char));
  }

  nqdfs_first (board, n, 0);
  show_board (board, n);

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

要生成所有可能的解决方案，我已经使用了相同的code nqdfs_all（）的功能，但没有返回的控制权交给父母，而不是继续列举和检查。调用该功能可显示不同的分支机构达到了重复的结果。

To generate all possible solution i have used the same code nqdfs_all () function, but did not return the control to the parent, instead continued enumerating and checking. A call to this function displays the duplicate results reached by different branches.

推荐答案

您应该利用这样一个事实：每个王后必须放置在不同的列。如果您已经放置皇后ķ在第k列，递归地把女王数k + 1列K + 1，并通过行1到n（而不是通过所有的N * N个单元，为您算法中目前如此）。继续K：= K + 1的各有效安置。这将避免任何重复的结果，因为这个算法中根本不产生任何重复板。

You should make use of the fact that each queen must be placed in a different column. If you have placed already k queens in the first k columns, recursively place queen number k+1 in column k+1 and go through rows 1 to n (and not through all n*n cells, as you algo currently does). Continue with k:=k+1 for each valid placement. That will avoid any duplicate results, since this algo does not generate any duplicate boards at all.

编辑：您如何避免对称性的问题：那些部分可以事先避免，例如，通过限制蜂王1列1行1，... N / 2 。如果你想避免完全对称解决方案的输出，你将不得不存储在列表中的每个找到解决方案，只要你找到一个新的解决方案，打印出来之前，测试，如果它的一个对称的等价物已经存在在列表中。

to your question about avoiding of symmetries: a part of those can be avoided beforehand, for example, by restricting queen 1 in column 1 to rows 1,...n/2. If you want to avoid the output of symmetric solutions completely, you will have to store every found solution in a list and whenever you find a new solution, before printing it out, test if one of it's symmetric equivalents is already there in the list.

为了使这更有效，你可以与每块板的canoncial重新presentation工作，定义如下。生成一个给定的所有对称板，收拾它每一个到字节数组，而那些阵列中保持阵列，PTED作为一个大数目除$ P $，取最小值。这种包装的再presention是对称类每块板的一个唯一的标识符，可以轻松的放进字典/哈希表，这使得测试，如果是对称类已经表现得很有效率。

To make this more efficient, you can work with a "canoncial representation" of each board, defined as follows. Generate all symmetric boards of a given one, pack each one of it into a byte array, and among those arrays keep the array which, interpreted as a big number, has the minimum value. This packed represention is a unique identifier of the symmetry class of each board and can be easily put in a dictionary / hash table, which makes testing if that symmetry class already appeared very efficient.

这篇关于第n皇后算法的所有可能的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！