在1秒内解决16个皇后问题

Question

我应该在1秒内解决16皇后问题。我使用了如下的回溯算法。当N小于13时，此代码足以在1秒内解决N皇后问题。但如果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下降对角线

由于没有两个皇后可以在上述四个"维度"中的任何一个中占据相同的位置，因此您需要一个布尔值数组来存储最后三个内容;因为backtrack的i参数(代表行)保证不同，所以保证行不同。

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

注意:在一秒钟内做一个16皇后的问题是相当棘手的。一个高度优化的程序在一台800兆赫的电脑上只需23秒就能完成。3.2 GHz应该会给你大约4倍的速度提升，但需要大约8秒才能得到解决方案。

Answer 2

我要把while (k < i && ret == 1) {改成while (k < i) {
并将ret = 0;改为return 0;。

(这将在每次迭代中保存一次检查。也许你的编译器会这样做，或者其他一些性能技巧，但这可能会有所帮助)。