51 N queens

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

做了无数次了，主要是检查valid的方法

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[][] board = new int[n][n];
        List<List<String>> ans = new ArrayList<>();
        dfs(board, 0, ans);
        return ans;
    }
    private void dfs(int[][] board, int row, List<List<String>> ans) {
        if (row == board.length) {
            ans.add(getAns(board));
        }
        int n = board.length;
        for (int i = 0; i < n; i++) {
            if (isValid(board, row, i)) {
                board[row][i] = 1;
                dfs(board, row + 1, ans);
                board[row][i] = 0;
            }
        }
    }
    private boolean isValid(int[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) return false;
        }
        int i = row - 1;
        int j = col - 1;
        int n = board.length;
        while (i >= 0 && j >= 0) {
            if (board[i][j] == 1) return false;
            i--;
            j--;
        }
        i = row - 1;
        j = col + 1;
        while (i >= 0 && j < n) {
            if (board[i][j] == 1) return false;
            i--;
            j++;
        }
        return true;
    }
    private List<String> getAns(int[][] board) {
        List<String> ans = new ArrayList<>();
        for (int[] row : board) {
            StringBuilder sb = new StringBuilder();
            for (int cell : row) {
                if (cell == 1) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            ans.add(sb.toString());
        }
        return ans;
    }
}