首页 > 代码库 > [数据结构] N皇后问题

[数据结构] N皇后问题

代码:

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=100;
int c[N];//皇后第i行放在第几列上
int n,total;
int cc;//方法数

void dfs(int cur)
{
    if(cur>n)
    {
        cout<<"第"<<cc++<<"种方法:"<<endl<<endl;
        for(int i=1;i<=n;i++)
        {
            cout<<"第 "<<i<<" 个皇后放在第 "<<i<<" 行的第 "<<c[i]<<" 列上"<<endl<<endl;
        }
        total++;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        c[cur]=i;
        int ok=1;
        for(int j=1;j<cur;j++)
        {
            if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])
            {
                ok=0;
                break;
            }
        }
        if(ok)
            dfs(cur+1);
    }
}

int main()
{
    while(1)
    {
        cout<<"请输入皇后的个数: "<<endl;
        cin>>n;
        if(n<=0)
        {
            cout<<"输入不合法,程序退出!"<<endl;
            break;
        }
        cc=1;
        total=0;
        dfs(1);
        cout<<"总计有"<<total<<"个解"<<endl<<endl;
    }
    return 0;
}

执行截图:



[数据结构] N皇后问题