n皇后（只需要几个量子）

题目链接：力扣

题目类型： DFS + 回溯

题目描述： 获取n皇后问题不同解法。以第一行为基准点，第一行的任意位置放置皇后，然后每一行都放皇后，且不与其他任意一行冲突。

impl Solution { pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> { let (mut res, mut board) = (vec![], vec![]); // 初始化n*n的棋盘 for i in 0..n { board.push(vec![".".to_string(); n as usize]); } // 判断当前位置是否可以放皇后 fn is_valid(row: usize, col: usize, n: usize, board: &mut Vec<Vec<String>>) -> bool { // 判断前row行的每一列是否有冲突 for i in 0..row { for j in 0..n { if board[i][j] == "Q".to_string() && ( j == col // 同一列判断 // 右斜向对角线 每个位置的 row+col 的值相同 || i + j == row + col // 右斜向对角线判断 // 左斜向对角线 每个位置的 row-col 的值相同 || i - j == row - col // 左斜向对角线判断 ) { return false; } } } true } // 递归查找所有可能放的组合 fn dfs(row: usize, n: usize, board: &mut Vec<Vec<String>>, res: &mut Vec<Vec<String>>) { if row == n { // 已经遍历所有行，结果存储 let mut item = vec![]; for i in 0..board.len() { // vec to string item.push(board[i].join("")); } // 结果收集 res.push(item); return; } // 对每一行的所有列进行遍历，判断是否可以放皇后 for col in 0..n { // 位置判断 if is_valid(row, col, n, board) { // 位置可以放皇后，记录 board[row][col] = "Q".to_string(); dfs(row + 1, n, board, res); // 位置回溯 board[row][col] = ".".to_string(); } } } dfs(0, n as usize, &mut board, &mut res); res } }

运行结果

题目链接： 力扣

题目描述： 获取n皇后问题不同解法的数量。在第51题时，已得出不同n*n矩阵的所有可行解，所以本题直接使用上一道题的结果。

impl Solution { pub fn total_n_queens(n: i32) -> i32 { let vec: Vec<i32> = vec![1, 0, 0, 2, 10, 4, 40, 92, 352]; vec[n as usize - 1] } }

运行结果