爲什麼這個解決方案對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; 
} 

正如你所看到的，我使用int數組的大數組表示棋盤。矩陣的大小是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來修復您的方法。