DSA problem
Sudoku Solver
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; each of the digits 1-9 must occur exactly once in each column; and each of the digits 1-9 must occur exactly once in each of the nine 3x3 sub-boxes of the grid. The . character indicates empty cells. Modify the board in place; you may assume the input is uniquely solvable.
This is the textbook constraint-satisfaction-by-backtracking problem. The naive search of 9^81 boards is hopeless, but with three simple bookkeeping arrays for "what digits are already in this row / column / 3x3 box", we can detect and reject any conflict in O(1) and recurse only when a candidate digit is compatible with all three constraint sets.
The key data structures are three boolean tables: rows[9][10], cols[9][10], and boxes[9][10], where boxes[(r / 3) * 3 + c / 3] indexes the 3x3 box containing cell (r, c). We populate them with the initial digits of the puzzle, then run a DFS that scans cells left to right, top to bottom, skipping already-filled cells and trying digits 1..9 at each empty cell.
For each candidate digit d at cell (r, c), we check whether d is already in rows[r], cols[c], or boxes[b]; if not, we mark d as used in all three sets, write d into the board, and recurse to the next cell. If the recursion succeeds, we propagate true upward; otherwise we unmark, restore the cell to ., and try the next digit. When we reach the end of the board we have a complete legal Sudoku — return true. Time is bounded by 9^k where k is the number of empty cells, but the constraint pruning makes practical runs nearly instant for human-grade puzzles.
Examples
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"]
]The board is filled in-place with the unique solution; row 1 becomes ["5","3","4","6","7","8","9","1","2"], etc.board with only 17 clues (minimum unique-solution Sudoku)The unique completionan almost-complete board with a single empty cellThe board with that one cell filled with the only legal digitConstraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit or '.'.
- It is guaranteed that the input board has only one solution.
- You must modify the input board in place.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.