The problem. Fill a 9 × 9 Sudoku board in place. Each row, each column and each of the nine 3 × 3 boxes must contain the digits 1 to 9 exactly once. Empty cells are ".", and the puzzle has exactly one solution.
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"]]
-> filled in place with the unique solutionFind the first empty cell. Try each digit that doesn't already appear in its row, column or box; write it in and recurse to fill the rest of the board. If the recursion succeeds, the board is solved — return true all the way up. If it fails, erase the digit (un-choose) and try the next one. If no digit fits, return false so the previous cell tries its next digit. This is N-Queens with digits: one choice per empty cell, pruned by the three rules.
Each empty cell tries the digits that fit; a cell with no options sends the search back to the previous guess.
function solveSudoku(board) { const n = board.length, box = Math.sqrt(n); // 9 and 3 for a normal sudoku const ok = (r, c, d) => { for (let i = 0; i < n; i++) { if (board[r][i] === d || board[i][c] === d) return false; // row and column const br = box * Math.floor(r / box) + Math.floor(i / box); const bc = box * Math.floor(c / box) + (i % box); if (board[br][bc] === d) return false; // box } return true; }; const solve = () => { for (let r = 0; r < n; r++) { for (let c = 0; c < n; c++) { if (board[r][c] !== ".") continue; for (let d = 1; d <= n; d++) { if (!ok(r, c, String(d))) continue; board[r][c] = String(d); // choose if (solve()) return true; // explore: the rest worked board[r][c] = "."; // un-choose } return false; // no digit fits: back up } } return true; // no empty cell left: solved }; solve();}Time O(9ᵉ) in the worst case for e empty cells, each with a 27-cell check; in practice the rules cut almost every branch, and typical puzzles solve in milliseconds. Space O(e) for the call stack. Returning true as soon as the board is full stops the search — there's no need to look for other solutions.
Keep the digits used in each row, column and box in sets (or bitmasks) so a check is O(1), and at each step fill the empty cell with the fewest possible digits. A cell with one option needs no guess at all, and a cell with zero options fails immediately — the tree shrinks dramatically. This "most constrained first" rule is how fast solvers work.
function solveSudoku(board) { const rows = Array.from({ length: 9 }, () => new Set()); const cols = Array.from({ length: 9 }, () => new Set()); const boxes = Array.from({ length: 9 }, () => new Set()); const empty = []; const boxOf = (r, c) => 3 * Math.floor(r / 3) + Math.floor(c / 3); for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { const d = board[r][c]; if (d === ".") empty.push([r, c]); else { rows[r].add(d); cols[c].add(d); boxes[boxOf(r, c)].add(d); } } } const options = (r, c) => "123456789".split("").filter((d) => !rows[r].has(d) && !cols[c].has(d) && !boxes[boxOf(r, c)].has(d)); const solve = () => { if (empty.length === 0) return true; let best = 0; // the empty cell with the fewest options for (let k = 1; k < empty.length; k++) { if (options(...empty[k]).length < options(...empty[best]).length) best = k; } const [r, c] = empty[best]; empty[best] = empty[empty.length - 1]; empty.pop(); for (const d of options(r, c)) { board[r][c] = d; rows[r].add(d); cols[c].add(d); boxes[boxOf(r, c)].add(d); if (solve()) return true; board[r][c] = "."; rows[r].delete(d); cols[c].delete(d); boxes[boxOf(r, c)].delete(d); } empty.push([r, c]); // put the cell back for the caller return false; }; solve();}Same exponential worst case, but tiny trees in practice: most cells are forced (one option), so very few real guesses are made. Space O(e) plus the 27 sets.
true up the stack; continuing would erase it.3 * (r / 3) + i / 3 and 3 * (c / 3) + i % 3 walk the 9 cells of r, c's box.Was this helpful?