Constraint Satisfaction Using Backtracking: DSA Guide

Place pieces one row at a time; when a choice poisons everything below, undo it and try the next column.

“All arrangements satisfying rules” / “place X so that no two conflict” → backtracking

Pattern: N-Queens

One full branch dies at row 3, backtracks to the root, and the second placement solves the board. Press ▶.

N-Queens (n=4)

Place n queens on an n×n board so none share a row, column, or diagonal.

Place row by row, trying each column and keeping only safe spots (no shared column or diagonal). The moment a row has no safe cell, backtrack: remove the last queen and try its next column. Fail fast, unwind cleanly, try the next branch — that's the whole algorithm.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        solve(r):
                      
                        2
                          if r == n: SOLUTION ✓
                      
                        3
                          for c in 0..n-1:
                      
                        4
                            if safe(r,c):          # no queen shares col/diag
                      
                        5
                              place(r,c); solve(r+1)
                      
                        6
                              remove(r,c)          # BACKTRACK
                      
                        7
                          # all columns failed → return false

The safe check is the whole problem: same column, or either diagonal.

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

void place(List<List<String>> res, char[][] b, int r) {
    if (r == b.length) { res.add(toStrings(b)); return; }
    for (int c = 0; c < b.length; c++) {
        if (safe(b, r, c)) {
            b[r][c] = 'Q';
            place(res, b, r + 1);
            b[r][c] = '.';      // BACKTRACK
        }
    }
}

boolean safe(char[][] b, int r, int c) {
    for (int i = 0; i < r; i++)
        for (int j = 0; j < b.length; j++)
            if (b[i][j] == 'Q'
                && (j == c || Math.abs(i-r) == Math.abs(j-c)))
                return false;
    return true;
}

def solve_n_queens(n):
    res, board = [], []

    def safe(r, c):
        for qr, qc in enumerate(board):
            if qc == c or abs(qr - r) == abs(qc - c):
                return False
        return True

    def place(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1)
                        for c in board])
            return
        for c in range(n):
            if safe(r, c):
                board.append(c)
                place(r + 1)
                board.pop()     # BACKTRACK

    place(0)
    return res

vector<vector<string>> res;
vector<int> queens;   // queens[r] = column of queen in row r

bool safe(int r, int c) {
    for (int qr = 0; qr < (int)queens.size(); qr++)
        if (queens[qr] == c ||
            abs(qr - r) == abs(queens[qr] - c))
            return false;
    return true;
}

void place(int r, int n) {
    if (r == n) {
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; i++) board[i][queens[i]] = 'Q';
        res.push_back(board);
        return;
    }
    for (int c = 0; c < n; c++) {
        if (!safe(r, c)) continue;
        queens.push_back(c);
        place(r + 1, n);
        queens.pop_back();   // BACKTRACK
    }
}

function solveNQueens(n) {
  const res = [],
    queens = []; // queens[r] = col

  const safe = (r, c) =>
    queens.every(
      (qc, qr) =>
        qc !== c && Math.abs(qr - r) !== Math.abs(qc - c),
    );

  const place = (r) => {
    if (r === n) {
      res.push(
        queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)),
      );
      return;
    }
    for (let c = 0; c < n; c++) {
      if (!safe(r, c)) continue;
      queens.push(c);
      place(r + 1);
      queens.pop(); // BACKTRACK
    }
  };

  place(0);
  return res;
}

Speed-up: track used columns/diagonals in three boolean sets → O(1) safety checks instead of scanning prior rows.

Undo exactly what you did — remove the piece before trying the next option, and the recursion stays correct.

Common Mistakes

Forgetting to UNDO after the recursive call (board fills up, results explode).
Diagonal check wrong sign: it’s |r1−r2| == |c1−c2|, not r1−c1.
Checking future rows — only earlier rows hold queens.
Missing solutions by returning early instead of exploring all columns.

Complexity

Metric	Value
Time	O(N!) worst
Space	O(N) recursion + board

⚠️ Animation & Content Notice

Constraint Satisfaction

Pattern: N-Queens

⚠️ Animation & Content Notice

N-Queens (n=4)

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern: N-Queens

N-Queens (n=4)

Common Mistakes

Complexity

Premium Content

My Private Notes