0052.N皇后 II

https://leetcode.cn/problems/n-queens-ii/

方法一：回溯

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。

func totalNQueens(n int) int {
	ans, vals := 0, make([][]byte, n)
	for i := 0; i < n; i++ {
		vals[i] = make([]byte, n)
		for j := 0; j < n; j++ {
			vals[i][j] = '.'
		}
	}
	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			ans++
			return
		}
		for i := 0; i < n; i++ {
			if isValid(vals, row, i) {
				vals[row][i] = 'Q'
				backtrack(row + 1)
				vals[row][i] = '.'
			}
		}
	}
	backtrack(0)
	return ans
}

func isValid(vals [][]byte, x, y int) bool {
	n := len(vals)
	for i := x - 1; i >= 0; i-- {
		if vals[i][y] == 'Q' {
			return false
		}
	}
	for i, j := x-1, y+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if vals[i][j] == 'Q' {
			return false
		}
	}
	for i, j := x-1, y-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if vals[i][j] == 'Q' {
			return false
		}
	}
	return true
}