51. N-Queens

class Solution {
    private Set<Integer> rowsWithQueen = new HashSet<>();
    private Set<Integer> colsWithQueen = new HashSet<>();
    private Set<Integer> diagWithQueen = new HashSet<>();
    private Set<Integer> antiWithQueen = new HashSet<>();
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(board, 0);
        return ans;
    }

    private void backtrack(char[][] board, int row) {
        if (row == board.length) {
            ans.add(createBoard(board));
            return;
        }
        for (int i = 0; i < board.length; i++) {
            if (isValidPosition(row, i)) {
                addQueen(row, i);
                board[row][i] = 'Q';
                backtrack(board, row + 1);
                board[row][i] = '.';
                removeQueen(row, i);
            }
        }
    }

    private boolean isValidPosition(int row, int col) {
        return !rowsWithQueen.contains(row) && !colsWithQueen.contains(col) && !diagWithQueen.contains(row - col)
                && !antiWithQueen.contains(row + col);
    }

    private void addQueen(int row, int col) {
        rowsWithQueen.add(row);
        colsWithQueen.add(col);
        diagWithQueen.add(row - col);
        antiWithQueen.add(row + col);
    }

    private void removeQueen(int row, int col) {
        rowsWithQueen.remove(row);
        colsWithQueen.remove(col);
        diagWithQueen.remove(row - col);
        antiWithQueen.remove(row + col);
    }

    private List<String> createBoard(char[][] board) {
        List<String> newBoard = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String currRow = new String(board[i]);
            newBoard.add(currRow);
        }
        return newBoard;
    }
}

N皇后, 很经典的回溯. 关键点在于同一个diagonal线上的row - col的值是定值, 因为往左上或者右下移动, row和col是同时增加的. 因此二者的差相同. 同一个anti- diagonal的线上的row + col是定值, 因为往左下和右上, 一个值增加另一个值减少. 比如去右上的话row减小但是col增加. 这是关键. 然后这道题就简单了.

时间复杂度: O(N!)
空间复杂度: O(N^2)

具体见https://leetcode.com/problems/n-queens/solution/