题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：
输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

题目分析

DFS，按每一行进行枚举.

Java

private List<List<String>> ans = new ArrayList<>();

public List<List<String>> solveNQueens(int n) {
    dfs(new char[n][n], n, 0);
    return ans;
}

private void dfs(char[][] board, int n, int row) {
    if (row == n) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 0) {
                    board[i][j] = '.';
                }
                sb.append(board[i][j]);
            }
            list.add(sb.toString());
        }
        ans.add(list);
        return;
    }

    // 枚举列号
    for (int col = 0; col < n; col++) {
        // 检查前面的行
        int pre;
        for (pre = 0; pre < row; pre++) {
            // 同一列有Q
            if (board[pre][col] == 'Q') {
                break;
            }
            // 对角线有Q
            int distance = row - pre;
            if ((col - distance >= 0 && board[pre][col - distance] == 'Q') || (col + distance < n && board[pre][col + distance] == 'Q')) {
                break;
            }
        }
        if (pre < row) {
            continue;
        }

        // 符合条件
        board[row][col] = 'Q';
        dfs(board, n, row + 1);
        board[row][col] = '.';

    }
}

Kotlin

private val ans = ArrayList<List<String>>()

fun solveNQueens(n: Int): List<List<String>> {
    dfs(Array(n) { CharArray(n) { '.' } }, n, 0)
    return ans
}

private fun dfs(board: Array<CharArray>, n: Int, row: Int) {
    if (row == n) {
        val list = ArrayList<String>()
        for (charArray in board) {
            val sb = StringBuilder()
            for (ch in charArray) {
                sb.append(ch)
            }
            list.add(sb.toString())
        }
        ans.add(list)
        return
    }

    for (col in 0 until n) {
        var valid = true
        for (pre in 0 until row) {
            // 同一列
            if (board[pre][col] == 'Q') {
                valid = false
                break
            }
            // 对角线
            val distance = row - pre
            if ((col - distance >= 0 && board[pre][col - distance] == 'Q') || (col + distance < n && board[pre][col + distance] == 'Q')) {
                valid = false
                break;
            }
        }
        if (valid) {
            board[row][col] = 'Q'
            dfs(board, n, row + 1)
            board[row][col] = '.'
        }
    }
}