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{// 存放最终结果// 每一个 ListString 表示一种棋盘摆放方案ListListStringresultnewArrayList();// 当前棋盘路径// 每个 String 表示棋盘的一行ListStringpathnewArrayList();/** * 判断当前位置是否可以放皇后 * * 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){// 保存当前方案result.add(newArrayList(path));return;}/** * 枚举当前行的每一列 */for(inti0;in;i){/** * 判断当前位置是否合法 */if(isValid(n,row,i,chessboard)){// 放置皇后chessboard[row][i]Q;// 当前行加入路径path.add(newString(chessboard[row]));// 递归下一行backtracking(n,row1,chessboard);// 回溯移除皇后chessboard[row][i].;// 删除当前行path.remove(path.size()-1);}}}publicListListStringsolveNQueens(intn){/** * 初始化棋盘 * * . 表示空位 */char[][]chessboardnewchar[n][n];for(inti0;in;i){for(intj0;jn;j){chessboard[i][j].;}}// 从第0行开始回溯backtracking(n,0,chessboard);returnresult;}}