n皇后问题

#include<iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20;

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

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i < n; i ++)
            puts(g[i]);
        puts("");
    }
    for(int i = 0 ; i < n ; i ++)
    {
        if(!col[i] && !dg[n - u + i] && !udg[u + i])
        {
            col[i] = dg[n - u + i] = udg[u + i] = 1;
            g[u][i] = ‘Q‘;
            dfs(u + 1);
            col[i] = dg[n - u + i] = udg[u + i] = 0;
            g[u][i] = ‘.‘;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j ++)
            g[i][j] = ‘.‘;
    dfs(0);

    return 0;

}

最短步数问题采用DFS,皇后的同行同列以及对角线反对角线都不能有其他的皇后,所以DFS时u代表x坐标,i代表y坐标,x从0依次到n-1,保证不重复,y利用一个判重数组,保证不重复.
对角线y = x + b,反对角线y = -x + b,kx,y都有的情况下,用b可以判断是否在同一直线上.b = y - x,b = x + y,通过加上一个n的偏移量保证不会取到负数.
注意还原现场.

n-皇后问题