Sudoku solver
Problem
Fill the empty cells (".") of a 9 × 9 Sudoku so that each row, each column and each 3 × 3 box contains the digits 1–9 exactly once. The puzzle has exactly one solution.
Example 1
Input: a partially filled 9 × 9 board Output: the completed board
Also asked as: Sudoku Solver
Test cases
Case 1
Input: [["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"]] Expected: [["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"]]
Case 2
Input: [[".","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",".","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","."]] Expected: [["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"]]
Case 3
Input: [["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"],[".",".",".",".",".",".",".",".","."],["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"]] Expected: [["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"]]
View solutionHide solution1 approach
1. Fill the first empty cell, try 1–9, recurse
Time exponential (fast in practice)Space O(1)
For each empty cell try every digit that is valid in its row, column and 3×3 box; recurse; undo if the branch fails.
function solveSudoku(board) { const valid = (r, c, ch) => { for (let i = 0; i < 9; i++) { if (board[r][i] === ch || board[i][c] === ch) return false; const br = 3 * ((r / 3) | 0) + ((i / 3) | 0); const bc = 3 * ((c / 3) | 0) + (i % 3); if (board[br][bc] === ch) return false; } return true; }; const bt = () => { 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 (valid(r, c, ch)) { board[r][c] = ch; if (bt()) return true; board[r][c] = '.'; } } return false; } return true; }; bt(); return board;}