我应该解决 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);
}
最佳答案
您的算法几乎没问题。一个小的改变可能会给你足够的时间来改进,以更快地产生一个解决方案。此外,还有一个数据结构更改应该可以让您进一步减少时间。
首先,稍微调整一下算法:而不是一直等待检查直到您放置所有 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 秒才能得到解决方案。
关于algorithm - 1秒解决16皇后问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32162496/