Sudoku Solver | Problems

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row, column, and each of the 9 3x3 sub-boxes of the grid.

Sample Input

board = [["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"]]

Sample Output

Solved Sudoku Board

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'

Topics

Backtracking Recursion

Use backtracking to fill empty cells one by one. For each cell, try digits 1–9 and validate against Sudoku row, column, and 3×3 box constraints. If no digit works, backtrack.

function solveSudoku(board) {
  function isValid(row, col, ch) {
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 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 r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;
        for (let d = 1; d <= 9; d++) {
          const ch = String(d);
          if (isValid(r, c, ch)) {
            board[r][c] = ch;
            if (solve()) return true;
            board[r][c] = '.';
          }
        }
        return false;
      }
    }
    return true;
  }

  solve();
}

Time: O(9^(empty cells)) — bounded by the fixed board size Space: O(81) recursion depth

Saved in this browser only. Private to you.