Backtracking grid

Sudoku Solver Concept

syntax

Fill empty cells one at a time.
For each empty cell, try digits 1-9.
Check row, column, and 3x3 box constraints.
Backtrack if no valid digit fits.

example

// JavaScript
function solveSudoku(board) {
  function isValid(board, row, col, num) {
    const ch = String(num);
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ch) return false; // row
      if (board[i][col] === ch) return false; // column
      const boxR = 3 * Math.floor(row / 3) + Math.floor(i / 3);
      const boxC = 3 * Math.floor(col / 3) + (i % 3);
      if (board[boxR][boxC] === ch) return false; // box
    }
    return true;
  }

  function solve(board) {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] === '.') {
          for (let num = 1; num <= 9; num++) {
            if (isValid(board, r, c, num)) {
              board[r][c] = String(num);
              if (solve(board)) return true;
              board[r][c] = '.';
            }
          }
          return false; // no valid digit → backtrack
        }
      }
    }
    return true; // all cells filled
  }
  solve(board);
}

# Python
def solve_sudoku(board):
    def is_valid(row, col, num):
        ch = str(num)
        for i in range(9):
            if board[row][i] == ch: return False
            if board[i][col] == ch: return False
            br = 3 * (row // 3) + i // 3
            bc = 3 * (col // 3) + i % 3
            if board[br][bc] == ch: return False
        return True

    def solve():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for num in range(1, 10):
                        if is_valid(r, c, num):
                            board[r][c] = str(num)
                            if solve(): return True
                            board[r][c] = '.'
                    return False
        return True
    solve()

output

Fills in all '.' cells with valid digits 1-9.

Note Time O(9^(empty cells)) worst case, but pruning makes it much faster in practice. Optimization: use sets for each row, column, and box to check validity in O(1) instead of O(9). Finding the cell with fewest candidates first (MRV heuristic) dramatically speeds up solving.

Word Search in Grid

DSA · Recursion & Backtracking

syntax

DFS from each cell. At each step, check if the current cell matches the next character.
Mark cell as visited (temporarily modify it), recurse in 4 directions, then unmark.

example

// JavaScript
function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    const saved = board[r][c];
    board[r][c] = '#'; // mark visited
    const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1)
               || dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
    board[r][c] = saved; // unmark
    return found;
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

# Python
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False
        saved = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1)
                 or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

output

board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
exist(board, 'ABCCED') → True

Note Time O(m * n * 4^L) where L = word length. The temporary cell modification is a clean alternative to a separate visited set. Always restore the cell after backtracking. Optimization: check if the board has all needed characters before starting DFS.

DSAInterview Prep