04N-皇后问题解法2

#include<iostream>
using namespace std;

const int N = 10;
int n;
char g[N][N];
bool row[N],col[N],dg[2*N],udg[2*N];

void dfs(int x,int y,int sum) //x是列，y是行，是让x不动，然后y向上走
{
    if(y==n+1) { //y跑到了n+1行，就调整回来
        y = 1;
        x++;
    }
    if(x == n+1) { //x跑到n+1行就枚举完了
        if(sum == n) //皇后的总数是n了，遍历完了整个g矩阵，得到了一组解
        {
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++)
                    cout << g[i][j];
                cout << endl;
            }
            cout << endl;
        }
        return;    
    } 
    //枚举一下每一个坐标的两种选择
    //不放皇后，就递归到下一个坐标
    dfs(x,y+1,sum);
    //放皇后
    if(!row[y] && !col[x] && !dg[x+y]&&!udg[y-x+n])
    {
        g[x][y] = 'Q';
        row[y] = col[x] = dg[x+y] = udg[y-x+n] = true;
        dfs(x,y+1,sum+1);
        g[x][y] = '*';
        row[y] = col[x] = dg[x+y] = udg[y-x+n] = false;
    }
}

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j] = '*';
    dfs(1,1,0); //从(1,1)开始搜，当然有0个皇后
    return 0;
}