n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例：
输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],
["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。
提示：
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
解答：
本次答案采用回溯框架，在该框架的基础上进行拓展。 vector<vector<string>> res; /* 输⼊棋盘边⻓ n，返回所有合法的放置 */ vector<vector<string>> solveNQueens(int n) { // '.' 表⽰空，'Q' 表⽰皇后，初始化空棋盘。 vector<string> board(n, string(n, '.')); backtrack(board, 0); return res; } // 路径：board 中⼩于 row 的那些⾏都已经成功放置了皇后 // 选择列表：第 row ⾏的所有列都是放置皇后的选择 // 结束条件：row 超过 board 的最后⼀⾏ void backtrack(vector<string>& board, int row) { // 触发结束条件 if (row == board.size()) { res.push_back(board); return; } int n = board[row].size(); for (int col = 0; col < n; col++) { // 排除不合法选择 if (!isValid(board, row, col)) continue; // 做选择 board[row][col] = 'Q'; // 进⼊下⼀⾏决策 backtrack(board, row + 1); // 撤销选择 board[row][col] = '.'; 回溯算法解题套路框架 54 } } 这部分主要代码，其实跟全排列问题差不多， isValid 函数的实现也很简 单： /* 是否可以在 board[row][col] 放置皇后？ */ bool isValid(vector<string>& board, int row, int col) { int n = board.size(); // 检查列是否有皇后互相冲突 for (int i = 0; i < n; i++) { if (board[i][col] == 'Q') return false; } // 检查右上⽅是否有皇后互相冲突 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') return false; } // 检查左上⽅是否有皇后互相冲突 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') return false; } return true; }本题答案
class Solution {
List<List<String>> res = new ArrayList<List<String>>();//定义全局变量 public List<List<String>> solveNQueens(int n) { char[][] board =new char[n][n]; //声明二维数组，用来存储选过的路径 for(int i = 0; i < n; i++){ for(int j = 0; j < n;j++){ board[i][j] = '.'; } } backtrack(res,board,0); return res; } public void backtrack(List<List<String>> res,char[][] board,int row){ if(board.length == row){ res.add(toAyyayList(board)); return ; } int n = board[row].length; for(int col = 0; col < n;col++){ if(!isValid(board,row,col)) continue; board[row][col] = 'Q'; //选择 backtrack(res,board,row + 1); board[row][col] = '.'; //取消选择 } } public boolean isValid(char[][] board, int row, int col){ int n = board.length; for(int i = 0; i < n; i++){ if(board[i][col] == 'Q') return false; } for(int i = row - 1,j = col - 1; i >=0 && j >= 0; i--,j--){ //查看左上方的斜线是不是有皇后 if(board[i][j] == 'Q') return false; } for(int i = row - 1, j = col + 1; i >=0 && j < n;i--,j++){//查看右上方的斜线是不是有皇后 if(board[i][j] == 'Q') return false; } return true; } public List<String> toAyyayList(char[][] board){ //将数组转换为List List<String> ans = new ArrayList<>(); for(int i = 0; i < board.length;i++){ ans.add(new String(board[i])); } return ans; }}
回溯算法组合问题
