leetcode51. N 皇后（回溯算法）

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例：

输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],

["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。

代码

class Solution { List<List<String>> resss=new ArrayList<>(); public List<List<String>> solveNQueens(int n) { getNQueens(n,new ArrayList<>()); return resss; } public void getNQueens(int n,List<String> temp) { if(temp.size()==n) resss.add(new ArrayList(temp)); char[] chars=new char[n]; Arrays.fill(chars,'.'); for(int i=0;i<n;i++)//遍历该行的所有列 { if(checkQueens(n,temp,i)) { chars[i]='Q';//放置 temp.add(String.valueOf(chars)); getNQueens(n,temp); chars[i]='.';//回溯 temp.remove(temp.size()-1); } } } public boolean checkQueens(int n,List<String> temp,int col) {//判断能否放置 int step=1,r=temp.size(); while (r-step>=0) { if(temp.get(r-step).charAt(col)=='Q') return false; if(col+step<n&&temp.get(r-step).charAt(col+step)=='Q') return false; if(col-step>=0&&temp.get(r-step).charAt(col-step)=='Q') return false; step++; } return true; } }