設(shè)計(jì)一種算法，打印 N 皇后在 N × N 棋盤上的各種擺法刺桃，其中每個(gè)皇后都不同行、不同列吸祟，也不在對(duì)角線上瑟慈。這里的“對(duì)角線”指的是所有的對(duì)角線，不只是平分整個(gè)棋盤的那兩條對(duì)角線屋匕。
注意：本題相對(duì)原題做了擴(kuò)展
示例:
輸入：4
輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋: 4 皇后問題存在如下兩個(gè)不同的解法葛碧。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/eight-queens-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)过吻，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處进泼。
Kotlin 解決
fun main() {
println(
Solution().solveNQueens(4)
)
}
class Solution {
var N = 0 // 替代n，棋盤的大小 [0...n-1]
var board = ArrayList<StringBuilder>()// 棋盤
var recordList = ArrayList<Point>() // 記錄皇后的位置纤虽，用于判斷能否放置皇后
private val result = ArrayList<ArrayList<String>>()// 存放結(jié)果
fun solveNQueens(n: Int): List<List<String>> {
initBoard(n) // 初始化棋盤
_solveNQueens(0)
return result
}
// 回溯法
private fun _solveNQueens(colum: Int) {
if (colum > N) {
result.add(ArrayList(board.map { it.toString() }))
return
}
for (row in 0..N) {// 當(dāng)前colum行乳绕，遍歷每一列，
if (isPlaced(colum, row)) {
board[colum][row] = 'Q'
recordList.add(Point(colum, row))
_solveNQueens(colum + 1)
recordList.removeAt(recordList.lastIndex)
board[colum][row] = '.'
}
}
}
// 是否滿足皇后問題
private fun isPlaced(colum: Int, row: Int): Boolean {
if (recordList.isEmpty()) return false
for (l in recordList) {
if (l.row == row) return false
if (row - (colum - l.colum) == l.row) return false
if (row + (colum - l.colum) == l.row) return false
}
return true
}
// 初始化
private fun initBoard(n: Int) {
N = n - 1
val columnElement = StringBuilder()
// 初始化一行棋盤
for (i in 0..N) {
columnElement.append('.')
}
// 初始化整個(gè)棋盤
for (i in 0..N) {
board.add(StringBuilder(columnElement.toString()))
}
}
}
class Point constructor(var colum: Int, var row: Int) {
override fun toString(): String {
return "Point(colum=$colum, row=$row)"
}
}
遇到的問題：
- Kotlin 傳參數(shù)與Java一樣是引用傳遞逼纸，初始化
map時(shí)洋措，沒有 new 對(duì)象。
解決：保存結(jié)果應(yīng)該創(chuàng)建新對(duì)象result.add(ArrayList(map.map { it.toString() }))
