51. N-Queens Hard

1/**
2 * [51] N-Queens
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 all distinct solutions to the n-queens puzzle. You may return the answer in any order.
6 * Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" />
10 * Input: n = 4
11 * Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
12 * Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
13 *
14 * Example 2:
15 *
16 * Input: n = 1
17 * Output: [["Q"]]
18 *
19 *  
20 * Constraints:
21 *
22 * 1 <= n <= 9
23 *
24 */
25pub struct Solution {}
26
27// problem: https://leetcode.com/problems/n-queens/
28// discuss: https://leetcode.com/problems/n-queens/discuss/?currentPage=1&orderBy=most_votes&query=
29
30// submission codes start here
31
32impl Solution {
33    pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
34        let mut board = vec![vec!['.'; n as usize]; n as usize];
35        let mut result: Vec<Vec<String>> = vec![];
36        Self::dfs(&mut board, &mut result, 0);
37        result
38    }
39
40    fn dfs(board: &mut Vec<Vec<char>>, result: &mut Vec<Vec<String>>, col: usize) {
41        if col == board.len() {
42            result.push(Self::generate(board));
43            return;
44        }
45
46        for i in 0..board.len() {
47            if Self::validate(board, i, col) {
48                board[i][col] = 'Q';
49                Self::dfs(board, result, col + 1);
50                board[i][col] = '.';
51            }
52        }
53    }
54
55    fn validate(board: &Vec<Vec<char>>, x: usize, y: usize) -> bool {
56        for i in 0..board.len() {
57            for j in 0..y {
58                if board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i) {
59                    return false;
60                }
61            }
62        }
63        true
64    }
65
66    fn generate(board: &Vec<Vec<char>>) -> Vec<String> {
67        let mut result = vec![];
68        for i in 0..board.len() {
69            result.push(board[i].iter().collect());
70        }
71        result
72    }
73}
74
75// submission codes end
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn test_51() {
83        let result = Solution::solve_n_queens(4);
84        println!("Got {:#?}", result);
85    }
86}
87