LeetCode--52. N皇后 II（回溯算法）
52. N皇后 II题目描述n 皇后问题研究的是如何将n个皇后放置在n × n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回n 皇后问题不同的解决方案的数量。示例 1输入n 4 输出2 解释如上图所示4 皇后问题存在两个不同的解法。示例 2输入n 1 输出1提示1 n 9代码classSolution{// 记录最终合法方案总数inttotal0;/** * 判断当前位置是否可以放皇后 * * param n 棋盘大小 * param row 当前行 * param column 当前列 * param chessboard 当前棋盘状态 */publicbooleanisValid(intn,introw,intcolumn,char[][]chessboard){/** * 检查当前列上方是否已有皇后 * * 因为是按行递归 * 当前行以下还没有放皇后 * 所以只需要检查上方即可 */for(inti0;irow;i){if(chessboard[i][column]Q){returnfalse;}}/** * 检查左上对角线\ */introw1row;intcolumn1column;while(row1--0column1--0){if(chessboard[row1][column1]Q){returnfalse;}}/** * 检查右上对角线/ */row1row;column1column;while(row1--0column1n-1){if(chessboard[row1][column1]Q){returnfalse;}}// 当前位置合法returntrue;}/** * 回溯函数 * * param n 棋盘大小 * param row 当前处理到第几行 * param chessboard 当前棋盘状态 */publicvoidbacktracking(intn,introw,char[][]chessboard){/** * 终止条件 * * row n * 说明前 n 行已经全部放置完成 */if(rown){// 找到一种合法方案total;return;}/** * 枚举当前行每一列 */for(inti0;in;i){/** * 如果当前位置合法 */if(isValid(n,row,i,chessboard)){// 放置皇后chessboard[row][i]Q;// 递归下一行backtracking(n,row1,chessboard);// 回溯恢复现场chessboard[row][i].;}}}publicinttotalNQueens(intn){/** * 初始化棋盘 * * . 表示空位 */char[][]chessboardnewchar[n][n];for(inti0;in;i){for(intj0;jn;j){chessboard[i][j].;}}// 从第0行开始回溯backtracking(n,0,chessboard);returntotal;}}
