Некоторые сомнения 8 проблемы ферзя алгоритм

Question

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

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

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

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

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

Это правда?

Tnx

Andrea

Answer 1

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

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

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

• При проверке совместимости размещения нам нужно только проверить: есть ли королева в той же строке и 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-я королева находилась в плохом месте и т. Д.