Экспоненциальные проблемы и их представление C

Question

Я столкнулся с известной проблемой N-Queen, и мне было интересно, как написать программу для расчета количества возможностей в этой конкретной задаче. Моя программа может быстро найти решение для действительно маленьких N (так как она эвристическая).

Я также хотел бы знать, как представлять такие большие числа в C. Существуют ли алгоритмы для действительно больших чисел? Каждый раз, когда я пишу и реализую свою собственную арифметику, я получаю то есть квадратичное умножение с тоннами распределения памяти, что не может быть быстрым. Заранее спасибо за исчерпывающий ответ.

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