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

Popular Posts