为什么这个解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）。因此，我认为标记已使用的元素并仅检查 space 是否可用而不是检查整个棋盘将是一个更明智的决定。

所以，我想到了这个解决方案：

#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.

为什么这个解n皇后的复杂度这么大？

Why is the complexity of this solution to the n queens so big?

c

algorithm

recursion

time-complexity

n-queens