算法 N皇后问题-(递归回溯)

牛客网 BM59.

解题思路：

行列、斜叉不在一条直线上。

命令行为 row, 列为col, row 从0开始递归直到最后一行，列从0开始遍历，直到最后一列，中间每一步记录或清除位置状态，状态分为 m1[col] = 1, m2[row-col] = 1, m3[row+col] = 1。当row递归到最后一行时，即获取一个符合要求的答案。

代码:

package main
// import "fmt"
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 the n
 * @return int整型
*/
var m1 = map[int]int{}
var m2 = map[int]int{}
var m3 = map[int]int{}
 
var res = 0
 
func calc(row, n int) {
    if row == n {
        res++
        return
    }
    for col := 0; col < n; col++ {
        if m1[col] == 1 || m2[row-col] == 1 || m3[row+col] == 1 {
            continue
        }
        m1[col] = 1
        m2[row-col] = 1
        m3[row+col] = 1
        calc(row+1, n)
        m1[col] = 0
        m2[row-col] = 0
        m3[row+col] = 0
    }
}
 
 
func Nqueen( n int ) int {
    // write code here
    calc(0, n)
    return res
}