7.7 回溯和剪枝小结----n皇后问题（深搜）

剪枝：在递归之前进行if判断，如果不满足限定条件，则剪枝

例题：n皇后问题

例如4皇后问题（依次考虑每一列，分别将第一个皇后放在a[0][0]、a[0][1]、a[0][2]、a[0][3]）

可得最后只有良种合法的排列方式

伪代码

import java.util.Scanner;

public class Main {
	/*
	 * n皇后问题思路
	 * （1）首先针对每一行进行dfs深搜，用res[i]记录i行中存在元素的列
	 * （2）dfs搜索（i行，res）
	 *    出口：当前的行>总行数n，cnt++,记录解的总数
	 *    （2.1）针对i行，遍历所有列。
	 *    （2.2）如果j列合法，将该列记录下来，res[i]=j,继续dfs（i+1行，res）
	 *         合法：第i行不存在元素（不需要判断，行是从上到下依次查找的）
	 *             第j列不存在元素：遍历数组res，使得所有行中，res[k]!=j
	 *             主对角线不存在元素：k-res[k]!=i-j
	 *             副对角线不存在元素:k+res[k]!=i+j
	 * */
	static int[] res;//记录每一行中存在元素的列
	static int cnt=0;//记录解的总数
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();//n皇后
		res = new int[n];
		dfs(0);//从第0行开始
		System.out.println(cnt);
	}
	private static void dfs(int x) {
		if(x==n) {//已找到合法的解。下标从0开始
			cnt++;
			return;
		}
		for(int j=0;j<n;j++) {//找当前行合法的列
			if(check(x,j)) {//合法
				res[x]=j;//将结果存到数组res
				dfs(x+1);//继续遍历下一行
				res[x]=0;//回溯
			}
		}
		
	}
	private static boolean check(int x, int y) {
		for(int row=0;row<x;row++) {//注意：只需检查前面已经确定好的行
			if(res[row]==y || row-res[row]==x-y || row+res[row]==x+y) {
				return false;
			}
		}
		return true;
	}
	
}


           

（1）4皇后，2个解

（2）8皇后，92个解