LeetCode.51.N皇后（困难）

题目

LeetCode.51.N皇后（困难）

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

提示：

• 1 <= n <= 9
• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

题解

• 尝试所有摆放的可能，用回溯。
• 每一行都放一个皇后，需要遍历所有行。
• 但是每一行放哪一列不确定，就遍历所有的列，都尝试一遍。
• 所有行放完了，完成了一种放置结果，添加到结果集。

限制条件如何检查？

因为是从上到下放皇后的，当前行肯定没有其他皇后，只需检查当前列、左上方斜线、右上方斜线有没有放置过皇后，若有有放置过，当前行的当前列不能选择，得选择下一列。

标准的dfs，时间复杂度O(n!)。

class Solution {
    private lateinit var result: MutableList<List<String>>
    private lateinit var grid: Array<CharArray>

    /**
     * 理解题意是关键
     * 期盼上每一行每一列都只能有1个皇后
     */
    fun solveNQueens(n: Int): List<List<String>> {
        grid = Array(n) { CharArray(n) { '.' } }
        result = mutableListOf()
        backtrack(0)
        return result
    }

    private fun backtrack(r: Int) {
        val n = grid.size
        // 所有的行选择完了，n个皇后也摆放完了，可以添加结果了
        if (r == n) {
            val solution = grid.map { row -> row.joinToString("") }
            result.add(solution)
            return
        }

        // 在当前后的每一列都可以做出选择
        for (c in 0 until n) {
            if (!isValid(r, c)) continue
            grid[r][c] = 'Q'
            backtrack(r + 1)
            grid[r][c] = '.'
        }
    }

    private fun isValid(r: Int, c: Int): Boolean {
        val n = grid.size
        // 检查第c列有没有皇后，有皇后了就不能选这列
        for (i in 0 until n) {
            if (grid[i][c] == 'Q') {
                return false
            }
        }

        // 斜着的也能走，要考虑斜着的四个方向，但其实我们选择的时候是从上往下选择的，所以只要考虑左上和右上的方向有没有皇后
        // 检查左上方有没有皇后
        var i = r - 1
        var j = c - 1
        while (i >= 0 && j >= 0) {
            if (grid[i][j] == 'Q') return false
            i--
            j--
        }
        // 检查右上方有没有皇后
        i = r - 1
        j = c + 1
        while (i >= 0 && j < n) {
            if (grid[i][j] == 'Q') return false
            i--
            j++
        }
        return true
    }

}