N queens problem trying all solutions
#include <iostream>
#define n 9
using namespace std;
int pos = 1, nos = 0;
int col[n + 1], RD[2 * n], LD[2 * n], a[n + 1];
int issafe(int i, int j)
{
if (col[j] == 1 || LD[i + n - j] == 1 || RD[i + j - 1] == 1)
return 0;
else
return 1;
}
void printboard(void)
{
int i;
cout<<endl;
for (i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
}
void placequeen(int i)
{
int j;
if (i == 1)
{
j = pos;
}
else
{
j = 1;
}
for (; j <= n; j++)
{
if (issafe(i, j) == 1)
{
//placing
a[i] = j;
col[j] = LD[i + n - j] = RD[i + j - 1] = 1;
if (i == n)
{
printboard();
++nos;
}
else
placequeen(i + 1);
//withdraw
a[i] = 0;
col[j] = LD[i + n - j] = RD[i + j - 1] = 0;
if (i == 1)
{
pos = j;
}
}
}
}
int main()
{
int i;
do
{
for (i = 1; i < n + 1; i++)
{
col[i] = a[i] = 0;
}
for (i = 1; i <= 2 * n; i++)
{
RD[i] = LD[i] = 0;
}
placequeen(1);
++pos;
} while (pos <= n);
cout<<endl<<"no. of sol = "<<nos;
return 0;
}
Comments
Post a Comment