DFS回溯法解决N皇后问题

思路：因为每一行有n个位置可放置皇后（不考虑合不合理），所以此问题可以抽象出一个n+1层（含根节点）的n叉树。然后对该树进行剪枝（DFS回溯）即可求出可行解。

手撸代码：

import java.util.Arrays;
import java.util.Scanner;

public class NQueens {
	public static int count=0;//可行解数量
	//判断row行,col列是否可放皇后
	public boolean check(int row,int col,int n,int[] queue) {
		for (int i = 0; i < row; i++) {
			//在一对角线上，禁止放皇后
			if(Math.abs(i-row)==Math.abs(queue[i]-col))return false;
		}
		return true;
	}
	public void calNQueens(int row,int n,int[] queue,boolean[] hasuse) {
		if(row==n){//所有行都走完了，是可行解
			count++;
			return;
		}
		//依次检测当前行(row)的每一列
		for(int col=0;col<n;col++){
			if (!hasuse[col]&&check(row, col, n, queue)) {
				hasuse[col]=true;
				queue[row]=col;
				calNQueens(row+1, n, queue, hasuse);
				//回溯
				hasuse[col]=false;
				queue[row]=-1;
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();//几皇后
		int[] queue=new int[n];//queue[i]=j表示i行j列为皇后位置
		Arrays.fill(queue, -1);
		boolean[] hasuse=new boolean[n];//表示这一列是否可用（即同一列是否有皇后）
		new NQueens().calNQueens(0, n, queue, hasuse);
		System.out.println(count);
	}
}

附：leetcode解法