【LeetCode】52、N 皇后 II

【LeetCode】52、N 皇后 II

一、递归 数组解法

1.1 递归 数组解法

// go
func totalNQueens(n int) int {
    return f(n, 0, make([]int, n))
}

// 在 [0...i-1] 行已摆放的情况下 路径是 path, 返回: 第i行 有几种方案
// 其中 path 的下标为行, 值为列
func f(n, i int, path []int) (ans int) {
    if i == n {return 1} // 若能成功摆放到 [0...n-1], 则说明已得到一种解决方案
    for j := 0; j < n; j++ { // 当前若摆放在 第i行, 第j列
        if check(path, i, j) { // 第i行, 第j列 可以摆放
            path[i] = j // 放入路径
            ans += f(n, i+1, path) // 继续下一行, 直到到达最后一行
        } // 否则: 若不能摆放, 则不会进入下一行, 从而无法到达最后一行, 最终不能形成解决方案
    }
    return
}

// 在 [0...i-1] 行已摆放且路径为 path 的情况下, 返回 第i行第j列能否摆放
func check(path []int, i, j int) bool {
    for k := 0; k < i; k++ { // 遍历第k行: 即从 第0到i-1行
        // 第k行, 对应的是 path[k] 列
        if j == path[k] || abs(i-k) == abs(j-path[k]) { // 列冲突, 或, 对角线冲突, 则无法摆放
            return false
        }
    }
    return true
}

func abs(x int) int {
    if x < 0 {return -x}
    return x
}

参考左神 N皇后 数组解法

1.2 多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts

二、位运算解法

1.1 位运算解法

func totalNQueens(n int) int {
    if n < 1 {return 0}
    limit := (1<<n) - 1 // 最低位为n个1
    return f(limit, 0, 0, 0)
}

// 第i行, col为列, left为向左下的对角线, right为向右下的对角线. 第x位为1表示第x位被占用了
// limit 则限制, 只处理 0 到 n 位内的数
func f(limit, col, left, right int) (ans int) {
    if col == limit {return 1} // 若 col 和 limit 相等, 说明之前 0...i-1 行已经把 各列 都填充了, 则说明找到了一个解决方案
    ban := col | left | right // 第i行的禁止区域
    candidate := limit & (^ban) // 第i行的可选区域, golang 中 ^ 就是表示 ~ 按位取反的意思
    for candidate != 0 { // 第i行, 尝试各种列的取值
        place := candidate & (-candidate) // candidate最右侧的1, 其中 -candidate 就是 ~candidate+1, 是放置皇后的尝试
        candidate ^= place // 移除candidate最右侧的1
        ans += f(limit, col | place, (left | place) >> 1, (right | place) << 1)
    }
    return
}

参考左神 位运算版本

2.2 多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts