n-皇后问题

框架

void dfs(开始位置 u)
{
    if(以后搜索完)
    {
        输出结果;
        return;
    }
    //枚举在这个位置可能转移到的所有状态
    for(所有可能转移到的状态)
    {
        转移到新状态;
        dfs(新的开始位置);
        恢复状态;
    }
}

思路1

比较原始的方法，枚举每一个位置放不放皇后，时间复杂度为$O(2^n)O(2^n)$

#include<iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], row[N], dg[N], udg[N];

void dfs(int x, int y, int s)
{
    if(y == n) y = 0, x++;
    if(x == n)
    {
        if(s == n)
        {
            for(int i = 0; i < n; i++) puts(g[i]);
            puts("");
        }
        return;
    }
    
    dfs(x,y+1,s);
    
    if(!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n] && g[x][y] == '.')
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x+y] = udg[y-x+n] = true;
        dfs(x,y+1,s+1);
        g[x][y] = '.';
        row[x]=col[y]=dg[x+y]=udg[y-x+n]=false;
    }
    
}

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;
}       

思路2

枚举每一行放不放皇后（因为我们很容易获取一个信息：每一行只能放一个皇后），时间复杂度为$O(n!)O(n!)$

#include<iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

//填写第u层
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++) puts(g[i]);
        cout << endl;
        return;
    }

    //第u层的所有选择，一共有n个
    for(int i = 0; i < n; i++)
    {
        if(!col[i] && !dg[i+u] && !udg[n + i - u])
        {
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            dfs(u+1);
            col[i] = dg[u+i]=udg[n-u+i] = false;
            g[u][i] = '.';
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            g[i][j] = '.';
    }
    dfs(0);
    return 0;
}