N皇后

https://leetcode.com/problems/n-queens/

image.png

   public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        char[][] queens = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                queens[i][j] = '.';
            }
        }

        this.queenHelper(0, queens, res);
        return res;
    }

    public void queenHelper(int curRow, char[][] queens, List<List<String>> res) {
        int n = queens.length;

        if (curRow == n) {
            res.add(this.construct(queens));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (queenValid(queens, curRow, i)) {
                queens[curRow][i] = 'Q';
                queenHelper(curRow + 1, queens, res);
                queens[curRow][i] = '.';
            }
        }
    }

    public Boolean queenValid(char[][] queens, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i][col] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (queens[i][j] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < queens.length; --i, ++j) {
            if (queens[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> res = new LinkedList<String>();
        for (int i = 0; i < board.length; i++) {
            String s = new String(board[i]);
            res.add(s);
        }
        return res;
    }