【leetcode hot 100 51】N皇后

解法一：（基于集合的回溯）我们从第一行开始寻找，找每一行皇后应该放在第几列。每次找到都用Set记录已经用过的列和对角，其中从左到右向下的对角（行-列相同），右到左向下的对角（行+列相同）。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 我们从第一行开始寻找，找每一行皇后应该放在第几列
        List<List<String>> result = new ArrayList<List<String>>();
        int[] queue = new int[n]; // queue[i]表示第i行的皇后放在第queue[i]列
        Set<Integer> columes = new HashSet<>(); // 用于登记已经用了哪一列
        Set<Integer> diagonal1 = new HashSet<>(); // 用于登记已经用了哪从左到右向下的对角（行-列相同）
        Set<Integer> diagonal2 = new HashSet<>(); // 用于登记已经用了哪从右到左向下的对角（行+列相同）
        backtrace(result, queue, n, 0, columes, diagonal1, diagonal2); // 0表示从第0行开始找
        return result;
    }

    public void backtrace(List result, int[] queue, int n, int row, Set columes, Set diagonal1, Set diagonal2){
        if(row == n){
            List<String> temp = generateResult(queue, n);
            result.add(temp);
            return;
        }
        // 找row行皇后应该放哪：应该循环每一列
        for(int col=0; col<n; col++){
            if(columes.contains(col)){
                // 这一列已经存在了
                continue; // return；
            }
            if(diagonal1.contains(row-col)){
                // 这一对角已经存在了
                continue; // return；
            }
            if(diagonal2.contains(row+col)){
                // 这一对角已经存在了
                continue; // return；
            }
            // 找到列+两对角都不存在的列
            columes.add(col);
            diagonal1.add(row-col);
            diagonal2.add(row+col);
            queue[row] = col;

            backtrace(result, queue, n, row+1, columes, diagonal1, diagonal2);

            // 回溯
            columes.remove(col);
            diagonal1.remove(row-col);
            diagonal2.remove(row+col);
            queue[row] = -1;
        }
    }

    public List<String> generateResult(int[] queue, int n){
        List<String> temp = new ArrayList<String>();
        for(int i=0; i<n; i++){
            char[] charTemp = new char[n];
            Arrays.fill(charTemp, '.');
            charTemp[queue[i]] = 'Q';
            temp.add(new String(charTemp));
        }
        return temp;
    }
}

注意：

• queue[i]表示第i行的皇后放在第queue[i]列
• 从左到右向下的对角（行-列相同），右到左向下的对角（行+列相同）
• Arrays.fill(charTemp, '.')表示用 '.' 填充charTemp数组