DFS-8皇后

题目：8皇后

emample，n = 4时，输出为[[1, 3, 0, 2], [2, 0, 3, 1]]，说明4皇后有2中摆法。第一种摆法为
[1,3,0,2]即
第rowIndex = 0行，对应的Q在colIndex = 1列处，即第一行的Q在第二列

package com.mjp.ai.dfs;import com.google.common.collect.Lists;import java.util.List;
import java.util.stream.Collectors;/* Author：m* Date： 2023/04/17 22:57*/
public class Queen8 {public static void main(String[] args) {int n = 4;List<List<String>> result = searchQueen(n);System.out.println(result);}private static List<List<String>> searchQueen(int n) {if (n <= 3) {return Lists.newArrayList();}List<List<String>> result = Lists.newArrayList();List<Integer> colsCombine = Lists.newArrayList();recursion(result, colsCombine, n);return result;}private static void recursion(List<List<String>> result, List<Integer> colCombine, int n) {// 1.终止条件// 2.小集合添加至大集合（当n=4,colCombine为[1,3,0,2]时，说明找到了四皇后的一种摆法）if (n == colCombine.size()) {result.add(colCombine.stream().map(String::valueOf).collect(Collectors.toList()));return;}// 3.for循环for (int colIndex = 0; colIndex < n; colIndex++) {// 3.1去重或过滤（即欲放Q的当前行、当前列，同列、同递增斜线上、同递减斜线上均为Q时，才能在此处放Q）if (! allowQInThisRowIndexAndThisColIndex(colCombine, colCombine.size(), colIndex)) {continue;}// 3.2优化|剪枝// 3.3添加元素到小集合colCombine.add(colIndex);// 3.4递归recursion(result, colCombine, n);// 3.5回溯(小集合删除最后一个元素)colCombine.remove(colCombine.size() - 1);}}private static boolean allowQInThisRowIndexAndThisColIndex(List<Integer> colCombine, int thisRowIndex, int thisColIndex) {// 如果colCombine为[0]，则说明第rowIndex = 0行第colIndex = 0列有个Q// 我们判断Q是否能放在，thisRowIndex = 1行 thisColIndex = 列// 这里判断thisRowIndex行，thisColIndex列能否放Q，需要从rowIndex = 0一直判断到rowIndex = thisRowIndex- 1行，这些行上存放的Q是否和(thisRowIndex行，thisColIndex)存在以下三种冲突for (int rowIndex = 0; rowIndex < thisRowIndex; rowIndex++) {// rowIndex行对应的皇后所在列Integer getColIndexFromCombineByRowIndex = colCombine.get(rowIndex);// 1.判断冲突1：（thisRowIndex，thisColIndex）和已存在的皇后（rowIndex，getColIndexFromCombineByRowIndex）是否在同一列if (thisColIndex == getColIndexFromCombineByRowIndex) {return false;//如果存在冲突，则说明（thisRowIndex，thisColIndex）处不能放Q}// 2.判断冲突2：（thisRowIndex，thisColIndex）和已存在的皇后（rowIndex，getColIndexFromCombineByRowIndex）是否在同一条递减斜线上if (thisRowIndex - thisColIndex == rowIndex - getColIndexFromCombineByRowIndex) {return false;}// 3.判断冲突3：（thisRowIndex，thisColIndex）和已存在的皇后（rowIndex，getColIndexFromCombineByRowIndex）是否在同一条递增斜线上if (thisRowIndex + thisColIndex == rowIndex + getColIndexFromCombineByRowIndex) {return false;}}// 如果rowIndex = 0一直判断到rowIndex = thisRowIndex- 1行，这些行上存放的Q均不与(thisRowIndex行，thisColIndex)存在上述三种冲突，则说明此处可放Qreturn true;}
}