N皇后问题

题目描述：

N皇后问题_牛客网
N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列也不再同一条斜线上，求给一个整数n，返回n皇后的摆法。

输入描述：

输入一个整数，代表n(1≤n≤14)

输出描述：

输出一个整数，代表n皇后的种数。

输入示例1：

1

输出示例1：

1

输入示例2：

8

输出示例2：

92

题目分析：

这道题呢，典型的递归回溯。（虽然典型，但是我不会啊哈哈。）我的理解呢，就是一行一行的去递归求解，对于每行的列数据挨个去尝试，当然啦，尝试的时候要标志哪些列、对角线不能再放。尝试完之后要把之前的标志清掉，便于下个可能解的递归。具体代码如下~

代码实现：

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main{
    private static int count;
    private static boolean[] markcol;
    private static boolean[] mark45;
    private static boolean[] mark135;
    private static int n;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        count=0;
        boolean[][] grid=new boolean[n][n];
        markcol=new boolean[n];
        mark45=new boolean[2*n-1];
        mark135=new boolean[2*n-1];
        backtracking(0);
        System.out.println(count);
    }
    
    public static void backtracking(int row){
        if(row==n){
            count++;
            return;
        }
        for(int col=0;col<n;col++){
            if(markcol[col]||mark45[row+col]||mark135[n-1-row+col])
                continue;
            markcol[col]=mark45[row+col]=mark135[n-1-row+col]=true;
            backtracking(row+1);
            markcol[col]=mark45[row+col]=mark135[n-1-row+col]=false;
        }
    }
}