前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的51题。
问题描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
分析：
参考王晓东版的《计算机算法分析与设计》，N皇后为子集树问题。可以套用回溯法搜索子集树的算法框架。
可以用一维数组记录N皇后的结果，因为一行一列中有且仅有一个皇后。其中一维数组的下标可以表示成皇后所在的行号（或者列号），一维数组元素的值可以表示皇后所在的列号（或者行号）。最后输出的结果是string类型的二维数组，所以需要进行转化。
func printResult(retMatrix [][]int, n int) [][]string{
retStringArray := make([][]string, 0)
for i := 0; i < len(retMatrix); i++ {
retOne := make([]string, 0)
for j := 0; j < n; j++ {
singleLine := make([]rune, n)
pos := retMatrix[i][j]
for k := 0; k < pos; k++ {
singleLine[k] = '.'
}
singleLine[pos] = 'Q'
for k := pos+1; k < n; k++ {
singleLine[k] = '.'
}
retOne = append(retOne, string(singleLine))
}
retStringArray = append(retStringArray, retOne)
}
return retStringArray
}
func solveNQueens(n int) [][]string {
retMatrix := make([][]int, 0)
ret := make([]int, n)
backtrack(n, 0, ret, &retMatrix)
return printResult(retMatrix, n)
}
func place(k int, ret []int) bool {//约束条件
for i := 0; i < k; i++ {
x := ret[i] - ret[k]
y := i - k
if (x == y) || (x + y == 0) || (ret[i] == ret[k]) {
return false
}
}
return true
}
func backtrack(n int, index int,ret []int, retMatrix *[][]int) {
if index == n {//n代表递归层数
temp := append([]int{}, ret...)
*retMatrix = append(*retMatrix, temp)
return
}
for i := 0; i < n; i++ {//n代表的是子集树非叶子节点共有的叶子数，若0-1背包为2
ret[index] = i
if place(index, ret) {
backtrack(n, index+1, ret, retMatrix)
}
}
}
提交结果：
执行用时: 20 ms, 在N-Queens的Go提交中击败了49.06% 的用户
内存消耗: 7.1 MB, 在N-Queens的Go提交中击败了66.67% 的用户
总结：
勤思考。
结语
不管怎么样好好加油。
