2021-02-16:n皇后问题。给定一个整数n，返回n皇后的摆法有多少种？

福大大架构师每日一题 · · 799 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福哥答案2021-02-16：

自然智慧即可。
1.普通递归。有代码。
需要判断同列和斜线。
2.位运算递归。有代码。
3.我的递归。有代码。
只需要判断斜线。

代码用golang编写，代码如下：

package main

import (
    "fmt"
    "time"
)

func main() {
    n := 12
    fmt.Println(n, "皇后问题")
    fmt.Println("------")
    now := time.Now()
    fmt.Println("1.普通递归：", num1(n))
    fmt.Println("时间：", time.Now().Sub(now))
    fmt.Println("------")

    now = time.Now()
    fmt.Println("2.位运算递归：", num2(n))
    fmt.Println("时间：", time.Now().Sub(now))
    fmt.Println("------")
    now = time.Now()
    fmt.Println("3.我的递归：", num3(n))
    fmt.Println("时间：", time.Now().Sub(now))
}
func num1(n int) int {
    if n < 1 {
        return 0
    }
    record := make([]int, n)
    return process1(0, record, n)
}
func process1(i int, record []int, n int) int {
    if i == n {
        return 1
    }
    res := 0
    for j := 0; j < n; j++ {
        if isValid(record, i, j) {
            record[i] = j
            res += process1(i+1, record, n)
        }
    }
    return res
}
func isValid(record []int, i int, j int) bool {
    for k := 0; k < i; k++ {
        if j == record[k] || abs(record[k]-j) == abs(i-k) {
            return false
        }
    }
    return true
}
func abs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

func num2(n int) int {
    if n < 1 || n > 32 {
        return 0
    }
    limit := -1
    if n != 32 {
        limit = (1 << n) - 1
    }
    return process2(limit, 0, 0, 0)
}
func process2(limit int, colLim int, leftDiaLim int, rightDiaLim int) int {
    if colLim == limit {
        return 1
    }
    pos := limit & (^(colLim | leftDiaLim | rightDiaLim))
    mostRightOne := 0
    res := 0
    for pos != 0 {
        mostRightOne = pos & (^pos + 1)
        pos = pos - mostRightOne
        res += process2(limit, colLim|mostRightOne, (leftDiaLim|mostRightOne)<<1,
            (rightDiaLim|mostRightOne)>>1)
    }
    return res
}

func num3(n int) int {
    rest := make([]int, n)
    record := make([]int, n)
    for i := 0; i < n; i++ {
        rest[i] = i
    }
    ansval := 0
    ans := &ansval
    process3(record, 0, rest, ans)
    return *ans
}
func process3(record []int, recordLen int, rest []int, ans *int) {
    restLen := len(rest)
    if restLen == 0 {
        *ans++
        return
    }
    for i := 0; i < restLen; i++ {
        isValid := true
        for j := 0; j < recordLen; j++ {
            //不需要看同行和同列，只需要考虑斜线
            if abs(j-recordLen) == abs(record[j]-rest[i]) {
                isValid = false
                break
            }
        }
        if isValid {
            record[recordLen] = rest[i]
            restCopy := make([]int, restLen)
            copy(restCopy, rest)
            restCopy = append(restCopy[:i], restCopy[i+1:]...)
            process3(record, recordLen+1, restCopy, ans)
        }
    }

}

执行结果如下：