Skip to content

Peaceful Chessboard

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Peaceful Chessboard

On an n x n chessboard you must place n queens so that no two threaten each other (no shared row, column, or diagonal).

Return the number of distinct ways to place the queens.

def total_n_queens(n):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Backtracking, Recursion, Sets

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What does it mean for two queens to threaten each other?
    • A: Two queens threaten each other if they share the same row, the same column, or the same diagonal (in either direction).
  • Q: Do we need to return the actual board arrangements?
    • A: No. We only need to return the count of distinct valid arrangements, not the boards themselves.
  • Q: Since exactly n queens go on an n x n board, what does that tell us about the rows?
    • A: Every row must contain exactly one queen. This lets us place queens row by row and only decide which column each one goes in.
HAPPY CASE
Input: n = 4
Output: 2
Explanation: There are exactly two ways to place 4 non-threatening queens on a 4x4 board (each is a mirror image of the other).

Input: n = 1
Output: 1
Explanation: A single queen on a 1x1 board threatens no one, so there is exactly 1 arrangement.

EDGE CASE
Input: n = 2
Output: 0
Explanation: On a 2x2 board, any two queens share a row, column, or diagonal, so no peaceful arrangement exists. (The same is true for n = 3.)

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Constraint Satisfaction / Counting Problems, we can consider the following approaches:

  • Backtracking: Build the board one row at a time. Place a queen in a column that is still safe, recurse to the next row, and undo the choice on the way back. This is the classic N-Queens backtracking pattern.
  • Sets for O(1) conflict checks: Track occupied columns and diagonals in sets so each candidate square can be validated in constant time instead of rescanning the board.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Place one queen per row, working from row 0 down to row n - 1. For each row, try every column; a column is safe if no earlier queen occupies that column, its "/" diagonal, or its "" diagonal. Squares on the same "" diagonal share the value row - col, and squares on the same "/" diagonal share the value row + col, so three sets are enough to detect every conflict. Each time we successfully place a queen in the last row, we have found one complete arrangement and count it.

1) Create three empty sets: cols, neg_diagonals (row - col), and pos_diagonals (row + col).
2) Define a recursive helper backtrack(row):
   a) Base case: if row == n, every queen is placed peacefully, so return 1.
   b) Initialize count = 0.
   c) For each col from 0 to n - 1:
      i)   If col is in cols, or (row - col) is in neg_diagonals, or (row + col) is in pos_diagonals, skip it.
      ii)  Otherwise, add col, (row - col), and (row + col) to the sets (place the queen).
      iii) Add backtrack(row + 1) to count.
      iv)  Remove col, (row - col), and (row + col) from the sets (un-place the queen).
   d) Return count.
3) Return backtrack(0).

⚠️ Common Mistakes

  • Forgetting to remove the queen from the sets after the recursive call, which corrupts the state for sibling branches.
  • Checking only rows and columns and forgetting one (or both) diagonal directions.
  • Mixing up the diagonal identifiers: row - col is constant along "" diagonals and row + col is constant along "/" diagonals.
  • Rescanning the whole board to validate each placement, which works but adds an unnecessary O(n) factor per check.

4: I-mplement

Implement the code to solve the algorithm.

def total_n_queens(n):
    def backtrack(row):
        # Base case: all n queens placed peacefully
        if row == n:
            return 1

        count = 0
        for col in range(n):
            # Skip any column or diagonal already under attack
            if col in cols or (row - col) in neg_diagonals or (row + col) in pos_diagonals:
                continue

            # Choose: place a queen at (row, col)
            cols.add(col)
            neg_diagonals.add(row - col)
            pos_diagonals.add(row + col)

            # Explore: place queens in the remaining rows
            count += backtrack(row + 1)

            # Un-choose: remove the queen and try the next column
            cols.remove(col)
            neg_diagonals.remove(row - col)
            pos_diagonals.remove(row + col)

        return count

    cols = set()           # Columns that already hold a queen
    neg_diagonals = set()  # "\" diagonals, identified by row - col
    pos_diagonals = set()  # "/" diagonals, identified by row + col
    return backtrack(0)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: n = 4

    • Row 0, col 0: placing here eventually dead-ends — rows 1-3 run out of safe columns, so this branch contributes 0.
    • Row 0, col 1: leads to the valid board with queens at columns (1, 3, 0, 2), contributing 1.
    • Row 0, col 2: leads to the mirror board with queens at columns (2, 0, 3, 1), contributing 1.
    • Row 0, col 3: dead-ends like col 0, contributing 0.
    • Output: 2

  • Input: n = 1

    • Row 0, col 0 is safe; backtrack(1) hits the base case and returns 1.
    • Output: 1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the side length of the board (and the number of queens).

  • Time Complexity: O(N!) — the first row has N column choices, and each subsequent row has strictly fewer safe columns, so the search tree is bounded by N * (N - 1) * (N - 2) * .... Each placement check is O(1) thanks to the sets.
  • Space Complexity: O(N) for the recursion stack (one frame per row) and the three conflict sets, each of which holds at most N entries.

Clone this wiki locally