Skip to content

Instantly share code, notes, and snippets.

@iyedb

iyedb/nqueens.cxx

Created Mar 2, 2014
Embed
What would you like to do?
N Queens solution implementation in C++
#include <iostream>
#include <vector>
#include <sstream>
#include <set>
#include <cmath>
std::set<std::vector<int>> solve(int n)
{
class place_queens
{
int queens;
public:
place_queens(int _n): queens(_n){}
std::set<std::vector<int>> operator()(int moves)
{
if(moves == 0) return std::set<std::vector<int>>{{}};
else {
std::set<std::vector<int>> solutions = this->operator()(moves - 1);
std::set<std::vector<int>> nexts;
for (auto v : solutions) {
for (auto col = 0; col < queens; ++col) {
if (is_safe(col, v)) {
std::vector<int> next(v.size());
std::copy(v.begin(), v.end(), next.begin());
next.push_back(col);
nexts.insert(next);
}
}
}
return nexts;
}
}
bool is_safe(int col, std::vector<int> positions)
{
int row = positions.size();
if (positions.empty()) {
return true;
}
else {
for(int i = 0; i < positions.size(); ++i){
if( col == positions[i]
|| std::abs(row - i) == std::abs(col - positions[i]) ) {
return false;
}
}
}
return true;
}
};
return place_queens(n)(n);
}
int main(int argc, char* argv[])
{
if (argc == 1) {
std::cerr << "please enter a number of queens\n";
return 1;
}
std::stringstream ss;
ss << argv[1];
int size = 0;
ss >> size;
std::set<std::vector<int>> solutions = solve(size);
std::cout << "all solutions: " << solutions.size() << std::endl;
auto sol = solutions.begin();
std::cout << "a solution:\n";
for (auto i : *sol) {
std::cout << i << " ";
}
std::cout << "\n";
}
@iyedb

This comment has been minimized.

Copy link
Owner Author

@iyedb iyedb commented Mar 2, 2014

c++ -std=c++11 nqueens.cxx -o nqueens

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment