Brute Force Solution of the N-Queens Problem by James Pate Williams, Jr.

/*
*  NQueensBruteForce.cpp
*  NQueensBruteForce
*
*	Brute force determination of the total number of
*	solutions of the n-queens constraint satisfaction
*	problem (CSP). Order n! complexity algorithm.
*
*  Created by James Pate Williams, Jr. on 12/10/07.
*  Copyright 2007. All rights reserved.
*
*/

#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int ConstraintViolations(std::vector<int> &Q, int &cvCount) {
	int a, b, cv = 0, i, j, n;

	n = Q.size();

	for (i = 0; i < n; i++) {

		a = Q[i];

		for (j = 0; j < n; j++) {
			b = Q[j];

			if (i != j && a != -1 && b != -1) {

				if (a == b)
					cv++;

				if (i - j == a - b || i - j == b - a)
					cv++;
			}
		}
	}

	cvCount++;
	return cv;
}

void PrintSolution(std::vector<int> &solution) {
	char hyphen[256];
	int column, i, i4, n = solution.size(), row;

	if (n <= 10) {
		for (i = 0; i < n; i++) {
			i4 = i * 4;
			hyphen[i4 + 0] = '-';
			hyphen[i4 + 1] = '-';
			hyphen[i4 + 2] = '-';
			hyphen[i4 + 3] = '-';
		}
		i4 = i * 4;
		hyphen[i4 + 0] = '-';
		hyphen[i4 + 1] = '\n';
		hyphen[i4 + 2] = '\0';
		for (row = 0; row < n; row++) {
			column = solution[row];
			std::cout << hyphen;
			for (i = 0; i < column; i++)
				std::cout << "|   ";
			std::cout << "| Q ";
			for (i = column + 1; i < n; i++)
				std::cout << "|   ";
			std::cout << '|' << std::endl;
		}
		std::cout << hyphen;
	}
	else
		for (row = 0; row < n; row++)
			std::cout << row << ' ' << solution[row] << std::endl;
}

int main(int argc, char * const argv[])
{
	if (argc != 3) {
		std::cout << "usage: " << argv[0] << " numberOfQueens print";
		std::cout << std::endl;
		exit(-1);
	}

	int numberOfQueens = atoi(argv[1]);

	if (numberOfQueens <= 0) {
		std::cout << "numberOfQueens must be positive" << std::endl;
		exit(-1);
	}

	int count = 0, i, cvCount = 0, print = atoi(argv[2]), space = 0;
	clock_t clock0;
	std::vector<int> queenVector;

	clock0 = clock();
	for (i = 0; i < numberOfQueens; i++)
		queenVector.push_back(i);

	do {

		int cv = ConstraintViolations(queenVector, cvCount);

		if (cv == 0) {
			count++;

			if (print == 1) {
				PrintSolution(queenVector);
				std::cout << std::endl;
			}
		}
		space++;
	} while (std::next_permutation(
		queenVector.begin(),
		queenVector.end(),
		std::less<int>()));

	double seconds = (double)(clock() - clock0) / CLOCKS_PER_SEC;

	std::cout << "search space size     = " << space << std::endl;
	std::cout << "number of con checks  = " << cvCount << std::endl;
	std::cout << "number of solutions   = " << count << std::endl;
	std::cout << "total time (seconds)  = " << seconds << std::endl;
	return 0;
}