#include <iostream>
#include <set>
#include <stdlib.h>

typedef int INDEX;
const int n = 8;
INDEX col[n + 1];

bool promising (INDEX i)
{
        INDEX k;
        bool s;

        k = 1;
        s = true;
        while(k < i && s) {
                if( col[i] == col[k] || abs(col[i] - col[k]) == i - k)
                        s = false;
                k++;
        }
        return s;
}

int estimate_n_queens()
{
	INDEX i, j;
	int m, mprod, numnodes;
	set<INDEX> prom_children;

	int k;
	set<INDEX>::iterator p;

	i = 0;
	numnodes = 1;
	m = 1;
	mprod = 1;

	while( m != 0 && i != n ) {
		mprod = mprod * m;
		numnodes += mprod * n;
		i++;
		m = 0;
		prom_children.clear();

		for (j = 1; j <= n; j++) {
			col[i] = j;
			if(promising(i)) {
				m++;
				prom_children.insert(j);
			}
		}
		if( m != 0) {
			sranddev();
			k = rand() % prom_children.size();
			for(p = prom_children.begin(); k--; p++);
			j = *p;
			col[i] = j;
		}
	}
	return numnodes;
}


main()
{
	int i = 20, sum = 0;
	while (i--) {
		sum += estimate_n_queens();
	}
	cout << sum / 20 << endl;
}