HTML5ANDCSS3Tools and Tutorials

HTML5ANDCSS3Tools and Tutorials

Classic Backtracking Problems — DSA Tutorial - HTML5ANDCSS3

Backtracking

Classic Backtracking Problems

Written by Swapnil RajaPublished 28 Aug 2026

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

PreviousBacktracking Explained NextSorting in JavaScript

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
}

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
}