n-皇后问题

• dfs: 将下一个皇后不能放的位置标记

  • col列 dg对角线 udg反对角线

  • 已经确定一列只有有一个皇后的做法:

    •   #include<iostream>using namespace std;const int N=20;char g[N][N];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++){//udg中n是因为下标不能为0 需要加上n的偏移量 相当于映射一下if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){  //u看作y i看作x 一次函数的关系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;}
      

  • 更加原始的思路的做法:

    •   #include<iostream>using namespace std;const int N=20;char g[N][N];int n;bool row[N],col[N],dg[N],udg[N];void dfs(int x,int y,int s){  //x为横轴，y为纵轴，n为皇后个数if(y==n) y=0,x++;  //纵轴爆了 if(x==n){  //横轴爆了 遍历完if(s==n){  //皇后数量符合要求 输出for(int i=0;i<n;i++) puts(g[i]);puts("");return;}return;}//不放皇后dfs(x,y+1,s);//放皇后if(!row[x] && !col[y] && !dg[x+y]&& !udg[n+x-y]){g[x][y] = 'Q';row[x] =col[y] =dg[x+y]=udg[n+x-y] = true;dfs(x,y+1,s+1);row[x] =col[y] =dg[x+y]=udg[n+x-y] = 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);return 0;}