0051.N 皇后

func hasConflict(vals []string, 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
}

func solveNQueens(n int) [][]string {
	ans, vals := [][]string{}, make([]string, n)
	for i := 0; i < n; i++ {
		vals[i] = strings.Repeat(".", n)
	}
	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			ans = append(ans, append([]string{}, vals...))
			return
		}
		for i := 0; i < n; i++ {
			if hasConflict(vals, row, i) {
				tmp := []byte(vals[row])
				tmp[i] = 'Q'
				vals[row] = string(tmp)
				backtrack(row + 1)
				tmp[i] = '.'
				vals[row] = string(tmp)
			}

		}
	}
	backtrack(0)
	return ans
}