P1219 八皇后 Checker Challenge(深度搜索dfs经典问题+回溯)

题目连接：P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 典型的深度优先搜索的问题----》先付代码再来跟新

java组代码

package PTACZW;
import java.util.Scanner;
import java.io.*;
import java.util.Set;
import java.util.HashSet;
import java.math.BigInteger;
import java.util.Collections;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
    static BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer tokenizer=new StringTokenizer("");
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
    static int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }
    static double Double() throws IOException
    {
        return Double.parseDouble(next());
    }
    static long nextlong() throws IOException
    {
        return Long.parseLong(next());
    }
    //快速输入输出模板
    static int[]a=new int[100];
    static int[]b=new int[100];
    static int[]c=new int[100];
    static int[]d=new int[100];
    static int total;
    static int n;
    public static void main(String[]args)throws IOException
    { 
        n=nextInt();
        dfs(1);
        pw.println(total);
        pw.flush();
        pw.close();
        
    }
    public static void show()
    {
        if(total<=2)
        {
            for(int i=1;i<=n;i++)
            {
                pw.print(a[i]+" ");
                pw.flush();
            }
            pw.println();
        }
        total++;
    }
    public static void dfs(int i)
    {
        if(i>n)
        {
            show();
        }
        else {
            for(int j=1;j<=n;j++)
            {
                if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0)
                {
                    a[i]=j;
                    b[j]=1;
                    c[i+j]=1;
                    d[i-j+n]=1;
                    dfs(i+1);
                    b[j]=0;
                    c[i+j]=0;
                    d[i-j+n]=0;
                }
            }
        }
    }
    
}