N queens ii

Backtracking

78.2% acceptance

Jan 12, 2026

4256

282

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. Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn total_n_queens(n: i32) -> i32 {
    let mut count = 0;
    let mut board = vec![vec![false; n as usize]; n as usize];
    Self::backtrack_52(&mut board, 0, n as usize, &mut count);
    count
  }
  
  fn backtrack_52(board: &mut Vec<Vec<bool>>, row: usize, n: usize, count: &mut i32) {
    if row == n {
      *count += 1;
      return;
    }
    
    for col in 0..n {
      if Self::is_valid_52(board, row, col, n) {
        board[row][col] = true;
        Self::backtrack_52(board, row + 1, n, count);
        board[row][col] = false;
      }
    }
  }
  
  fn is_valid_52(board: &Vec<Vec<bool>>, row: usize, col: usize, n: usize) -> bool {
    // Check column
    for i in 0..row {
      if board[i][col] {
        return false;
      }
    }
    
    // Check diagonal
    let mut i = row as i32 - 1;
    let mut j = col as i32 - 1;
    while i >= 0 && j >= 0 {
      if board[i as usize][j as usize] {
        return false;
      }
      i -= 1;
      j -= 1;
    }
    
    // Check anti-diagonal
    let mut i = row as i32 - 1;
    let mut j = col as i32 + 1;
    while i >= 0 && j < n as i32 {
      if board[i as usize][j as usize] {
        return false;
      }
      i -= 1;
      j += 1;
    }
    
    true
  }
}