[leetcode-in-go] 0052-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…”]

]

解題思路

• 回溯

func available(current []int, index int) bool {
	n := len(current)
	for i, v := range current {
		// 同一列
		if index == v {
			return false
		}

		// 對角線
		if (n-i) == index-v || (n-i) == v-index {
			return false
		}
	}

	return true
}

func core(current []int, n int, cnt *int) {
	if len(current) == n {
        *cnt += 1
	}

	for i := 0; i < n; i++ {
		if available(current, i) {
			core(append(current, i), n, cnt)
		}
	}
}

func totalNQueens(n int) int {
    cnt := 0
	if n == 0 {
		return cnt
	}
	core([]int{}, n, &cnt)
	return cnt
}