#pragma warning(disable:4996)

#include <Windows.h>
#include <tchar.h>
#include <cstdio>

/*
	submit time : 1
	request :
		Follow up for N-Queens problem.

		Now, instead outputting board configurations, return the total number of distinct solutions.
*/

void Swap(int* data, int i, int j) {
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

void totalNQueensRecursively(int& total, int* data, int length, int index) {
	if (index == length - 1) {
		bool bPossible = true;
		for (int i = 0; i < length; ++i) {
			for (int j = i + 1; j < length; ++j) {
				if (i - j == data[i] - data[j] || i - j == data[j] - data[i]) {
					bPossible = false;
					break;
				}
				if (!bPossible)
					break;
			}
		}
		if (bPossible)
			++total;
	}
	else {
		int vernier = index;
		while (vernier < length) {
			Swap(data, vernier, index);
			totalNQueensRecursively(total, data, length, index + 1);
			Swap(data, vernier, index);
			++vernier;
		}
	}
}

int totalNQueens(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;

	int total = 0;
	int* data = http://www.mamicode.com/new int[n];>