Skip to content

Instantly share code, notes, and snippets.

@afvanwoudenberg
Created October 19, 2018 12:44
Show Gist options
  • Save afvanwoudenberg/ae206a4debdfe8088ce1eb1ed0de8479 to your computer and use it in GitHub Desktop.
Save afvanwoudenberg/ae206a4debdfe8088ce1eb1ed0de8479 to your computer and use it in GitHub Desktop.
C++ solution to the N-queens problem
// nqueens.cpp
// Aswin van Woudenberg
#include <iostream>
#include <cstdlib>
bool issafe(int *rows, int i)
{
for (int k=0; k<i; k++)
if (rows[i] == rows[k] || abs(rows[i]-rows[k]) == i-k)
return false;
return true;
}
void println(int n)
{
std::cout << "+";
for (int c=0; c<n; c++)
std::cout << "-+";
std::cout << std::endl;
}
void printsol(int *rows, int n)
{
println(n);
for (int r=0; r<n; r++)
{
std::cout << "|";
for (int c=0; c<n; c++)
if (rows[r] == c)
std::cout << "Q|";
else
std::cout << " |";
std::cout << std::endl;
println(n);
}
std::cout << std::endl;
}
void nqueens(int *rows, int n, int i)
{
if (issafe(rows, i-1))
if (i == n)
printsol(rows, n);
else
for (int k=0; k<n; k++)
{
rows[i] = k;
nqueens(rows, n, i+1);
}
}
void nqueens(int n)
{
int *rows;
rows = new int[n];
nqueens(rows, n, 0);
delete [] rows;
}
int main(int argc, char *argv[])
{
int n; // number of queens
if (argc == 1)
std::cout << "Usage: " << argv[0] << " <number_of_queens>" << std::endl;
else
{
n = atoi(argv[1]);
if (n == 0)
std::cout << "No valid number of queens entered!" << std::endl;
else
nqueens(n);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment