Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# The Qeens Problem

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```Prints all valid ways to arrange n qeens on a n x n chessboard so that the qeens don't attack each other.

```
#include

#include

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;
}

``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.