题目: N皇后 II

分析

回溯法

n 皇后不能将皇后摆在同一行，所以回溯的时候可以每次从上到下遍历，每次在当前那一行寻找一个位置摆放皇后。此类问题可以使用回溯法解决。

回溯法通用模版如下：

回溯(路径, 选择列表){

如果到达终止条件：

将该路径加入结果列表；

循环选择列表:

  #将该选择添加到选择路径

  路径.添加(选择)

  回溯(路径, 选择列表)

  # 撤销选择

  路径.删除(选择）

}

终止条件是到达最后一行，

路径选择的时候不能出现和其他皇后在同一列或者对角线，所以每放置一个棋子，需要将这些不能摆放的位置提前计算好并且记录下来，后续在摆放皇后的时候，将这些位置剔除。

题解

class Solution {
    List<List<String>> solute(int n) {
        List<List<String>> results = new ArrayList<>();
        if (n <= 0) {
            return results;
        }
        
        search(results, new ArrayList<Integer>(), n);
        return results;
    }
    
    private void search(List<List<String>> results, List<Integer> cols, int n) {
        if (cols.size() == n) {
            results.add(Draw(cols));
            return;
        }
        
        for (int colIndex = 0; colIndex < n; colIndex++) {
            if (!isValid(cols, colIndex)) {
                continue;
            }
            cols.add(colIndex);
            search(results, cols, n);
            cols.remove(cols.size() - 1);
        }
    }
    
    private boolean isValid(List<Integer> cols, int col) {
        int row = cols.size();
        for (int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {
            if (cols.get(rowIndex) == col) {
                return false;
            }
            if (row + col == rowIndex + cols.get(rowIndex)) {
                return false;
            }
            if (row - col == rowIndex - cols.get(rowIndex)) {
                return false;
            }
        }
        return true;
    }
    
    private List<String> Draw(List<Integer> cols) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < cols.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cols.size(); j++) {
                sb.append(j == cols.get(i) ? 'Q' : '.');
            }
            result.add(sb.toString());
        }
        return result;
    }
}