【Check 65】2024-04-28 - 51. N 皇后

[larscheng]

51. N 皇后

[larscheng]

思路

回溯

• 皇后问题，皇后之间不能在同行、同列、同斜线
• 可以通过记录已经放置的皇后所在的行、列、斜线位置，来确定后续皇后位置
• 整个过程可以通过回溯完成
• 整数数组queens记录每1行皇后放置的列，Set1记录已放置皇后的列号，Set2记录左上到右下的斜线差值（同一斜线差值相同），Set3记录右上到左下的斜线和值（同一斜线和值相同）
• 最终queens收集到n个元素后，将其转化为结果集格式
• 回溯重置状态，继续收集其他情况

  代码

class Solution { public List<List> solveNQueens(int n) { List<List> result = new ArrayList<>(); //记录每行皇后所在的列 int[] queenIndex = new int[n]; Arrays.fill(queenIndex,-1); Set col = new HashSet<>(); //左上到右下（差恒等） Set xieXian1 = new HashSet<>(); //右上到左下（和恒等） Set xieXian2 = new HashSet<>();

    backtrack(result,queenIndex,n,0,col,xieXian1,xieXian2);

    return result;
}

private void backtrack(List<List<String>> result, int[] queenIndex, int n, int row, Set<Integer> col, Set<Integer> xieXian1, Set<Integer> xieXian2) {
    if (row==n){
        //根据queens数组转化为结果集
        result.add(createResult(queenIndex,n));
    }else {
        for (int i = 0; i < n; i++) {
            if (col.contains(i)){
                continue;
            }
            int diff = row - i;
            if (xieXian1.contains(diff)){
                continue;
            }
            int sum = row+i;
            if (xieXian2.contains(sum)){
                continue;
            }
            queenIndex[row] = i;
            col.add(i);
            xieXian1.add(diff);
            xieXian2.add(sum);
            //递归
            backtrack(result,queenIndex,n,row+1,col,xieXian1,xieXian2);
            //重置
            queenIndex[row] = -1;
            col.remove(i);
            xieXian1.remove(diff);
            xieXian2.remove(sum);
        }
    }
}

private List<String> createResult(int[] queenIndex, int n) {
    List<String> temp = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        char[] row = new char[n];
        Arrays.fill(row,'.');
        row[queenIndex[i]]='Q';
        temp.add(new String(row));
    }
    return temp;
}

}

### 复杂度
- 时间复杂度：O(N!)
- 空间复杂度：O(N)