Backtracking: Exploring Possibilities (N-Queens, Sudoku)

TL;DR: Backtracking is an algorithmic technique for finding solutions by incrementally building candidates and "undoing" choices when a path proves fruitless. You'll learn:

1. What Backtracking is and its systematic search approach.
2. How Stacks (explicit and implicit) are fundamental to backtracking.
3. Code examples for classic problems like N-Queens and Sudoku Solver in JavaScript.
4. Key components: choices, constraints, and goals.
5. Best practices for designing effective backtracking solutions.

🎓 New to JavaScript? Start with the JavaScript Essentials Course for a solid foundation before diving into advanced algorithms.
💡 Building DSA skills? Check out Mastering Data Structures & Algorithms in JS to level up your problem–solving toolkit.
🔄 Need a recursion refresher? Check out Understanding Recursion in JS for clear, hands-on examples.
🧩 Explore related structures: Learn about Linked Lists, Stacks & Queues with JavaScript Examples to see more backtracking foundations in action.
🎯 Ready to practice? Apply your skills with the Codyssey Challenges I’ve created.

What Is Backtracking?

Backtracking is an algorithmic paradigm that attempts to solve problems by recursively trying to build a solution incrementally, one piece at a time. It's often used for problems that involve finding all (or some) solutions satisfying certain constraints, rather than finding an optimal one (though it can be adapted).

Think of it like navigating a maze: you try a path, and if it leads to a dead end, you retrace your steps (backtrack) to the last decision point and try a different path.

The core idea revolves around:

• Choices: At each step, there are one or more options to choose from.
• Constraints: Rules that must be satisfied for a solution to be valid.
• Goal: A condition that determines when a complete, valid solution has been found.

When a choice leads to a state that violates a constraint or cannot lead to a solution, the algorithm "backtracks" by undoing the last choice and exploring another option.

The Role of Stacks in Backtracking

The LIFO (Last-In, First-Out) nature of stacks is perfectly suited for managing the decision points and state changes in a backtracking algorithm.

1. Implicit Stacks (Recursion)

Most commonly, backtracking is implemented using recursion. This leverages the call stack automatically:

• Making a Choice (Recursive Call): When your recursive function makes a choice and calls itself with a new state (e.g., placing a queen on the board, trying a number in a Sudoku cell), a new stack frame is pushed onto the call stack. This frame stores all the context for that particular choice.
• Backtracking (Function Return): If a recursive call hits a dead end or fails to find a solution, it simply returns. This action pops its stack frame off the call stack, restoring the state of the previous function call. This effectively "undoes" the last decision, allowing the previous call to try a different path.

This implicit management by the call stack makes recursive backtracking solutions often concise and elegant.

2. Explicit Stacks

While less common for pure backtracking (due to recursion's elegance), you can also implement backtracking iteratively using an explicit stack:

• You would manually push the current state (e.g., coordinates, choices made so far) onto a custom stack when exploring a new path.
• When a dead end is reached, you would pop elements from your stack to revert to a previous decision point.

This approach is useful when dealing with very deep recursion that might lead to a "Stack Overflow" error in languages with limited call stack depth.

Real-World Problems with Backtracking

Let's look at two classic examples:

1. N-Queens Problem

The N-Queens problem asks: "How can N chess queens be placed on an N×N chessboard so that no two queens attack each other?" (Queens attack horizontally, vertically, and diagonally).

This is a perfect fit for backtracking:

• Choices: For each row, choose a column to place a queen.
• Constraints: No two queens can share the same row, column, or diagonal.
• Goal: Place N queens without any attacks.

// JavaScript: N-Queens Problem (simplified for concept)
function solveNQueens(n) {
  const board = Array.from({ length: n }, () => Array(n).fill('.'))
  const solutions = []

  // Helper function to check if a queen can be placed at (row, col)
  function isSafe(row, col) {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false
    }
    // Check upper-left diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false
    }
    // Check upper-right diagonal
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false
    }
    return true
  }

  // Recursive backtracking function
  function backtrack(row) {
    // Base case: If all queens are placed
    if (row === n) {
      solutions.push(board.map((r) => r.join(''))) // Add a copy of the current board
      return
    }

    // Try placing a queen in each column of the current row
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q' // Make a choice
        backtrack(row + 1) // Recurse to the next row
        board[row][col] = '.' // Undo the choice (backtrack)
      }
    }
  }

  backtrack(0) // Start from the first row
  return solutions
}

// Example for N=4
const nQueensSolutions = solveNQueens(4)
console.log(`Found ${nQueensSolutions.length} solutions for 4-Queens:`)
nQueensSolutions.forEach((sol) => console.log(sol))
/* Example output for one solution:
[
  " . Q .",
  "Q . . .",
  ". . . Q",
  ". Q . ."
]
*/

In the backtrack function, when board[row][col] = 'Q' is executed, we are making a choice and pushing a new state onto the call stack with backtrack(row + 1). If that path doesn't lead to a solution, the backtrack(row + 1) call returns, and board[row][col] = '.' effectively "undoes" that choice, allowing the loop to try the next col.

2. Sudoku Solver

Given a partially filled 9×9 Sudoku grid, the goal is to fill the remaining empty cells such that every row, column, and 3×3 subgrid contains all of the digits from 1 to 9.

• Choices: For each empty cell, try placing a digit from 1 to 9.
• Constraints: The digit must not already exist in the same row, column, or 3×3 subgrid.
• Goal: Fill all empty cells according to the rules.

// JavaScript: Sudoku Solver (simplified for concept)
function solveSudoku(board) {
  const N = 9

  function isValid(row, col, num) {
    // Check row
    for (let x = 0; x < N; x++) {
      if (board[row][x] === num) return false
    }
    // Check column
    for (let x = 0; x < N; x++) {
      if (board[x][col] === num) return false
    }
    // Check 3x3 box
    const startRow = row - (row % 3)
    const startCol = col - (col % 3)
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[i + startRow][j + startCol] === num) return false
      }
    }
    return true
  }

  function findEmpty() {
    for (let r = 0; r < N; r++) {
      for (let c = 0; c < N; c++) {
        if (board[r][c] === '.') {
          // '.' represents an empty cell
          return [r, c]
        }
      }
    }
    return null // No empty cells left
  }

  function backtrack() {
    const emptyPos = findEmpty()
    if (!emptyPos) {
      return true // All cells filled, puzzle solved!
    }

    const [row, col] = emptyPos

    for (let num = 1; num <= 9; num++) {
      if (isValid(row, col, String(num))) {
        // Convert num to string to match board char
        board[row][col] = String(num) // Make a choice
        if (backtrack()) {
          return true // If this choice leads to a solution, propagate true
        }
        board[row][col] = '.' // Undo the choice (backtrack)
      }
    }
    return false // No number worked for this cell
  }

  backtrack() // Start the solving process
  return board
}

// Example Sudoku Board
const sudokuBoard = [
  ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
  ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
  ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
  ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
  ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
  ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
  ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
  ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
  ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
]

console.log('Original Sudoku:')
sudokuBoard.forEach((row) => console.log(row.join(' ')))

solveSudoku(sudokuBoard)

console.log('\nSolved Sudoku:')
sudokuBoard.forEach((row) => console.log(row.join(' ')))

Similar to N-Queens, when board[row][col] = String(num) is set, a choice is made, and a recursive call to backtrack() is initiated. If that path doesn't lead to a full solution (if (backtrack()) is false), the board[row][col] = '.' line "undoes" the assignment, and the loop proceeds to try the next number.

Designing Backtracking Solutions: Best Practices

1. Define Your State: Clearly understand what information needs to be maintained at each recursive call (e.g., current row, current board configuration).
2. Identify Base Cases: When does your recursion stop? This is usually when a full solution is found or when it's impossible to continue.
3. Define Choices: What are the possible options at each step?
4. Implement Constraints/Validity Checks: How do you determine if a partial solution is valid or if a choice leads to a dead end? Pruning (stopping early when a path is invalid) is crucial for efficiency.
5. Make/Undo Choices: Implement the "explore" (make a choice, recurse) and "backtrack" (undo the choice) steps clearly. This usually involves modifying a shared data structure and then reverting it after the recursive call.

Conclusion

Backtracking is a powerful and versatile algorithmic technique for systematically exploring a search space. Its reliance on the stack (explicitly or implicitly through recursion) makes it exceptionally well-suited for problems where you need to make a series of choices, evaluate their consequences, and then efficiently "undo" those choices if they lead to an invalid or non-optimal path. Mastering backtracking opens doors to solving a wide range of complex combinatorial and decision problems.