DFS&BFS - 52. N-Queens II

ppxai

发布于 2020-09-23 17:42:25

46100

代码可运行

文章被收录于专栏：皮皮星球皮皮星球

运行总次数：0

代码可运行

52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n_×_n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

思路：

这一题n皇后与51题区别是只用求出组合种数，而51题要求输出所有结果，做法是一样，都是dfs递归回溯，使用列和对角线是否能摆放皇后来剪枝。

代码：

go：

var col, dia1, dia2 []bool


func totalNQueens(n int) int {
    var res int
    
    col = make([]bool, n)
    dia1 = make([]bool, 2*n-1)
    dia2 = make([]bool, 2*n-1)

    putQueen(n, 0, []int{}, &res)
    
    return res 
}


// 尝试在一个n皇后问题中，摆放第index行的皇后位置
func putQueen(n int, index int, row []int, res *int) {
    if index == n {
        *res++
        return
    }
    
    for i := 0; i < n; i++ {
        if !col[i] && !dia1[index+i] && !dia2[index-i+n-1] { // 对应列、对角线、反对角线没有皇后
            row = append(row, i)
            col[i] = true
            dia1[index+i] = true
            dia2[index-i+n-1] = true
            // 尝试在index + 1 摆放皇后
            putQueen(n, index+1, row, res)
            col[i] = false
            dia1[index+i] = false
            dia2[index-i+n-1] = false
            row = row[:len(row)-1]
        }
    }  
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019年11月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs