算法基础之n-皇后问题

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;
        }