算法:递归-八皇后问题
算法 About 1,123 words说明
一维数组即可表示。
数组的索引i
表示第i+1
行皇后。即:索引从0
开始,表示第1
行。
元素的值arr[i]=value
,value
表示第value+1
列。若:arr[2]=4
,表示皇后放置在第3
行第4
列。
判断是否冲突
因为n
表示行,且每次递增,所以无需再判断是否再同一行。
// 判断摆放的皇后和已经摆放的皇后是否有冲突
func Judge(queue []int, n int) bool {
// 之前摆放的皇后依此判断
for i := 0; i < n; i++ {
// queue[i] == queue[n] 判断是否在同一列
// math.Abs(float64(n-i)) == math.Abs(float64(queue[n]-queue[i]) 判断是否在同一斜线
if queue[i] == queue[n] || math.Abs(float64(n-i)) == math.Abs(float64(queue[n]-queue[i])) {
return false
}
}
return true
}
递归检测
func Check(queue []int, n int) {
if n == 8 {
PrintQueue(queue)
return
}
for i := 0; i < 8; i++ {
queue[n] = i
if Judge(queue, n) {
Check(queue, n+1)
}
}
}
测试代码
func main() {
// [0, 1, 2, 3, 4, 5, 6, 7]
// 数组的索引i表示第i+1行皇后,索引从0开始,表示第1行
// 元素的值arr[i]=value,value表示第value+1列
queue := make([]int, 8)
Check(queue, 0)
fmt.Println(count)
}
var count = 0
func PrintQueue(queue []int) {
count++
for _, value := range queue {
fmt.Printf("%d\t", value)
}
fmt.Println()
}
Views: 1,957 · Posted: 2021-02-01
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...