Блог

При реализации алгоритма для всех возможных решений задачи 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) amp;amp; (j>=0); i--, j--)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }

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

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

  for (i=a, j=b; (i<n) amp;amp; (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", amp;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 () функции, но не вернул элемент управления родительскому элементу, вместо этого продолжил перечисление и проверку. Вызов этой функции отображает повторяющиеся результаты, достигнутые разными ветвями.

Вы должны использовать тот факт, что каждый ферзь должен быть помещен в другой столбец. Если вы уже разместили k ферзей в первых k столбцах, рекурсивно поместите номер ферзя k 1 в столбец k 1 и пройдите по строкам от 1 до n (а не по всем n * n ячейкам, как это делает ваш алгоритм в настоящее время). Продолжайте с k: = k 1 для каждого допустимого размещения. Это позволит избежать любых повторяющихся результатов, поскольку этот алгоритм вообще не генерирует никаких повторяющихся плат.

РЕДАКТИРОВАТЬ: на ваш вопрос об избежании симметрий: часть из них можно избежать заранее, например, ограничив queen 1 в столбце 1 строками 1, … n/2 . Если вы хотите полностью избежать вывода симметричных решений, вам придется сохранять каждое найденное решение в списке, и всякий раз, когда вы находите новое решение, перед его распечаткой проверьте, есть ли в списке один из его симметричных эквивалентов.

Чтобы сделать это более эффективным, вы можете работать с «каноническим представлением» каждой доски, определенным следующим образом. Сгенерируйте все симметричные платы заданной платы, упакуйте каждую из них в массив байтов, и среди этих массивов сохраните массив, который, интерпретируемый как большое число, имеет минимальное значение. Это упакованное представление является уникальным идентификатором класса симметрии каждой доски и может быть легко помещено в словарь / хэш-таблицу, что делает тестирование, если этот класс симметрии уже появился, очень эффективным.