n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例： 输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],
["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。
题解：利用回溯法遍历所有可能的情况，找出满足要求的情况，为了降低时间复杂度，我们可以在遍历的同时增加一些条件限制——每当我们在一个位置上放置了一个皇后时，我们可以将左斜线，右斜线，竖直方向和横向方向设置为“禁区”，即不能放皇后的位置，同时为了方便回溯，我们以横行为单位，从上到下的放置皇后，每一行放一个（由于n个皇后放置在n ∗ * ∗n的棋盘上，所以必定每一行放一个）。
import java.util.*; class Solution { private final Stack<Integer>stack=new Stack<>(); private final List<List<String>>res=new ArrayList<>(); public List<List<String>> solveNQueens(int n) { //二维布尔型数组记录不能放置皇后的位置 boolean[][] banned=new boolean[n][n]; DFS(banned,0); return res; } private void DFS(boolean[][]banned,int row){ if(stack.size()== banned.length){ getMap(stack,res); return; } Queue<int[]>save=new LinkedList<>(); int len=banned[row].length; //在每一行从左到右一次尝试放皇后 for(int i=0;i<len;i++){ if(!banned[row][i]) { stack.add(i); //将该行往下的每一行不能放置皇后的位置都设置为true for (int j = row; j < banned.length; j++) { if(!banned[j][i ]) { save.add(new int[]{j, i}); banned[j][i] = true; } int k = j - row; if (i + k < len&&!banned[j][i + k]) { save.add(new int[]{j, i + k}); banned[j][i + k] = true; } if (i - k >= 0&&!banned[j][i - k]) { save.add(new int[]{j, i - k}); banned[j][i - k] = true; } } DFS(banned, row + 1); stack.pop(); //还原 while(!save.isEmpty()){ int[] temp=save.poll(); banned[temp[0]][temp[1]]=false; } } } } private void getMap(Stack<Integer>stack,List<List<String>>res){ int size=stack.size(); List<String>map=new ArrayList<>(); for(int x:stack){ StringBuilder row=new StringBuilder(); for(int i=0;i<size;i++){ if(i!=x) row.append("."); else row.append("Q"); } map.add(row.toString()); } res.add(map); } }优化：我们可以通过棋盘的规律优化代码——其实棋盘上的每一条斜线都有一个该斜线独有的数字，比如同一条右斜线上的点横纵坐标的差为一个特有的常数，左斜线上的点横纵坐标上的和为一个特有常数，同时不同列可以用列标数字进行区分，所以，我们不必再用二维数组来保存不能放置皇后的点，直接用一个数字来代表某条斜线上或某列上不能放置皇后。
import java.util.*; class Solution { private final Stack<Integer>stack=new Stack<>(); private final List<List<String>>res=new ArrayList<>(); private final Set<Integer>left=new HashSet<>(); private final Set<Integer>right=new HashSet<>(); private final Set<Integer>down=new HashSet<>(); public List<List<String>> solveNQueens(int n) { boolean[][] banned=new boolean[n][n]; backTrace(0,n); return res; } private void backTrace(int column,int len){ if(stack.size()==len){ getMap(stack,res); return; } for(int i=0;i<len;i++){ int rightKey=column-i; int leftKey=column+i; if(!right.contains(rightKey)&&!left.contains(leftKey)&&!down.contains(i)) { right.add(rightKey); left.add(leftKey); down.add(i); stack.push(i); backTrace(column+1,len); right.remove(rightKey); left.remove(leftKey); down.remove(i); stack.pop(); } } } private void getMap(Stack<Integer>stack,List<List<String>>res){ int size=stack.size(); List<String>map=new ArrayList<>(); for(int x:stack){ StringBuilder row=new StringBuilder(); for(int i=0;i<size;i++){ if(i!=x) row.append("."); else row.append("Q"); } map.add(row.toString()); } res.add(map); } }