hard

Sudoku Solver

Fill in a partially completed Sudoku board so every row, column, and box is valid.

1. Define the problem

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy these rules: each of the digits 1-9 must occur exactly once in each row, each column, and each of the nine 3x3 sub-boxes of the grid. The character "." indicates an empty cell. Use backtracking that fills the grid cell by cell: try each digit 1-9 in the next empty cell, and prune immediately if that digit already appears in the same row, column, or box — undoing the placement and trying the next digit whenever every option from here leads to a dead end.

Constraints

  • board.length == 9
  • boardi.length == 9
  • boardi[j] is a digit 1-9 or "."
  • It is guaranteed that the input board has only one solution

Example

Inputboard = [["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"]]
Output[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Explanation Every empty cell is filled so that each row, column, and 3x3 box contains the digits 1-9 exactly once.

2. Know the words first

In plain terms

3x3 sub-box
One of the nine non-overlapping 3-by-3 blocks that tile the 9x9 grid — like a row or column, each box must also contain the digits 1-9 exactly once.
3. Visualize the solution

Try each digit in the next empty cell, prune on any conflict

Try each digit in the next empty cell, prune on any conflict
Statusprune

Cell (0,2) is empty. Try 1 — but column 2 already has a 1 at row 6, so this conflicts.

What happens in this step

check digit 1 at row 0, col 2
  row 0 so far:  5 3 [1] . 7 . . . .

isValid checks three things for this cell: the whole row, the whole
column, and the 3x3 box it sits in. 1 is already placed somewhere in
column 2, so this placement is rejected before it's even tried — undo
and move on to the next candidate digit.
Step 1 of 4

Steps to visualize

  1. Move to the next empty cell in the grid.
  2. Try digits 1 through 9 in order, skipping any digit that already appears in this row, column, or 3x3 box.
  3. Place the first digit that has no conflicts and recurse into the next empty cell.
  4. If every digit leads to a dead end further on, undo the last placement and try the next digit at the previous cell.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Try each digit in the next empty cell, prune on any conflict
Statusprune

Cell (0,2) is empty. Try 1 — but column 2 already has a 1 at row 6, so this conflicts.

What happens in this step

check digit 1 at row 0, col 2
  row 0 so far:  5 3 [1] . 7 . . . .

isValid checks three things for this cell: the whole row, the whole
column, and the 3x3 box it sits in. 1 is already placed somewhere in
column 2, so this placement is rejected before it's even tried — undo
and move on to the next candidate digit.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function solveSudoku(board) {
  const grid = board.map((row) => row.slice());

  function isValid(row, col, value) {
    for (let i = 0; i < 9; i++) {
      if (grid[row][i] === value) return false;
      if (grid[i][col] === value) return false;
    }

    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let r = boxRow; r < boxRow + 3; r++) {
      for (let c = boxCol; c < boxCol + 3; c++) {
        if (grid[r][c] === value) return false;
      }
    }

    return true;
  }

  function backtrack(pos) {
    if (pos === 81) {
      return true;
    }

    const row = Math.floor(pos / 9);
    const col = pos % 9;

    if (grid[row][col] !== '.') {
      return backtrack(pos + 1);
    }

    for (let digit = 1; digit <= 9; digit++) {
      const value = String(digit);
      if (isValid(row, col, value)) {
        grid[row][col] = value;
        if (backtrack(pos + 1)) {
          return true;
        }
        grid[row][col] = '.'; // undo
      }
    }

    return false;
  }

  backtrack(0);
  return grid;
}
Time
O(9^m) where m is the number of empty cells
Space
O(1) beyond the grid
6. Test cases

Test cases

InputExpectedCovers
the classic 9x9 puzzle from the docstringthe fully solved 9x9 gridexample from the docstring
the solved grid with only (row 0, col 2) blanked outthe same fully solved 9x9 grid, with 4 restored at (0, 2)a single empty cell forced by its row, column, and box
the solved grid with (row 1, col 1) and (row 1, col 2) blanked outthe same fully solved 9x9 grid, with 7 and 2 restoredtwo adjacent empty cells in the same row, each forced by column and box
the solved grid with only (row 8, col 0) blanked outthe same fully solved 9x9 grid, with 3 restored at (8, 0)a single empty cell forced within the bottom-left box

Keep reading