Некоторые сомнения насчет алгоритма 8-ми задач

Question

Я изучаю проблему 8 ферзей, и я думаю, что следующий алгоритм для решения этой проблемы (но, кажется, не правильно)

Мой алгоритм работает таким образом на шахматной доске 8X8:

1. В начале поставить ферзя в случайном месте на доске
2. Отметьте как непригодные для использования все местоположения, которые находятся на горизонтальной линии, на вертикальной линии и на двух диагональных линиях текущей королевы.
3. Поместите другую королеву в любое место, все еще свободное на доске
4. Повторите этот процесс (из пункта 2) до тех пор, пока на доске не будет подходящего места

Я пробовал это решение на бумаге, но, часто я могу поставить только 7 королеву, а не королеву...

Поэтому я думаю, что это решение может разместить несколько ферзей, которые не могут есть друг друга, но не гарантирует, что, если я использую плату nXn, я всегда могу разместить 8 ферзей...

Это правда?

Tnx

Andrea

Answer 1

@miorel абсолютно прав насчет возврата. Просто для удовольствия я попытался решить эту грубую силу в C/C++, используя простой рекурсивный алгоритм с одной простой оптимизацией:

Мы знаем, что для любого заданного размера задачи N каждая ферзь будет находиться в отдельном столбце. Поэтому мы даже не пробуем другие столбцы. Итак, идея заключается в следующем:

• У каждой ферзя будет свой собственный столбец, поэтому ферзь 1 указывается в колонке 1, ферзь 2 в колонке 2 и т. Д.
• Таким образом, цель действительно состоит в том, чтобы выбрать ряд для каждой королевы. Начиная с первой королевы, давайте попробуем каждую строку по очереди. Мы делаем это, помещая ферзю в возможный ряд, а затем делаем рекурсивный вызов для размещения второй, третьей и четвертой ферзя.

• При проверке совместимости размещения нам нужно только проверить a) есть ли ферзь в той же строке и b) есть ли диагональные королевы.

  #include <stdlib.h>
  #include <stdio.h>
  
  int solveQueens(int queenIndex, int sz, int * positions) {
      for (int i=0; i<sz; i++) {
          int valid = 1;
          for (int j=0; j<queenIndex; j++) {
              int diff = queenIndex-j;
              if ( 
                      (positions[j]==i)
                  ||  (positions[j]+diff == i) 
                  ||  (positions[j]-diff == i)
              ) {
                  valid = 0;
                  break;
              }
          }
  
          if (valid) {
              positions[queenIndex]=i;
              if (queenIndex < sz-1) {
                  // Recursive call
                  int res = solveQueens(queenIndex+1, sz, positions);
                  if (res) 
                      return 1;
              } else {
                  return 1;
              }
          }
      }
      return 0;
  }
  
  void printQueens(int sz, int * positions) {
      for (int i=0; i<sz; i++) {
          printf("%c%d ", (char)(i+(int)'A'), positions[i]+1);
      }   
  }
  
  void queens(int sz) {
      int * positions = (int *)malloc(sizeof(int)*sz);
      if (solveQueens(0, sz, positions)) {
          printQueens(sz, positions);
      } else {
          printf("No solutions found\n");
      }
      free(positions);
  }
  
  int main() {
      queens(24);
      return 0;
  }
  

Я уверен, что это не оптимальный алгоритм, но он работает менее чем за 1 секунду при размерах платы 24.

Answer 2

Добавьте возврат к вашему алгоритму. Если размещение 7-й королевы приводит к позиции, в которой нет места для 8-й, то это было плохое место для 7-й королевы. Так что удалите его и выберите другое место для него. Если у вас закончились места для 7-й королевы, это означает, что 6-я королева оказалась в плохом положении и т. Д.