n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q‘ 和 ‘.‘ 分别代表了皇后和空位。
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
八皇后的一般思路就是回溯了。
class Solution { private List<List<String>> output = new ArrayList<>(); int[] rows; int[] mains; int[] secondary; int[] queens; int n; public List<List<String>> solveNQueens(int n) { rows = new int[n]; mains = new int[2 * n - 1]; secondary = new int[2 * n - 1]; queens = new int[n]; this.n = n; backtrack(0); return output; } private void backtrack(int row) { if (row >= n) { return; } for (int col = 0; col < n; col++) { if (isNotUnderAttack(row, col)) { placeQueen(row, col); if (row == n - 1) { addSolution(); } backtrack(row + 1); removeQueen(row, col); } } } private void addSolution() { List<String> solution = new ArrayList<>(); for (int i = 0; i < n; i++) { int col = queens[i]; StringBuilder sb = new StringBuilder(); for (int j = 0; j < col; j++) { sb.append("."); } sb.append("Q"); for (int j = 0; j < n - col - 1; j++) { sb.append("."); } solution.add(sb.toString()); } output.add(solution); } private void removeQueen(int row, int col) { queens[row] = 0; rows[col] = 0; mains[row - col + n - 1] = 0; secondary[row + col] = 0; } private void placeQueen(int row, int col) { queens[row] = col; rows[col] = 1; mains[row - col + n - 1] = 1; secondary[row + col] = 1; } private boolean isNotUnderAttack(int row, int col) { int res = rows[col] + mains[row - col + n - 1] + secondary[row + col]; return res == 0; } }
end
原文：https://www.cnblogs.com/CherryTab/p/12392584.html