题解 | #N皇后问题#
N皇后问题
https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6
本题用递归求解（没有回溯）
题目要求，在n阶矩阵中，找到所有n个皇后摆放方式，摆放要求不能在同一直线1，同一列，以及同一对角线
刚刚开始刷递归以及dfs、回溯的题，在这里总结一下模板，
- 找出终结条件，即使递归结束的条件 本题为 行数递归到最后一行，代表选择完毕返回
- 剪枝是对于回溯过程中不合题目要求或者重复的选项进行删除
- 然后写一个for循环 ，在for循环中判断符合条件的情况，进行递归，递归后还原
本题思路很简单，请看代码注释
import java.util.*;
public class Solution {
//pos 数组 下标为 row 值为col
//pos[row] = col
//记录总摆放方法数
int count = 0;
//isValid 方法 判断当前行是否符合题目要求，不在同一行，不在同一列，不在对角线上
//注意循环以row为界，因为是判断是否和已经摆放了的位置有冲突
public boolean isValid(int[] pow,int row ,int col){
for (int i = 0; i < row; i++) {
if ( row == i || col == pow[i] ||
Math.abs(row - i) == Math.abs(col - pow[i])){
return false;
}
}
return true;
}
//递归
public void backTrace(int n ,int row ,int[] pos){
if (row == n){//终止条件，当递归到最后一行，已经全部摆放完成，返回
count++;
return;
}
for (int i = 0; i < n; i++) {
if (isValid(pos,row,i)){
pos[row] = i;//判断如果合法，那放入该位置
backTrace(n,row+1,pos);//寻找下一行是否有合法位置
}
}
}
public int Nqueen (int n) {
// write code here
int[] pos = new int[n];
backTrace(n,0,pos);
return count;
}
}
递归、回溯 文章被收录于专栏
dfs、bfs、剪枝等题解
