算法:递归-八皇后问题

算法 大约 1123 字

说明

一维数组即可表示。

数组的索引i表示第i+1行皇后。即:索引从0开始,表示第1行。

元素的值arr[i]=valuevalue表示第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()
}
阅读 168 · 发布于 2021-02-01

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批