Solving the N-Queens puzzle with backtracking

You are 30 minutes into a Google interview. The interviewer hands you a whiteboard marker and says, "Place four queens on a 4x4 chessboard so that none of them can attack each other. Now write code that finds every valid arrangement for any board size." This is the N-Queens problem, also known as "N-Queens" on other platforms. It is one of the most well-known backtracking challenges, and it has been asked at Google, Bloomberg, Meta, and Microsoft.

TL;DR

Place queens one row at a time. For each row, try every column. Before placing a queen, verify no previously placed queen shares the same column or diagonal. If no column works, backtrack to the previous row and try the next option. Collect every complete board as a solution. The algorithm runs in O(n!) time and uses O(n^2) space for the board.

Why This Problem Matters

N-Queens is the textbook example of backtracking. If you understand how to solve it, you can apply the same pattern to Sudoku solvers, permutation generators, combination sums, and dozens of other problems that explore a search space with constraints. Interviewers love it because it tests recursive thinking, pruning logic, and the ability to translate a visual problem into clean code.

How Queens Attack

Before diving into the algorithm, let's make sure the chess rules are clear. A queen attacks every square on its row, its column, and both diagonals. Here is a queen placed at row 1, column 1 on a 4x4 board. Every square marked x is under attack:

The row, column, and diagonal constraints are what make this problem interesting. Placing a single queen eliminates many squares from consideration for subsequent queens.

Understanding the Problem

Given: An integer n representing the board size. Return: All distinct arrangements of n queens on an n x n board where no two queens attack each other.

Each solution is a list of strings. 'Q' marks a queen and '.' marks an empty square.

For n = 4, there are exactly two solutions:

Solution 1:

Solution 2:

Constraints

• 1 ≤ n ≤ 9
• For n = 2 and n = 3, no valid solutions exist.
• For n = 1, the only solution is a single queen.

Solution Approach: Row-by-Row Backtracking

The key observation is that each row must contain exactly one queen (since two queens in the same row would attack each other). This lets us frame the problem as placing one queen per row, choosing which column to use.

The Algorithm

1. Start at row 0.
2. Try placing a queen in each column of the current row.
3. For each placement, check whether it conflicts with queens already on the board.
4. If valid, move to the next row and repeat.
5. If we fill all rows, record the board as a solution.
6. After exploring a placement, remove the queen (backtrack) and try the next column.

Walking Through n=4

Let's trace the algorithm on a 4x4 board. We start by placing a queen at (0, 0). The x marks show squares that are now blocked:

Row 1 has two open squares: columns 2 and 3. Let's try column 2. Now queens sit at (0, 0) and (1, 2):

Looking at row 2, every column is blocked. Column 0 shares a column with the first queen, column 1 is on the diagonal of the second queen, column 2 shares a column with the second queen, and column 3 is on the diagonal of the first queen. This means we hit a dead end and need to backtrack.

We remove the queen from (1, 2) and try (1, 3) instead. Eventually, after several rounds of trying and backtracking, we discover that starting at column 0 in row 0 does not lead to any solution for n=4. The algorithm then backtracks all the way to row 0 and tries column 1.

Starting from column 1, we find our first solution: queens at (0, 1), (1, 3), (2, 0), (3, 2):

The last open square in row 3 is column 2, completing the arrangement. The algorithm records this solution and continues searching for more.

The Validation Check

When placing a queen at (row, col), we only need to check rows above the current one (rows below are empty). Three things can cause a conflict:

1. Same column: Any queen in rows 0 through row - 1 at the same col.
2. Upper-left diagonal: Walk upward-left from (row - 1, col - 1) until you go off the board.
3. Upper-right diagonal: Walk upward-right from (row - 1, col + 1) until you go off the board.

If all three checks pass, the placement is safe.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {

  public List<List<String>> solveNQueens(int n) {
    List<List<String>> solutions = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) {
      Arrays.fill(row, '.');
    }
    solve(solutions, board, 0, n);
    return solutions;
  }

  private void solve(List<List<String>> solutions, char[][] board, int row, int n) {
    if (row == n) {
      solutions.add(construct(board));
      return;
    }
    for (int col = 0; col < n; col++) {
      if (isValid(board, row, col, n)) {
        board[row][col] = 'Q';
        solve(solutions, board, row + 1, n);
        board[row][col] = '.';
      }
    }
  }

  private boolean isValid(char[][] board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
      if (board[i][col] == 'Q') {
        return false;
      }
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] == 'Q') {
        return false;
      }
    }
    return true;
  }

  private List<String> construct(char[][] board) {
    List<String> path = new ArrayList<>();
    for (char[] row : board) {
      path.add(new String(row));
    }
    return path;
  }
}

Let's walk through the key pieces:

• solveNQueens initializes the board with dots and kicks off the recursive search from row 0.
• solve is the recursive backtracking function. It tries each column in the current row, places a queen if valid, recurses into the next row, then removes the queen to try the next column.
• isValid scans upward through the column, upper-left diagonal, and upper-right diagonal. It returns false the moment it finds a conflict.
• construct converts the 2D character array into a list of strings for the final output.

The backtracking happens on the line board[row][col] = '.'. After the recursive call returns (whether it found solutions or hit dead ends), we undo the placement so the next column can be explored with a clean board.

Complexity Analysis

Time Complexity: O(n!)

In the worst case, we try n columns for row 0, up to n - 1 for row 1 (one column is already taken), n - 2 for row 2, and so on. This gives roughly n! leaf nodes in the search tree. The validation check at each node costs O(n) for scanning the column and diagonals, giving an upper bound of O(n * n!). In practice, pruning cuts the actual work significantly below this bound.

Space Complexity: O(n^2)

The board itself takes O(n^2) space. The recursion stack is O(n) deep since we recurse one row at a time. The output can contain many solutions (92 for n=8), but we typically don't count output space in the complexity.

Optimization note: You can replace the isValid scan with three boolean arrays (or sets) tracking occupied columns, left diagonals, and right diagonals. This makes each validation check O(1) instead of O(n), at the cost of O(n) extra space. The JavaScript and TypeScript solutions below use this approach with sets.

Common Pitfalls

1. Forgetting to backtrack. If you place a queen but never remove it after exploring, subsequent iterations will see a corrupted board. Always reset board[row][col] = '.' after the recursive call.

2. Checking all four diagonal directions. You only need to check upward (upper-left and upper-right) because rows below the current one are still empty. Checking downward is wasted work.

3. Returning early after one solution. The problem asks for all solutions. Make sure the loop continues after recording a valid board.

4. Off-by-one in diagonal indexing. When using row + col and row - col as diagonal keys, remember that row - col can be negative. If you're using an array instead of a set, offset the index by n - 1.

Interview Tips

When solving this in an interview:

1. Draw the board. Sketch a 4x4 grid and walk through placing queens. This shows the interviewer your thinking and helps you catch bugs.

2. State the row-by-row insight early. Mentioning that each row has exactly one queen immediately simplifies the search space from n^n to roughly n!.

3. Discuss the validation trade-off. Explain that scanning the board is O(n) per check, and mention the O(1) optimization with boolean arrays or sets. Implement whichever version you are more comfortable coding correctly.

4. Consider follow-ups. The interviewer might ask for just the count of solutions (simpler, no board construction), or whether a solution exists for a given n, or for an optimized bitmask approach. Knowing these variants exist shows depth.

Key Takeaways

• N-Queens is solved by placing one queen per row and using backtracking to prune invalid branches early, reducing the search space from n^n to roughly n!.
• The validation step only looks upward because rows below the current placement are always empty.
• Backtracking requires undoing each choice (removing the queen) after exploring its subtree so subsequent iterations work with a clean board state.
• Replacing the O(n) column/diagonal scan with boolean arrays or sets gives O(1) validation at the cost of O(n) extra space.
• For n=4 there are exactly 2 solutions, and for n=8 there are 92. No valid arrangement exists for n=2 or n=3.

Practice Makes Perfect

Once you're comfortable with N-Queens, try these related backtracking problems to solidify the pattern:

• Sudoku Puzzle Completion Challenge (same constraint-satisfaction structure with a 9x9 grid)
• Generate Combinations of Parentheses (backtracking with a different constraint)
• Sum Combinations with Repeats (explore/backtrack with a running total)
• Power Set Exploration (subset generation using backtracking)

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed jobs at top tech companies. Whether you are warming up for your first interview or targeting a specific FAANG company, consistent practice with problems like N-Queens builds the pattern recognition that makes hard problems feel routine.

Solutions in Other Languages

Python

class Solution:
    def solve_n_queens(self, n: int) -> list[list[str]]:
        def is_valid(board: list[str], row: int, col: int) -> bool:
            for i in range(row):
                if board[i][col] == 'Q':
                    return False
                if col - (row - i) >= 0 and board[i][col - (row - i)] == 'Q':
                    return False
                if col + (row - i) < n and board[i][col + (row - i)] == 'Q':
                    return False
            return True

        def solve(row: int, board: list[str]):
            if row == n:
                solutions.append(board[:])
                return
            for col in range(n):
                if is_valid(board, row, col):
                    board[row] = board[row][:col] + 'Q' + board[row][col+1:]
                    solve(row + 1, board)
                    board[row] = board[row][:col] + '.' + board[row][col+1:]

        solutions = []
        solve(0, ['.' * n for _ in range(n)])
        return solutions

JavaScript

The JavaScript solution uses Set objects to track occupied columns and diagonals, giving O(1) validation per placement.

class Solution {
  solveNQueens(n) {
    const solutions = [];
    const solve = (row, columns, diagonals1, diagonals2, board) => {
      if (row === n) {
        solutions.push(board.map(r => r.join('')));
        return;
      }
      for (let col = 0; col < n; col++) {
        const diag1 = row - col;
        const diag2 = row + col;
        if (columns.has(col) || diagonals1.has(diag1) || diagonals2.has(diag2)) {
          continue;
        }
        board[row][col] = 'Q';
        columns.add(col);
        diagonals1.add(diag1);
        diagonals2.add(diag2);
        solve(row + 1, columns, diagonals1, diagonals2, board);
        board[row][col] = '.';
        columns.delete(col);
        diagonals1.delete(diag1);
        diagonals2.delete(diag2);
      }
    };
    const board = Array.from({ length: n }, () => Array(n).fill('.'));
    solve(0, new Set(), new Set(), new Set(), board);
    return solutions;
  }
}

TypeScript

Same set-based approach as JavaScript, with explicit type annotations.

class Solution {
  solveNQueens(n: number): string[][] {
    const solutions: string[][] = [];
    const solve = (
      row: number,
      columns: Set<number>,
      diagonals1: Set<number>,
      diagonals2: Set<number>,
      board: string[][]
    ): void => {
      if (row === n) {
        solutions.push(board.map((r) => r.join("")));
        return;
      }
      for (let col = 0; col < n; col++) {
        const diag1 = row - col;
        const diag2 = row + col;
        if (columns.has(col) || diagonals1.has(diag1) || diagonals2.has(diag2)) {
          continue;
        }
        board[row][col] = "Q";
        columns.add(col);
        diagonals1.add(diag1);
        diagonals2.add(diag2);
        solve(row + 1, columns, diagonals1, diagonals2, board);
        board[row][col] = ".";
        columns.delete(col);
        diagonals1.delete(diag1);
        diagonals2.delete(diag2);
      }
    };
    const board: string[][] = Array.from({ length: n }, () => Array(n).fill("."));
    solve(0, new Set<number>(), new Set<number>(), new Set<number>(), board);
    return solutions;
  }
}

C++

The C++ solution uses boolean vectors for column and diagonal tracking.

#include <vector>
#include <string>
#include <functional>

class Solution {
public:
  std::vector<std::vector<std::string>> solveNQueens(int n) {
    std::vector<std::vector<std::string>> solutions;
    std::vector<std::string> board(n, std::string(n, '.'));
    std::vector<bool> columns(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);

    std::function<void(int)> backtrack = [&](int row) {
      if (row == n) {
        solutions.push_back(board);
        return;
      }
      for (int col = 0; col < n; ++col) {
        if (columns[col] || diag1[row + col] || diag2[row - col + n - 1]) continue;
        board[row][col] = 'Q';
        columns[col] = diag1[row + col] = diag2[row - col + n - 1] = true;
        backtrack(row + 1);
        board[row][col] = '.';
        columns[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
      }
    };

    backtrack(0);
    return solutions;
  }
};

Go

package solution

func (s *Solution) SolveNQueens(n int) [][]string {
    var solutions [][]string
    board := make([][]byte, n)
    for i := range board {
        board[i] = make([]byte, n)
        for j := range board[i] {
            board[i][j] = '.'
        }
    }

    var solve func(row int)
    solve = func(row int) {
        if row == n {
            var solution []string
            for _, b := range board {
                solution = append(solution, string(b))
            }
            solutions = append(solutions, solution)
            return
        }
        for col := 0; col < n; col++ {
            if isValid(board, row, col, n) {
                board[row][col] = 'Q'
                solve(row + 1)
                board[row][col] = '.'
            }
        }
    }

    solve(0)
    return solutions
}

func isValid(board [][]byte, row, col, n int) bool {
    for i := 0; i < row; i++ {
        if board[i][col] == 'Q' {
            return false
        }
    }
    for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if board[i][j] == 'Q' {
            return false
        }
    }
    for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
        if board[i][j] == 'Q' {
            return false
        }
    }
    return true
}

Scala

The Scala solution uses an integer array to track queen column positions and a functional fold to accumulate solutions.

class Solution {
  def solveNQueens(n: Int): List[List[String]] = {
    def isSafe(board: Array[Int], row: Int, col: Int): Boolean = {
      for (i <- 0 until row) {
        if (board(i) == col || board(i) - i == col - row || board(i) + i == col + row) {
          return false
        }
      }
      true
    }

    def solve(row: Int, board: Array[Int], solutions: List[List[String]]): List[List[String]] = {
      if (row == n) {
        val solution = board.map { col =>
          "." * col + "Q" + "." * (n - col - 1)
        }.toList
        solution :: solutions
      } else {
        (0 until n).foldLeft(solutions) { (acc, col) =>
          if (isSafe(board, row, col)) {
            board(row) = col
            solve(row + 1, board, acc)
          } else {
            acc
          }
        }
      }
    }

    solve(0, new Array[Int](n), List.empty[List[String]])
  }
}

Kotlin

class Solution {
  fun solveNQueens(n: Int): List<List<String>> {
    val solutions = mutableListOf<List<String>>()
    val board = Array(n) { CharArray(n) { '.' } }

    fun isValid(row: Int, col: Int): Boolean {
      for (i in 0 until row) {
        if (board[i][col] == 'Q') return false
      }
      var i = row - 1; var j = col - 1
      while (i >= 0 && j >= 0) {
        if (board[i][j] == 'Q') return false
        i--; j--
      }
      i = row - 1; j = col + 1
      while (i >= 0 && j < n) {
        if (board[i][j] == 'Q') return false
        i--; j++
      }
      return true
    }

    fun solve(row: Int) {
      if (row == n) {
        solutions.add(board.map { String(it) })
        return
      }
      for (col in 0 until n) {
        if (isValid(row, col)) {
          board[row][col] = 'Q'
          solve(row + 1)
          board[row][col] = '.'
        }
      }
    }

    solve(0)
    return solutions
  }
}

Ruby

class Solution
  def solve_n_queens(n)
    solutions = []
    board = Array.new(n) { Array.new(n, '.') }

    solve = lambda do |row|
      if row == n
        solutions << board.map { |r| r.join }
        return
      end
      (0...n).each do |col|
        if valid?(board, row, col, n)
          board[row][col] = 'Q'
          solve.call(row + 1)
          board[row][col] = '.'
        end
      end
    end

    solve.call(0)
    solutions
  end

  private

  def valid?(board, row, col, n)
    (0...row).each { |i| return false if board[i][col] == 'Q' }
    i, j = row - 1, col - 1
    while i >= 0 && j >= 0
      return false if board[i][j] == 'Q'
      i -= 1; j -= 1
    end
    i, j = row - 1, col + 1
    while i >= 0 && j < n
      return false if board[i][j] == 'Q'
      i -= 1; j += 1
    end
    true
  end
end

Rust

pub struct Solution;

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

    fn solve(&self, solutions: &mut Vec<Vec<String>>, board: &mut Vec<Vec<char>>, row: usize, n: usize) {
        if row == n {
            solutions.push(board.iter().map(|r| r.iter().collect()).collect());
            return;
        }
        for col in 0..n {
            if self.is_valid(board, row, col, n) {
                board[row][col] = 'Q';
                self.solve(solutions, board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }

    fn is_valid(&self, board: &[Vec<char>], row: usize, col: usize, n: usize) -> bool {
        for i in 0..row {
            if board[i][col] == 'Q' { return false; }
        }
        let (mut i, mut j) = (row as i32 - 1, col as i32 - 1);
        while i >= 0 && j >= 0 {
            if board[i as usize][j as usize] == 'Q' { return false; }
            i -= 1; j -= 1;
        }
        let (mut i, mut j) = (row as i32 - 1, col as i32 + 1);
        while i >= 0 && (j as usize) < n {
            if board[i as usize][j as usize] == 'Q' { return false; }
            i -= 1; j += 1;
        }
        true
    }
}

Swift

class Solution {
    func solveNQueens(_ n: Int) -> [[String]] {
        var solutions: [[String]] = []
        var board = [[Character]](repeating: [Character](repeating: ".", count: n), count: n)

        func isValid(_ row: Int, _ col: Int) -> Bool {
            for i in 0..<row {
                if board[i][col] == "Q" { return false }
            }
            var i = row - 1, j = col - 1
            while i >= 0 && j >= 0 {
                if board[i][j] == "Q" { return false }
                i -= 1; j -= 1
            }
            i = row - 1; j = col + 1
            while i >= 0 && j < n {
                if board[i][j] == "Q" { return false }
                i -= 1; j += 1
            }
            return true
        }

        func solve(_ row: Int) {
            if row == n {
                solutions.append(board.map { String($0) })
                return
            }
            for col in 0..<n {
                if isValid(row, col) {
                    board[row][col] = "Q"
                    solve(row + 1)
                    board[row][col] = "."
                }
            }
        }

        solve(0)
        return solutions
    }
}

Dart

class Solution {
  List<List<String>> solveNQueens(int n) {
    List<List<String>> solutions = [];
    List<List<String>> board = List.generate(n, (_) => List.filled(n, '.'));

    bool isValid(int row, int col) {
      for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
      }
      int i = row - 1, j = col - 1;
      while (i >= 0 && j >= 0) {
        if (board[i][j] == 'Q') return false;
        i--; j--;
      }
      i = row - 1; j = col + 1;
      while (i >= 0 && j < n) {
        if (board[i][j] == 'Q') return false;
        i--; j++;
      }
      return true;
    }

    void solve(int row) {
      if (row == n) {
        solutions.add(board.map((row) => row.join()).toList());
        return;
      }
      for (int col = 0; col < n; col++) {
        if (isValid(row, col)) {
          board[row][col] = 'Q';
          solve(row + 1);
          board[row][col] = '.';
        }
      }
    }

    solve(0);
    return solutions;
  }
}

C#

public class Solution {
    public List<List<string>> SolveNQueens(int n) {
        var solutions = new List<List<string>>();
        var board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = new char[n];
            Array.Fill(board[i], '.');
        }
        Solve(solutions, board, 0, n);
        return solutions;
    }

    private void Solve(List<List<string>> solutions, char[][] board, int row, int n) {
        if (row == n) {
            var path = new List<string>();
            foreach (var r in board) path.Add(new string(r));
            solutions.Add(path);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (IsValid(board, row, col, n)) {
                board[row][col] = 'Q';
                Solve(solutions, board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }

    private bool IsValid(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
}

PHP

class Solution {
    public function solveNQueens(int $n): array {
        $solutions = [];
        $board = array_fill(0, $n, array_fill(0, $n, '.'));
        $this->solve($solutions, $board, 0, $n);
        return $solutions;
    }

    private function solve(array &$solutions, array &$board, int $row, int $n): void {
        if ($row === $n) {
            $path = [];
            foreach ($board as $r) $path[] = implode('', $r);
            $solutions[] = $path;
            return;
        }
        for ($col = 0; $col < $n; $col++) {
            if ($this->isValid($board, $row, $col, $n)) {
                $board[$row][$col] = 'Q';
                $this->solve($solutions, $board, $row + 1, $n);
                $board[$row][$col] = '.';
            }
        }
    }

    private function isValid(array $board, int $row, int $col, int $n): bool {
        for ($i = 0; $i < $row; $i++) {
            if ($board[$i][$col] === 'Q') return false;
        }
        for ($i = $row - 1, $j = $col - 1; $i >= 0 && $j >= 0; $i--, $j--) {
            if ($board[$i][$j] === 'Q') return false;
        }
        for ($i = $row - 1, $j = $col + 1; $i >= 0 && $j < $n; $i--, $j++) {
            if ($board[$i][$j] === 'Q') return false;
        }
        return true;
    }
}