N-Queens solution counter.

nqueens.cpp

// Use N <= 30 (good luck to calculate that)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// bits values for bit arrays: 
//    1 = free
//    0 = used
int lr_diag_state; // bit array
int rl_diag_state; // bit array
int col_state; // bit array
int n;
int counter;

inline bool state_free(int& state, int index) 
{
    return state & (1 << index);
}

inline void set_state_to_free(int& state, int index) 
{
    state |= (1 << index);
}

inline void set_state_to_used(int& state, int index) 
{
    state &= ~(1 << index);
}

void solve(int y)
{
    if (y == n) {
        ++counter;
        return;
    }

    for (int x = 0; x < n; ++x) {
        //if (column_free(x) and diagonals_collisions_free(x, y)) { // if column not used and any diagonal collision
        if (state_free(col_state, x) and state_free(rl_diag_state, x + y) and state_free(lr_diag_state, y - x + n)) {
            set_state_to_used(col_state, x);
            set_state_to_used(rl_diag_state, x + y);
            set_state_to_used(lr_diag_state, y - x + n);
            solve(y+1);
            // Backtrack:
            set_state_to_free(col_state, x);
            set_state_to_free(rl_diag_state, x + y);
            set_state_to_free(lr_diag_state, y - x + n);
        }
    }
}

int main()
{
    vector<int> mem(31, -1);
    while ((cin >> n) and n != 0) {
        const int all_free = (1 << 30) - 1; // Set all bits to free (1)
        lr_diag_state |= all_free;
        rl_diag_state |= all_free;
        col_state |= all_free;
        counter = 0;
        if (mem[n] == -1) {
            solve(0);
            mem[n] = counter;
            cout << counter << endl;
        }
        else {
            cout << mem[n] << endl;
        }
    }
    return 0;
}