class Solution {
    // 记录总皇后数
    private var totalQueues = 0
    // 记录已经放置的皇后位置
    private lateinit var queens: IntArray
    // 记录可行的方案
    private lateinit var solutions: MutableList<List<String>>

    fun solveNQueens(n: Int): List<List<String>> {
        solutions = mutableListOf()
        totalQueues = n
        queens = IntArray(n)
        backTrack(0)
        return solutions
    }

    /**
     * 放置第 current 个皇后
     */
    private fun backTrack(current: Int) {
        // 如果已经放下了最后一个皇后，表明此方案可行，记录此方案
        if (current == totalQueues) {
            val queenList = mutableListOf<String>()
            for (i in 0 until totalQueues) {
                val stringBuilder = StringBuilder()
                for (j in 0 until totalQueues)
                    stringBuilder.append(if (queens[i] == j) "Q" else ".")
                queenList.add(stringBuilder.toString())
            }
            solutions.add(queenList)
            return
        }
        // 还未到最后一行，尝试放置皇后
        for (position in 0 until totalQueues) {
            queens[current] = position
            // 如果能放在此位置，继续放置下一个皇后
            if (canPlace(current)) backTrack(current + 1)
            // 否则继续循环，尝试放置在另一个位置。这里是回溯的精髓，有一个回到上一步的操作
        }
    }

    /**
     * 判断皇后能否放在此位置
     */
    private fun canPlace(position: Int): Boolean {
        // 判断是否与之前放置的皇后冲突
        for (before in 0 until position) {
            if (queens[before] == queens[position]
                || Math.abs(queens[position] - queens[before]) == Math.abs(position - before)
            )
                return false
        }
        return true
    }

1.用queens[current]=position表示第current个皇后放在第current行，第position列。

2.由于每一行上只有一个皇后，所以皇后在横向不会冲突。

3.先尝试将皇后放在position位置上，再判断这个皇后放在这里会不会和之前的皇后冲突。判断方法为：

if (queens[before] == queens[position] 
|| Math.abs(queens[position] - queens[before]) == Math.abs(position - before))
                return false

（1）如果queens[before] == queens[position]，表示竖向冲突

（2）如果Math.abs(queens[position] - queens[before]) == Math.abs(position - before))，表示斜线上冲突。

4.如果这个皇后没有和之前放置的所有皇后冲突，表示此皇后可以放在这里，继续放下一个皇后。

5.如果这个皇后和之前放置的皇后冲突，则回到上一步，尝试将此皇后放置在下一个position位置上。这个回到上一步的操作就是回溯算法的精髓。

6.如果放完所有皇后都没有冲突，表示此方案可行。根据queens数组拼接答案即可。