52. N-Queens II Hard

1/**
2 * [52] N-Queens II
3 *
4 * The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
5 * Given an integer n, return the number of distinct solutions to the n-queens puzzle.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" />
9 * Input: n = 4
10 * Output: 2
11 * Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
12 *
13 * Example 2:
14 *
15 * Input: n = 1
16 * Output: 1
17 *
18 *  
19 * Constraints:
20 *
21 * 1 <= n <= 9
22 *
23 */
24pub struct Solution {}
25
26// problem: https://leetcode.com/problems/n-queens-ii/
27// discuss: https://leetcode.com/problems/n-queens-ii/discuss/?currentPage=1&orderBy=most_votes&query=
28
29// submission codes start here
30
31impl Solution {
32    pub fn total_n_queens(n: i32) -> i32 {
33        let mut board = vec![vec!['.'; n as usize]; n as usize];
34        let mut result = 0;
35        Self::dfs(&mut board, 0, &mut result);
36        result
37    }
38
39    fn dfs(board: &mut Vec<Vec<char>>, col: usize, result: &mut i32) {
40        if col == board.len() {
41            *result += 1;
42            return;
43        }
44
45        for i in 0..board.len() {
46            if Self::validate(board, i, col) {
47                board[i][col] = 'Q';
48                Self::dfs(board, col + 1, result);
49                board[i][col] = '.';
50            }
51        }
52    }
53
54    fn validate(board: &Vec<Vec<char>>, x: usize, y: usize) -> bool {
55        for i in 0..board.len() {
56            for j in 0..y {
57                if board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i) {
58                    return false;
59                }
60            }
61        }
62        true
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_52() {
74        assert_eq!(Solution::total_n_queens(4), 2);
75    }
76}
77