DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

The Qeens Problem

10.02.2007
| 3419 views |
  • submit to reddit
        Prints all valid ways to arrange n qeens on a n x n chessboard so that the qeens don't attack each other.

#include <iostream>
#include <vector>

typedef std::vector< int > Vect;
typedef std::vector< Vect > List;

const int n = 12;

bool checkRow(const Vect &v, int k) {
	for (int i = k - 1; i >= 0; --i)
		if (v[k] == v[i])
			return false;

	return true;
}

bool checkDiag(const Vect &v, int k) {
	for (int i = k - 1; i >= 0; --i)
		if (k - i == abs(v[k] - v[i]))
			return false;
	
	return true;
}

List filter(List l, int k) {
	List r;
	for (List::const_iterator it = l.begin(); it != l.end(); ++it) {
		if (checkRow(*it, k) && checkDiag(*it, k))
			r.push_back(*it);
	}
	
	return r;
}

List qeens(int k) {
	if (0 == k) {
		List l;
		l.push_back(Vect());
		return l;
	}
	
	List l = qeens(k - 1);
	List r;
	for (List::iterator it = l.begin(); it != l.end(); ++it) {
		for (int newRow = 1; newRow <= n; ++newRow) {
			Vect v(*it);
			v.push_back(newRow);
			r.push_back(v);
		}
	}
	
	r = filter(r, k - 1);
	
	return r;
}

void printS(List l) {
	for (List::const_iterator it = l.begin(); it != l.end(); ++it) {
		for (Vect::const_iterator jt = it->begin(); jt != it->end(); ++jt)
			std::cout << *jt << " ";
		std::cout << std::endl;
	}
}

int main(int argc, char *argv[]) {
	List l = qeens(n);
	
	printS(l);
	
	return 0;
}