algorithm - 1秒解决16皇后问题

Question

我应该解决 16-Queens Problem在 1 秒内。我使用了如下的回溯算法。当 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皇后，尽早检查:每次你要放置一个新皇后时，检查是否有另一个皇后占据同一列或同一对角线在制作arr[i+1] = j;之前任务。这将为您节省大量 CPU 周期。

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

• 你有N行数
• 你有N专栏
• 你有2N-1上升对角线
• 你有2N-1下降对角线

由于没有两个皇后可以在上述四个“维度”中的任何一个中占据相同的位置，因此您需要一个 bool 值数组来表示最后三件事；这些行保证是不同的，因为 i backtrack 的参数，代表行，保证是不同的。

与 N最多 16 个，2N-1上升到 31，所以你可以使用 uint32_t为你的位数组。现在您可以检查列是否为 c通过按位应用 & 来获取到列位掩码和 1 << c .对角线位掩码也是如此。

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