Sudoku solver

Hard

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"]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}