DFS-八皇后 Checker Challenge

灰太狼 2023-07-08 11:25 64阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]  
设4个数组：  
a\[i\]表示第i行的纵坐标为多少  
b\[i\]表示第i列有没有被占用，1占用，0，没占用  
c\[i\]记录左下到右上的对角线：我们可以发现，如果两个点都在左下到右上的线上，那么他们的横、纵坐标相加的值相等;  
d\[i\]记录右下到左上的对角线：我们可以发现，如果两个点都在右下到左上的线上，那么他们的横、纵坐标相减的值相等，但有可能是负数，所以我们偏移n

这样设4个数组，我们每次判断即可，不用再循环一次了。

import java.util.Scanner;
    
    public class 八黄后 {
        
        static int sum,n;
        static int a[]=new int[30];
        static int b[]=new int[30];
        static int c[]=new int[30];
        static int d[]=new int[30];
        static void dfs(int h){
        
            if (h==n+1){
        
                sum++;
                 if(sum<=3){
        
                    for (int i = 1; i <n ; i++) {
        
                        System.out.print(a[i]+" ");
                    }
                    System.out.print(a[n]);
                    System.out.println();
                }
                return;
            }
            for (int j = 1; j <=n ; j++) {
        
                if(b[j]!=1&&c[h+j]!=1&&d[h-j+n]!=1){
        
                    a[h]=j;//表示第h行的纵坐标为多少
                    b[j]=1;//表示第i列有没有被占用，1占用，0，没占用
                    c[h+j]=1;//左下到右上的对角线被占
                    d[h-j+n]=1;//右下到左上的对角线被占
                    dfs(h+1);//深搜
                    b[j]=0;//回溯
                    c[h+j]=0;
                    d[h-j+n]=0;
                }
            }
    
        }
        public static void main(String[] args) {
        
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
            sum=0;
            dfs(1);
            System.out.println(sum);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200310080805149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200226142849211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70