n-皇后问题

⬅ 返回

1、例题

2、方法

2.1、按行枚举

#include<iostream>
using namespace std;
const int N = 20;
int n;
int r[N];//列
int v[N];//对角线y=x+b---> b=y-x+n 
int unv[N];//反对角线 y=-x+b---> b=y+x
int st[N];//st[k]表示第k行放皇后的列数 
 
void dfs(int x)//找第x行的元素 
{
	if(x>n){//输出 
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(st[i]==j){
					cout<<"Q";
				}else{
					cout<<".";
				}
			}
			cout<<endl;
		}
		cout<<endl;
	}
	//当前是第x行 
	for(int i=1;i<=n;i++)//找列 
	{
		// 剪枝(对于不满足要求的点，不再继续往下搜索)  
		if(r[i]==0 &&v[i-x+n]==0&&unv[i+x]==0)
		{
			st[x]=i;
			r[i]=1;//第i列不让放了 
			v[i-x+n]=1;
			unv[i+x]=1;
			dfs(x+1);
			//恢复现场
			st[x]=0;
			r[i]=0;//第i列不让放了 
			v[i-x+n]=0;
			unv[i+x]=0;
		}
	}	
}
 
int main(){
	cin>>n;
	dfs(1); 
 
}

2.2、按元素枚举

#include <iostream>
using namespace std;
const int N = 20;
 
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];
 
void dfs(int x, int y, int s) // x表示的行 y表示的是列 s表示的是已经放上的皇后个数
{
    if (y == n)
        y = 0, x++; //列超出边界 让行下移 列从0开始
    if (x == n)     //已遍历完所有的行
    {
        if (s == n) //放上了n个皇后
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    cout << g[i][j];
                }
                cout << endl;
            }
            cout<<endl;
        }
        return;
    }
 
    //选择不放
    dfs(x, y + 1, s);
    //选择放上元素
    if (row[x] == false && col[y] == false && dg[x + y] == false && udg[x - y + n] == false)
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            g[i][j] = '.';
        }
    }
    dfs(0, 0, 0);
 
    return 0;
}