6

n-Queen問題のすべての可能な解決策に対してアルゴリズムを実装すると、多くのブランチで同じ解決策に到達することがわかりました。n-Queens問題に対するすべてのユニークなソリューションを生成する良い方法はありますか？異なるブランチ（保存と比較を除く）によって生成された重複ソリューションを回避するにはどうすればよいですか？

これが私が最初の解決策として試したことです： http ：//www.ideone.com/hDpr3

コード：

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

考えられるすべてのソリューションを生成するために、同じコードnqdfs_all ()関数を使用しましたが、コントロールを親に返さず、代わりに列挙とチェックを続けました。この関数を呼び出すと、さまざまなブランチが到達した重複した結果が表示されます。

4

1 に答える 1

8

各クイーンは異なる列に配置する必要があるという事実を利用する必要があります。すでにk個のクイーンを最初のk列に配置している場合は、クイーン番号k+1を列k+1に再帰的に配置し、行1からnを通過します（現在のように、すべてのn * nセルを通過するわけではありません）。有効な配置ごとにk：= k+1を続行します。このアルゴは重複するボードをまったく生成しないため、重複する結果を回避できます。

編集：対称性の回避に関する質問へ：たとえば、列1のクイーン1を行1に制限することで、対称性の一部を事前に回避できますn/2。対称解の出力を完全に回避したい場合は、見つかったすべての解をリストに保存する必要があります。新しい解を見つけたら、印刷する前に、対称の同等物の1つがリストにすでに存在するかどうかをテストします。

これをより効率的にするために、次のように定義された各ボードの「正規表現」を使用できます。特定のボードのすべての対称ボードを生成し、それぞれをバイト配列にパックします。これらの配列の中で、大きな数として解釈される最小値を持つ配列を保持します。このパックされた表現は、各ボードの対称クラスの一意の識別子であり、辞書/ハッシュテーブルに簡単に配置できます。これにより、その対称クラスがすでに非常に効率的に表示されているかどうかをテストできます。

于 2011-10-11T18:07:54.720 に答える