Почему сложность этого решения для n королев настолько велика?

Question

Я пытаюсь решить n queens problem с использованием матрицы для представления шахматной доски. Это мое первое решение:

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

#define N 13 

void printTable(int table[N][N], int size) 
{ 
    for(int i = 0; i < size; i++) 
    { 
     for(int j = 0; j < size; j++) 
     { 
      printf("%d ", table[i][j]); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
} 

bool isSafe(int table[N][N], int row, int column, int size) 
{ 
    // check the main diagonal 
    // we add +1 because otherwise we would be comparind against the base 
    // element on that line 
    for(int i = row + 1, j = column + 1; i < size && j < size; i++, j++) 
    { 
     if(table[i][j] == 1) 
      return false; 
    } 

    // check the secondary diagonal 
    for(int i = row + 1, j = column - 1; i < size && j >= 0; i++, j--) 
    { 
     if(table[i][j] == 1) 
      return false; 
    } 

    // check the column 
    for(int i = row + 1, j = column; i < size; i++) 
    { 
     if(table[i][j] == 1) 
      return false; 
    } 

    return true; 
} 

bool isSafeTable(int table[N][N], int size) 
{ 
    for(int i = 0; i < size; i++) 
    { 
     for(int j = 0; j < size; j++) 
     { 
      if(table[i][j] == 1) 
      { 
       if(!isSafe(table, i, j, size)) 
       { 
        return false; 
       } 
      } 
     } 
    } 
    return true; 
} 

void getQueens(int table[N][N], int size, int queens, int row) 
{ 
    if(queens == size) 
    { 
     if(isSafeTable(table, size)) 
     { 
      printTable(table, size); 
     } 
     return; 
    } 

    for(int i = 0; i < size; i++) 
    { 
     table[row][i] = 1; 
     if(isSafeTable(table, size)) 
     { 
      getQueens(table, size, queens + 1, row + 1); 
     } 
     table[row][i] = 0; 
    } 
} 

int main() 
{ 
    int table[N][N] = 
    { 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} 
    }; 

    getQueens(table, 4, 0, 0); 

    return 0; 
} 

Как вы можете видеть, я использую большой массив массивов Интс представлять шахматную доску. Размер матрицы равен 13 x 13. Чтобы решить проблему с менее чем 13 королевами, я работаю над подмножеством этой большой матрицы.

Как вы можете видеть, я использую функцию isSafeTable на каждом шаге, чтобы проверить правильность конфигурации шахматной доски. Если он есть, я переключаюсь на следующую строку. Если это не так, я возвращаюсь.

Однако эта функция isSafeTable имеет сложность O(n^3) (поскольку на каждой итерации она называет isSafe). Таким образом, я думал, что будет разумным решением отметить используемые элементы и просто проверить, доступно ли это пространство вместо проверки всей шахматной доски.

Итак, я пришел с этим решением:

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

#define N 13 

void printTable(int table[N][N], int size) 
{ 
    for(int i = 0; i < size; i++) 
    { 
     for(int j = 0; j < size; j++) 
     { 
      printf("%2d ", table[i][j]); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
} 

void _markWith(int table[N][N], int size, int row, int column, int element, 
    int specialCharacter) 
{ 
    for(int i = 0; i < size - row; i++) 
    { 
     int tmp = element; 
     // using the specialCharacter we can mark the queens with a different 
     // character depeneding on the calling function. 
     if(i == 0) 
      element = specialCharacter; 

     // mark the left diagonal 
     if(column - i >= 0) 
      table[row + i][column - i] = element; 

     // mark the right diagonal 
     if(column + i < size) 
      table[row + i][column + i] = element; 

     // mark the column 
     table[row + i][column] = element; 

     element = tmp; 
    } 
} 

// This is just a wrapper used to avoid duplicating the code for marking and 
// unmarking a table. 
void mark(int table[N][N], int size, int row, int column) 
{ 
    _markWith(table, size, row, column, -1, 8); 
} 

// See the documentation for `mark`. 
void unmark(int table[N][N], int size, int row, int column) 
{ 
    _markWith(table, size, row, column, 0, 0); 
} 

void getQueens(int table[N][N], int size, int queens, int row) 
{ 
    if(queens == size) 
    { 
     printTable(table, size); 
     return; 
    } 

    for(int i = 0; i < size; i++) 
    { 
     if(table[row][i] == 0) 
     { 
      // This function call will result in pruning the column and the 
      // diagonals of this element. It actually replaces the 0s with -1s. 
      mark(table, size, row, i); 

      getQueens(table, size, queens + 1, row + 1 ); 

      // Now replace the -1s with 0s. 
      unmark(table, size, row, i); 
     } 

    } 
} 


int main() 
{ 
    int table[N][N] = 
    { 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
     {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0} 
    }; 

    getQueens(table, 11, 0, 0); 

    return 0; 
} 

Функция mark и unmark используется для установки диагоналей и столбцов элемента в -1. Кроме того, элемент (королева) отмечен 8 (я думал, что человеческому глазу будет легче идентифицировать ферзей таким образом при печати матрицы).

_markWith Функция используется только, чтобы избежать перезаписи того же кода в mark и unmark.

Сложность этих функций - O(n), поэтому программа должна двигаться немного быстрее, но это не так. Первое решение на самом деле быстрее второго.

Вот некоторые статистические данные в зависимости от n:

Время, затраченное обоими решениями в зависимости от n:

n | first solution | second solution  
--+-----------------+-----------------  
4 | 0.001s   | 0.002s  
--+-----------------+-----------------  
5 | 0.002s   | 0.001s  
--+-----------------+-----------------  
6 | 0.001s   | 0.002s  
--+-----------------+-----------------  
7 | 0.004s   | 0.003s  
--+-----------------+-----------------  
8 | 0.006s   | 0.011s  
--+-----------------+-----------------  
9 | 0.025s   | 0.133s  
--+-----------------+-----------------  
10| 0.093s   | 3.032s  
--+-----------------+-----------------  
11| 0.581s   | 1m 24.210s 

Разница не то, что видно при малых значениях n, но для более крупных довольно очевидно.

Здесь число рекурсивных вызовов, что каждая функция не зависит от n:

n | first solution | second solution  
--+-----------------+-----------------  
4 | 16    | 16  
--+-----------------+-----------------  
5 | 53    | 65  
--+-----------------+-----------------  
6 | 152    | 514  
--+-----------------+-----------------  
7 | 551    | 7085  
--+-----------------+-----------------  
8 | 2 056   | 129 175  
--+-----------------+-----------------  
9 | 8 393   | 2 810 090  
--+-----------------+-----------------  
10| 35 538   | 70 159 513  
--+-----------------+-----------------  
11| 16 695   | 1 962 694 935 

Как вы можете видеть, количество рекурсивных вызовов экспоненциально возрастает во втором растворе. Таким образом, функции mark и unmark не несут ответственности за медленный ход программы.

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

Вы можете мне помочь?

Answer 1

Второе решение неверно. Он выводит больше решений, чем обычно.Например, для N = 5, он выводит (среди прочих):

8 0 0 0 0 
-1 -1 0 0 8 
-1 0 8 -1 -1 
8 -1 -1 -1 -1 
-1 -1 -1 8 -1 

0 0 0 8 0 
0 8 -1 -1 -1 
-1 -1 -1 -1 8 
8 -1 0 -1 -1 
-1 -1 -1 8 -1 

Причина ваша маркировка код:

if(table[row][i] == 0) 
{ 
     // This function call will result in pruning the column and the 
     // diagonals of this element. It actually replaces the 0s with -1s. 
     mark(table, size, row, i); 

     getQueens(table, size, queens + 1, row + 1 ); 

     // Now replace the -1s with 0s. 
     unmark(table, size, row, i); 
} 

Подумайте о том, что происходит с клеткой атакован двумя дамами: вы будете отмечать его при размещении первой королевы, сделать рекурсивный вызов (или больше, не имеет значения), пометьте его снова, а затем отмените его при возврате из второго рекурсивного вызова. Тогда вы забудете, что королева, помещенная во время первого рекурсивного вызова, все еще атакует его.

Обратите внимание, что в каждом из неправильных решений выше одна из королевы, которая неправильно помещена, атакуется двумя другими, и она также помещается перед двумя другими, которые атакуют ее.

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

Классическое решение

Правильный способ решения проблемы является использование алгоритма для генерации перестановок. Пусть:

col[i] = the column of the queen placed on row i 

Затем вам нужно генерировать правильные перестановки в col массиве. Я оставлю необходимые условия в качестве упражнения.

Конечно, вы также можете исправить свой подход, увеличивая и уменьшая счетчик вместо использования только 1/0.