【回溯】BM59-N皇后问题

思路

求解代码

privateintans=0;/** * 解决N皇后问题的主方法，初始化棋盘并调用回溯方法 * * @param n 棋盘的大小和皇后的数量 * @return 返回解的总数 */publicintNqueen(intn){// 创建一个长度为n的数组pos，用于记录每一行中皇后所在的列位置// 初始时所有位置都设为0int[]pos=newint[n];Arrays.fill(pos,0);// 调用回溯方法开始求解N皇后问题backtrack(n,0,pos);// 返回最终找到的解的总数returnans;}/** * 检查在指定位置放置皇后是否有效 * * @param pos 数组，记录每一行皇后所在的列位置 * @param row 当前行号 * @param col 当前列号 * @return 如果当前位置可以放置皇后则返回true，否则返回false */privatebooleanisValid(int[]pos,introw,intcol){// 遍历之前所有已经放置了皇后的行for(inti=0;i<row;i++){// 检查是否有同列的皇后，或者两个皇后是否在同一对角线上if(pos[i]==col||Math.abs(row-i)==Math.abs(col-pos[i])){// 如果冲突，返回falsereturnfalse;}}// 如果没有冲突，返回truereturntrue;}/** * 使用回溯算法解决N皇后问题 * * @param n 棋盘大小，即n×n的棋盘 * @param row 当前行号，从0开始 * @param pos 记录每行皇后放置的位置，pos[i]表示第i行皇后所在的列 */privatevoidbacktrack(intn,introw,int[]pos){// 如果已经处理完所有行，说明找到了一个有效的解if(row==n){ans++;// 解的数量加1return;// 返回上一行}// 遍历当前行的所有列for(inti=0;i<n;i++){// 检查在当前行的第i列放置皇后是否有效if(isValid(pos,row,i)){pos[row]=i;// 将皇后放置在当前行的第i列// 递归处理下一行backtrack(n,row+1,pos);}// 如果无效，则尝试下一列}}

小贴士

1.pos[i]==col||Math.abs(row-i)==Math.abs(col-pos[i]这个校验逻辑为什么是这样？

主要是因为回溯是逐行递归，一行只放一个皇后，天然规避同行冲突，所以这里没有写i==row;

然后利用了对角线的数学判定公式：

两个皇后的【行号差值的绝对值】 = 【列号差值的绝对值】➡️必在同一条对角线上

2.在 N 皇后问题中，行不会重复选（遍历规则）、列不会重复选（校验规则），used数组的使命已经被替代，所以不需要写used数组。

3.本题的回溯为什么不需要显式写撤销代码？

做选择时只修改了当前层级专属的变量，且变量会被下一次循环自动覆盖，覆盖之后，旧值就消失了，相当于恢复成了原始状态。