CC150 9.9

9_9.cpp

/* CC150 9.9 */
// n queens

#include <iostream>
#include <vector>

using namespace std;

bool checkValid(vector<int> columns, int row) // return true if placement on (row) is valid
{
	for (int i = 0; i != row; ++i) {
		if (columns[i] == columns[row] || row - i == abs(columns[row] - columns[i]))
			return false;
	}
	return true;
}

// Recursion approach
void placeQueens(vector<int> columns, int row, vector<vector<int>> &placements)
{
	if (row == columns.size()) { // finish placement
		placements.push_back(columns);
		return;
	}
	for (columns[row] = 0; columns[row] != columns.size(); ++columns[row]) {
		if (checkValid(columns, row)) {
			placeQueens(columns, row + 1, placements);
		}
	}
}

vector<vector<int>> placeQueens(int n)
{
	vector<vector<int>> placements;
	vector<int> columns(n, -1);
	placeQueens(columns, 0, placements);
	return placements;
}

// Iteration approach
vector<vector<int>> placeQueensIter(int n)
{
	vector<vector<int>> placements;
	vector<int> columns(n, -1);
	int row = 0;
	while (row >= 0) {
		++columns[row]; // increment the current queen position
		while (columns[row] != n && !checkValid(columns, row))
			++columns[row]; // increment until a valid position or end of row
		if (columns[row] != n) { // valid position
			if (row == n - 1) {
				placements.push_back(columns); // save the result if all queens have been placed
			}
			else // move to the next row to place another queen
				++row;
		}
		else { // end of row
			columns[row] = -1; // reset queen position
			--row; // return to the previous row
		}
	}
	return placements;
}

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> placements = placeQueensIter(n);
	for (auto columns : placements) {
		for (int i = 0; i != n; ++i)
			cout << columns[i] << " ";
		cout << endl;
	}
	cout << "Number of solutions (Iteration): " << placements.size() << endl;
	placements = placeQueens(n);
	cout << "Number of solutions (Recursion): " << placements.size() << endl;
	return 0;
}