Exponential problems and their C representation

Question

I came across well-known N-Queen problem and I was wondering how to write a program to calculate number of possibilities in this particular problem. My program can find solution fast for really small N's (since it's heuristic).

I'd also like to know how to represent such big numbers in C. Are there any algorithms for really big numbers? Anytime I write and implementation of my own arithmetic I get i. e. quadratic multiplication with tons of memory allocation what cannot be fast. Thank you in advance for exhaustive answer.

Answer 1

here is a nice solution, using recursion 
(taken from: <http://rosettacode.org/wiki/N-queens_problem#C>)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef uint32_t uint;
uint full, *qs, count = 0, nn;

void solve(uint d, uint c, uint l, uint r)
{
    uint b, a, *s;
    if (!d)  // exit condition
    {
        count++;
#if 0
        printf("\nNo. %d\n===========\n", count);
        for (a = 0; a < nn; a++, putchar('\n'))
        {
            for (b = 0; b < nn; b++, putchar(' '))
            {
                putchar(" -QQ"[((b == qs[a])<<1)|((a + b)&1)]);
            } // end for
        } // end for
#endif
        return;
    } // end if

    a = (c | (l <<= 1) | (r >>= 1)) & full;
    if (a != full)
    {
        for (*(s = qs + --d) = 0, b = 1; b <= full; (*s)++, b <<= 1)
        {
            if (!(b & a)) 
            {
                solve(d, b|c, b|l, b|r);
            } // end if
        } // end for
    } // end if
} // end function: solve


int main(int n, char **argv)
{
    if (n <= 1 || (nn = atoi(argv[1])) <= 0) nn = 8;

    qs = calloc(nn, sizeof(int));
    full = (1U << nn) - 1;

    solve(nn, 0, 0, 0);
    printf("\nSolutions: %d\n", count);
    return 0;
}  // end function: main