八皇后問題，是一個古老而著名的問題同辣，是回溯算法的典型案例弯屈。
該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊娜扇，即任意兩個皇后都不能處于同一行错沃、同一列或同一斜線上，問有多少種擺法雀瓢。
高斯認為有76種方案枢析。
1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解。
后來有人用圖論的方法解出92種結(jié)果刃麸。
現(xiàn)在給出n皇后問題的代碼：

#include<iostream>

using namespace std;

int total = 0;
int n;
int* n_queens;

void print()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n_queens[i];j++)
        {
            cout<<"0";
        }
        cout<<"1";
        for(int j=n_queens[i]+1;j<n;j++)
        {
            cout<<"0";
        }
        cout<<endl;
    }
    cout<<"****************************"<<endl;
}

bool check(int queen_i, int pos_i)//第queen_i個皇后醒叁，在第pos_i列
{
    int i, pos;
    for(i=0;i<queen_i;i++)//只需要查看前面的皇后
    {
        pos = n_queens[i];//在同一列
        if(pos_i==pos)
            return false;
        if((queen_i+pos_i)==(i+pos))//在右下角
            return false;
        if((queen_i-pos_i)==(i-pos))//在左下角
            return false;
    }
    return true;
}

void my_queens(int i)//第i個皇后
{
    for(int pos=0;pos<n;pos++)//在第pos列
    {
        if(check(i,pos))
        {
            n_queens[i] = pos;
            if(i == n-1)
            {
                total++; 
                print();
                n_queens[i] = 0;
                return;
            }
            my_queens(i+1);//找下一個皇后的位置
            n_queens[i] = 0;//回溯，這個皇后繼續(xù)尋找新位置
        }
    }
}

int main()
{
    cout<<"Please enter the number of queens."<<endl;
    cin>>n;
    n_queens = new int[n];
    my_queens(0);
    if(total==0)
        cout<<"There is no way."<<endl;
    else if(total==1)
        cout<<"There is only one way."<<endl;
    else
        cout<<"There are "<<total<<" ways."<<endl;
    return 0;
}

運行后可以發(fā)現(xiàn)當(dāng)n為1或大于3的時候才有解泊业。