Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Backtracking

Classic Backtracking Problems

Written by Updated

These three cover the shapes: placing pieces under constraints, searching a grid, and filling in blanks. Everything else is a variation.

N-Queens - placing under constraints

Place n queens on an n×n board so none attack each other. One queen per row, so the only question is which column.

N-Queens

javascript

function solveNQueens(n) {
  const results = []
  const columns = new Set()
  const diagonal = new Set()      // row - col
  const antiDiagonal = new Set()  // row + col
  const placement = []

  function place(row) {
    if (row === n) {
      results.push([...placement])
      return
    }

    for (let col = 0; col < n; col++) {
      // O(1) conflict check instead of scanning the board.
      if (columns.has(col)) continue
      if (diagonal.has(row - col)) continue
      if (antiDiagonal.has(row + col)) continue

      columns.add(col)
      diagonal.add(row - col)
      antiDiagonal.add(row + col)
      placement.push(col)

      place(row + 1)

      placement.pop()
      antiDiagonal.delete(row + col)
      diagonal.delete(row - col)
      columns.delete(col)
    }
  }

  place(0)
  return results
}

console.log(solveNQueens(8).length)  // 92

The three sets are the trick. row - col is constant along one diagonal and row + col along the other, so a conflict check is a hash lookup rather than a board scan.

Word search - backtracking on a grid

Find a word in a grid

javascript

function exist(board, word) {
  const rows = board.length
  const cols = board[0].length

  function search(row, col, index) {
    if (index === word.length) return true
    if (row < 0 || row >= rows || col < 0 || col >= cols) return false
    if (board[row][col] !== word[index]) return false

    // Mark as used so this path cannot reuse the same cell.
    const original = board[row][col]
    board[row][col] = "#"

    const found =
      search(row + 1, col, index + 1) ||
      search(row - 1, col, index + 1) ||
      search(row, col + 1, index + 1) ||
      search(row, col - 1, index + 1)

    board[row][col] = original   // restore on the way out
    return found
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (search(r, c, 0)) return true
    }
  }

  return false
}

const demoGrid = [["c", "a"], ["b", "t"]]
console.log(exist(demoGrid, "cat"))   // true
console.log(exist(demoGrid, "cbt"))   // false

Overwriting the cell and restoring it is the visited set - no extra structure needed. Forgetting to restore is the classic bug, and it produces false negatives that are hard to spot.

Sudoku - filling blanks

Sudoku solver

javascript

function solveSudoku(board) {
  function isValid(row, col, ch) {
    const boxRow = 3 * Math.floor(row / 3)
    const boxCol = 3 * Math.floor(col / 3)

    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ch) return false
      if (board[i][col] === ch) return false
      if (board[boxRow + Math.floor(i / 3)][boxCol + (i % 3)] === ch) return false
    }

    return true
  }

  function solve() {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (board[row][col] !== ".") continue

        for (let d = 1; d <= 9; d++) {
          const ch = String(d)
          if (!isValid(row, col, ch)) continue

          board[row][col] = ch
          if (solve()) return true
          board[row][col] = "."    // undo
        }

        return false   // no digit fits — this branch is dead
      }
    }

    return true   // no blanks left
  }

  solve()
  return board
}

console.log("solveSudoku fills the board in place and returns nothing")

The return false after the digit loop is essential. It says "nothing works here", which forces the caller to undo its own choice - that is the backtrack.

The common thread

  • State is changed on the way down and restored on the way up.
  • Invalid branches are abandoned as early as possible.
  • A conflict check should be O(1) - use sets, not scans.
  • The base case returns; every other path must undo before it does.

Avoiding duplicate results

When the input contains repeats, the naive recursion produces the same combination several times. The fix is to sort first and then skip a value that equals its predecessor at the same depth - not globally, only among siblings in the tree.

Subsets with duplicates

javascript

function subsetsWithDup(nums) {
  const sorted = [...nums].sort((a, b) => a - b)
  const results = []
  const path = []

  function backtrack(start) {
    results.push([...path])

    for (let i = start; i < sorted.length; i++) {
      // Skip a repeat only when it is a sibling, not when nested.
      if (i > start && sorted[i] === sorted[i - 1]) continue

      path.push(sorted[i])
      backtrack(i + 1)
      path.pop()
    }
  }

  backtrack(0)
  return results
}

console.log(subsetsWithDup([1, 2, 2]).length)  // 6, not 8

The condition is i > start, not i > 0. The first is "this is a sibling of a value I already tried at this level"; the second would wrongly block legitimate nesting like [2, 2].

The recurring set

  • Subsets - include or exclude each element.
  • Permutations - track which indices are used.
  • Combination sum - recurse on the same index when reuse is allowed.
  • N-Queens - validity check over columns and both diagonals.
  • Word search - mark the grid cell, recurse, unmark it.
PreviousBacktracking ExplainedNextSorting in JavaScript