Problem

思路

参考小例子的walkthrough: https://www.youtube.com/watch?v=lTPIX2Ywo3U

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) return result;
        char[][] board = new char[n][n];
        for (int i = 0; i < board.length; i++) {
            Arrays.fill(board[i], '.');
        }
        dfs(board, result, 0);
        return result;
    }

    private void dfs (char[][] board, List<List<String>> result, int rowIndex) {
        if (rowIndex == board.length) {
            result.add(convert(board));
            return;
        }

        for (int i = 0; i < board.length; i++) {
            if (validate(board, rowIndex, i)) {
                board[rowIndex][i] = 'Q';
                dfs(board, result, rowIndex + 1);
                board[rowIndex][i] = '.';
            }
        }
    }

    private boolean validate (char[][] board, int x, int y) {
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == 'Q' && (i + j == x + y || i - j == x - y || j == y)) {
                    return false;
                }
            }
        }
        return true;
    }

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