共计 1075 个字符,预计需要花费 3 分钟才能阅读完成。
题目起源:Leetcode 51 题
最近在学习 go 语言,用 go 解决了个 N 皇后问题,这里分享下心得。
N 皇后是经典的回溯问题,解决这种问题,都是有特定模板的,这里我写下回溯法的伪代码模板。
def backTrace():
if 完结条件
执行相应操作
return
for i in 条件:
做抉择
backTrace()
撤销抉择
而后的话,只需拿模板往上套就行。
我的解题思路是:从上往下往棋盘中一行一行的填充,填充时对应模板中的做抉择,即抉择在一行中某一列地位填充上 Q 皇后,而后进入递归,前面紧跟着撤销之前抉择的地位。进入递归后,首先是进行地位的断定,即判断下面、左上、右上这几个地位有没有抵触,如果有就立刻完结。而后判断是否是最初一行,如果是,那么就将这个后果插入到存储最终后果的切片中。
上面是代码:
import "fmt"
var Res [][]string
var N int
func Recursion(mid []string, i,j int){
// mid 代表存储两头后果的 string 切片,i 代表棋盘的第几行,j 代表第几列曾经有 Q 了
// 对插入的这个地位左上、上、右上进行判断,是否存在皇后
// 先判断上
for idx:=i-1;idx>=0;idx--{if mid[idx][j] == 'Q'{return}
}
// 再判断左上
for x,y:=i-1,j-1;x>=0&&y>=0;x,y=x-1,y-1{if mid[x][y] == 'Q'{return}
}
// 再判断右上
for x,y:=i-1,j+1;x>=0&&y<N;x,y=x-1,y+1{if mid[x][y] == 'Q'{return}
}
if i==N-1{
// 遍历过了最初一行,间接完结
Res = append(Res, mid)
return
}
subMid := make([]byte, 0)
for idx := 0; idx < N; idx++ {subMid = append(subMid, '.')
}
for idx:=0;idx<N;idx++{subMid[idx] = 'Q'
length := len(mid)
Recursion(append(mid[:length:length], string(subMid)), i+1, idx)
subMid[idx] = '.'
}
}
func solveNQueens(n int) [][]string {
N = n
Res = make([][]string, 0)
Recursion(make([]string, 0), -1,-1)
return Res
}
func main() {res := solveNQueens(4)
fmt.Println(res)
}
正文完