LeetCode--51. N皇后（回溯算法）
51. N皇后
题目描述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数n，返回所有不同的n 皇后问题的解决方案。
每一种解法包含一个不同的n 皇后问题的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[["Q"]]提示：
1 <= n <= 9
代码
classSolution{// 存放最终结果// 每一个 List<String> 表示一种棋盘摆放方案List<List<String>>result=newArrayList<>();// 当前棋盘路径// 每个 String 表示棋盘的一行List<String>path=newArrayList<>();/** * 判断当前位置是否可以放皇后 * * @param n 棋盘大小 * @param row 当前行 * @param column 当前列 * @param chessboard 当前棋盘 */publicbooleanisValid(intn,introw,intcolumn,char[][]chessboard){/** * 检查同行、同列是否有皇后 */for(inti=0;i<row;i++){// 纵向检查if(chessboard[i][column]=='Q')returnfalse;}/** * 检查主对角线（\） */// 左上方向introw1=row;intcolumn1=column;while(row1-->0&&column1-->0){if(chessboard[row1][column1]=='Q')returnfalse;}/** * 检查副对角线（/） */// 右上方向row1=row;column1=column;while(row1-->0&&column1++<n-1){if(chessboard[row1][column1]=='Q')returnfalse;}// 当前位置合法returntrue;}/** * 回溯函数 * * @param n 棋盘大小 * @param row 当前处理到第几行 * @param chessboard 当前棋盘状态 */publicvoidbacktracking(intn,introw,char[][]chessboard){/** * 终止条件 * * row == n * 说明前 n 行已经全部放置完成 */if(row==n){// 保存当前方案result.add(newArrayList<>(path));return;}/** * 枚举当前行的每一列 */for(inti=0;i<n;i++){/** * 判断当前位置是否合法 */if(isValid(n,row,i,chessboard)){// 放置皇后chessboard[row][i]='Q';// 当前行加入路径path.add(newString(chessboard[row]));// 递归下一行backtracking(n,row+1,chessboard);// 回溯：移除皇后chessboard[row][i]='.';// 删除当前行path.remove(path.size()-1);}}}publicList<List<String>>solveNQueens(intn){/** * 初始化棋盘 * * '.' 表示空位 */char[][]chessboard=newchar[n][n];for(inti=0;i<n;i++){for(intj=0;j<n;j++){chessboard[i][j]='.';}}// 从第0行开始回溯backtracking(n,0,chessboard);returnresult;}}