问题： 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
规则：皇后不能出现在同行同列以及同斜线上，所以要一套判断规则来剔除不符合的情况。
解答：回溯算法
在第i行摆放了棋子时候，可以选择摆放第i+1行，也可以撤销第i行的摆放，将第i行的棋子放在之前位置的后面。因为具有回溯的这么一个过程，所以可以使用回溯算法解决本题。
List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { List<String> solution = new ArrayList<>(); StringBuilder sb = new StringBuilder(""); for (int i = 0; i < n; i++) { sb.append("."); } for (int i = 0; i < n; i++) { solution.add(sb.toString()); } backTrace(solution, 0, n); return res; } private void backTrace(List<String> solution, int index, int n) { if (index == n) { res.add(new ArrayList<>(solution)); return; } for (int i = 0; i < n; i++) { //如果当前位置能放，那就将该位置的"."替换为"Q" if (isValid(index, i, solution, n)) { //做出选择 StringBuilder temp = new StringBuilder(solution.get(index)); temp.setCharAt(i, 'Q'); solution.set(index, temp.toString()); //回溯 backTrace(solution, index + 1, n); //恢复现场 temp = new StringBuilder(solution.get(index)); temp.setCharAt(i, '.'); solution.set(index, temp.toString()); } } } private boolean isValid(int index, int i, List<String> solution, int n) { //不同列不能相同 for (int row = 0; row < index; row++) { if (solution.get(row).charAt(i) == 'Q') return false; } //左对角 for (int row = index - 1, col = i - 1; row >= 0 && col >= 0; row--, col--) { if (solution.get(row).charAt(col) == 'Q') return false; } //右对角 for (int row = index - 1, col = i + 1; row >= 0 && col < n; row--, col++) { if (solution.get(row).charAt(col) == 'Q') return false; } return true; } public static void main(String[] args) { System.out.println(new Test51().solveNQueens(4)); }