1秒解决16皇后问题

Question

我应该在 1 秒内解决 16-Queens Problem。我使用了如下的回溯算法。当 N 小于 13 时，这段代码足以在 1 秒内解决 N-Queens Problem。但如果 N 大于 13，则需要很长时间。

我该如何改进它？

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

int n;
int arr[100]={0,};
int solution_count = 0;

int check(int i) 
{ 
    int k=1, ret=1;
    while (k < i && ret == 1) {
        if (arr[i] == arr[k] ||                 
            abs(arr[i]-arr[k]) == abs(i-k))     
            ret = 0; 
        k++;
    }
    return ret;
}

void backtrack(int i) 
{
    if(check(i)) {
        if(i == n) {
            solution_count++;
        } else {
            for(int j=1; j<=n; j++) {
                arr[i+1] = j;
                backtrack(i+1);
            }
        }
    }
}

int main() 
{ 
    scanf("%d", &n);  
    backtrack(0);
    printf("%d", solution_count);
}

Answer 1

你的算法几乎没问题。一个小的改变可能会给你足够的时间来改进，以更快地产生一个解决方案。此外，还有一个数据结构更改可以让您进一步减少时间。

首先，稍微调整算法：与其一直等待检查直到放置所有 N 个皇后，不如尽早检查：每次您要放置一个新皇后时，检查是否有另一个queen 在进行 arr[i+1] = j; 分配之前占据同一列或同一对角线 。这将为您节省很多 CPU 个周期。

现在需要加快对下一个女王的检查。为了做到这一点，你必须改变你的数据结构，这样你就可以在没有任何循环的情况下进行所有检查。方法如下：

您有 N 行

您有 N 列

您有 2N-1 条上升对角线

您有 2N-1 条下降对角线

由于在上面的四个 "dimensions" 中的任何一个中，没有两个皇后可以占据相同的位置，因此您需要一个布尔值数组来表示最后三件事；行保证不同，因为代表行的 backtrack 的 i 参数保证不同。

N 最多为 16，2N-1 最多为 31，因此您可以将 uint32_t 用于您的位数组。现在，您可以通过将按位和 & 应用于列位掩码和 1 << c 来检查列 c 是否被占用。对角线位掩码也是如此。

注意：在一秒钟内完成 16 Queen 问题会相当棘手。 very highly optimized program 在 800 MHz PC 上用 23 秒完成。一个 3.2 GHz 应该给你大约 4 倍的加速，但是大约需要 8 秒才能得到解决方案。

Answer 2

我会把while (k < i && ret == 1) {改成while (k < i) {
而不是 ret = 0; 做 return 0;.

（这将节省每次迭代的检查。可能是您的编译器无论如何都会这样做，或者其他一些性能技巧，但这可能会有所帮助）。

1秒解决16皇后问题

Resolve 16-Queens Problem in 1 second only

algorithm

backtracking

n-queens