impl Solution {
    fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
        let mut solutions = Vec::new();
        let mut board = vec![vec!['.'; n as usize]; n as usize];
        Solution::solve(0, &mut board, &mut solutions, n as usize);
        solutions
    }

    fn solve(row: usize, board: &mut Vec<Vec<char>>, solutions: &mut Vec<Vec<String>>, n: usize) {
        if row == n {
            solutions.push(board.iter().map(|r| r.iter().collect()).collect());
            return;
        }

        for col in 0..n {
            if Solution::is_valid(row, col, board, n) {
                board[row][col] = 'Q';
                Solution::solve(row + 1, board, solutions, n);
                board[row][col] = '.';
            }
        }
    }

    fn is_valid(row: usize, col: usize, board: &Vec<Vec<char>>, n: usize) -> bool {
        // Check this column
        for i in 0..row {
            if board[i][col] == 'Q' {
                return false;
            }
        }

        // Check upper left diagonal
        let mut i = row as i32;
        let mut j = col as i32;
        while i >= 0 && j >= 0 {
            if board[i as usize][j as usize] == 'Q' {
                return false;
            }
            i -= 1;
            j -= 1;
        }

        // Check upper right diagonal
        i = row as i32;
        j = col as i32;
        while i >= 0 && j < n as i32 {
            if board[i as usize][j as usize] == 'Q' {
                return false;
            }
            i -= 1;
            j += 1;
        }

        true
    }
}