Решить проблему 16-куин за 1 секунду

Question

Я должен решить проблему с 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);
}

Answer 1

Ваш алгоритм почти в порядке. Небольшое изменение, вероятно, даст вам достаточно времени для улучшения решения. Кроме того, есть изменение структуры данных, которое должно позволить вам еще больше сократить время.

Во-первых, немного подправьте алгоритм: вместо того, чтобы ждать проверки, пока вы не разместите все N королевы, проверяйте заранее: каждый раз, когда вы собираетесь разместить новую королеву, проверьте, занимает ли другая королева тот же столбец или ту же диагональ, прежде чем arr[i+1] = j; назначение. Это сэкономит вам много циклов процессора.

Теперь вам нужно ускорить проверку следующей королевы. Для этого вы должны изменить структуру данных, чтобы вы могли выполнять все проверки без каких-либо циклов. Вот как это сделать:

• У тебя есть N строки
• У тебя есть N столбцы
• У тебя есть 2N-1 восходящие диагонали
• У тебя есть 2N-1 нисходящие диагонали

Поскольку никакие две королевы не могут занимать одно и то же место в любом из четырех "измерений" выше, вам нужен массив логических значений для последних трех вещей; строки гарантированно будут разными, потому что i параметр backtrack, который представляет строку, гарантированно будет другим.

С N до 16, 2N-1 идет до 31, так что вы можете использовать uint32_t для ваших битовых массивов. Теперь вы можете проверить, если столбец c берется путем применения побитового и & к битовой маске столбцов и 1 << c, То же самое касается диагональных битовых масок.

Примечание. Выполнение задачи с 16-ю королевами за секунду было бы довольно сложно. Очень оптимизированная программа делает это за 23 секунды на ПК с частотой 800 МГц. Частота 3,2 ГГц должна дать вам ускорение примерно в 4 раза, но для решения проблемы потребуется около 8 секунд.

Answer 2

Я бы поменял while (k < i && ret == 1) { в while (k < i) {
и вместо ret = 0; делать return 0;,

(это сохранит проверку при каждой итерации. Возможно, ваш компилятор так или иначе сделает это, или какой-то другой трюк с производительностью, но это может немного помочь).