Backtracking

Backtracking

Backtracking builds solutions incrementally and abandons (backtracks) when a solution can't be completed. It's like exploring a maze and returning when you hit a dead end.

N-Queens Problem

function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill(null).map(() => Array(n).fill('.'));
  
  function isSafe(row, col) {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }
    // Check diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false;
    }
    return true;
  }
  
  function backtrack(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.'; // Backtrack
      }
    }
  }
  
  backtrack(0);
  return result;
}

Sudoku Solver

function solveSudoku(board) {
  function isValid(row, col, num) {
    // Check row
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num) return false;
    }
    // Check column
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === num) return false;
    }
    // Check 3x3 box
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[startRow + i][startCol + j] === num) return false;
      }
    }
    return true;
  }
  
  function solve() {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (board[row][col] === '.') {
          for (let num = '1'; num <= '9'; num++) {
            if (isValid(row, col, num)) {

  

    
Learn More
    

      
        
GeeksforGeeks: Backtracking
        
Deep dive into Backtracking algorithms with examples like N-Queens.
      
      
        
LeetCode: Backtracking
        
Practice constructing solutions incrementally with backtracking.
      
    
  

              board[row][col] = num;
              if (solve()) return true;
              board[row][col] = '.'; // Backtrack
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  
  solve();
  return board;
}