Resolve 16-Queens Problem in 1 second only

I should resolve 16-Queens Problem in 1 second. I used backtracking algorithm like below. This code is enough to resolve N-Queens Problem in 1 second when the N is smaller than 13. But it takes long time if N is bigger than 13.

How can I improve it?

#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);
}

Solution

Your algorithm is almost fine. A small change will probably give you enough time improvement to produce a solution much faster. In addition, there is a data structure change that should let you reduce the time even further.

First, tweak the algorithm a little: rather than waiting for the check all the way till you place all N queens, check early: every time you are about to place a new queen, check if another queen is occupying the same column or the same diagonal before making the arr[i+1] = j; assignment. This will save you a lot of CPU cycles.

Now you need to speed up checking of the next queen. In order to do that you have to change your data structure so that you could do all your checks without any loops. Here is how to do it:

You have N rows
You have N columns
You have 2N-1 ascending diagonals
You have 2N-1 descending diagonals

Since no two queens can take the same spot in any of the four "dimensions" above, you need an array of boolean values for the last three things; the rows are guaranteed to be different, because the i parameter of backtrack, which represents the row, is guaranteed to be different.

With N up to 16, 2N-1 goes up to 31, so you can use uint32_t for your bit arrays. Now you can check if a column c is taken by applying bitwise and & to the columns bit mask and 1 << c. Same goes for the diagonal bit masks.

Note: Doing a 16 Queen problem in under a second would be rather tricky. A very highly optimized program does it in 23 seconds on an 800 MHz PC. A 3.2 GHz should give you a speed-up of about 4 times, but it would be about 8 seconds to get a solution.