c++ n皇后问题

题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入

一个整数n（ 1 < = n < = 10 )

输出

每行输出对应一种方案，每种方案顺序输出每一行皇后所在的列号，相邻两数之间用空格隔开，按字典序输出。如果不存在对应的方案，输出-1。

样例输入

4

样例输出

2 4 1 3
3 1 4 2

Source Code

#include <bits/stdc++.h>
using namespace std;
bool used[11];
int g[11][11];
int n;
bool flag=0;
bool check(int x,int y)
{
    int xx = x,yy = y;
    while(x >= 1&&y >= 1)
    {
        if(g[x][y] == 1) return 0;
        x--,y--;
    }
    x = xx,y = yy;
    while(x >= 1&&y <= n)
    {
        if(g[x][y] == 1) return 0;
        x--,y++;
    }
    return 1;
}
void dfs(int u)
{
    if(u == n + 1)
    {
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= n;j ++)
            if(g[i][j] == 1)
            {
                printf("%d ",j);
                break;
            }
        }
        printf("n");
        flag = 1;
    }
    for (int i = 1;i <= n;i ++)
    if(used[i] == 0&&check(u,i) == 1)
    {
        g[u][i] = 1;
        used[i] = 1;
        dfs(u + 1);
        used[i] = 0;
        g[u][i] = 0;
    }
}
int main()
{
    cin >> n;
    memset(used,sizeof(used));
    memset(g,sizeof(g));
    dfs(1);
    if(flag == 0) cout << -1 << endl;
    return 0;
}