sudokuSolver

Hard · Recursion · 1 test cases

Write a function that solves a Sudoku puzzle. The input will be a 9x9 board with some cells filled (non-zero) and others empty (zero).

Examples

sudokuSolver([[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]) → [[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]]

Starter code

function sudokuSolver(board) {

}

Complexity of the optimal solution

Time O(9^m), space O(m). This is a backtracking algorithm. In the worst case, it tries to fill 'm' empty cells with up to 9 choices each. This leads to an exponential time complexity of O(9^m). The space complexity is determined by the recursion depth, which is at most m.

Solve sudokuSolver in the browser