n-皇后问题

全排列方法

1.用u表示每一行皇后的位置，在用i表示皇后的列坐标。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
char g[10][10];
int n;
bool col[N], dg[N], udg[N];//判断两个皇后的方法：两个皇后在一直线上，则截距相同，通过截距判断就行了
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i ++)puts(g[i]);
        puts("");
        
        return ;
    }
    
    for(int i = 0; i < n; i ++)
    {
        if(!col[i] && !dg[i + u] && !udg[n - u + i])//u - i可能是负数，所以用n减去u - i 
        {
            g[u][i] = 'Q';
            col[i] = dg[i + u] = udg[n - u + i] = true;
            dfs(u + 1);
            
            col[i] = dg[i + u] = 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);
}

原始做法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
char g[10][10];
int n;
bool col[N], row[N], dg[N], udg[N];
void dfs(int x, int y , int s)
{
    if(y == n)x ++ , y = 0;
    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[n - y + x])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n - y + x] = true;
        dfs(x, y + 1, s + 1);
        
        
        row[x] = col[y] = dg[x + y] = udg[n - y + x] = 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);
    
    
}