N queens

Array Backtracking

75.0% acceptance

Jan 12, 2026

14197

347

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 all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
    let mut result = Vec::new();
    let mut board = vec![vec!['.'; n as usize]; n as usize];
    Self::backtrack_51(&mut board, 0, n as usize, &mut result);
    result
  }
  
  fn backtrack_51(board: &mut Vec<Vec<char>>, row: usize, n: usize, result: &mut Vec<Vec<String>>) {
    if row == n {
      result.push(board.iter().map(|r| r.iter().collect()).collect());
      return;
    }
    
    for col in 0..n {
      if Self::is_valid_51(board, row, col, n) {
        board[row][col] = 'Q';
        Self::backtrack_51(board, row + 1, n, result);
        board[row][col] = '.';
      }
    }
  }
  
  fn is_valid_51(board: &Vec<Vec<char>>, row: usize, col: usize, n: usize) -> bool {
    // Check column
    for i in 0..row {
      if board[i][col] == 'Q' {
        return false;
      }
    }
    
    // Check diagonal (top-left to bottom-right)
    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] == 'Q' {
        return false;
      }
      i -= 1;
      j -= 1;
    }
    
    // Check anti-diagonal (top-right to bottom-left)
    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] == 'Q' {
        return false;
      }
      i -= 1;
      j += 1;
    }
    
    true
  }
}