Я должен решить Задачу с 16 ферзями за 1 секунду. Я использовал алгоритм возврата, как показано ниже. Этого кода достаточно, чтобы решить проблему N-Queens за 1 секунду, когда N меньше 13. Но это занимает много времени, если 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);
}
