Sudoku Solver in JavaScript (Time Complexity: O(9^(n*n)))

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.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: 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"]]
Output: [["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"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

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.

Understanding the Problem

The core challenge of solving a Sudoku puzzle lies in ensuring that each number from 1 to 9 appears exactly once in each row, column, and 3x3 sub-box. This problem is significant in various fields such as constraint satisfaction problems, artificial intelligence, and recreational mathematics. A common pitfall is not considering all constraints simultaneously, leading to invalid solutions.

Approach

To solve the Sudoku puzzle, we can use a backtracking algorithm. The idea is to try placing each number from 1 to 9 in each empty cell and recursively attempt to solve the puzzle. If a number placement leads to a conflict, we backtrack and try the next number.

Naive Solution

A naive solution would involve trying every possible combination of numbers in the empty cells, which is computationally infeasible due to the vast number of possibilities.

Optimized Solution

The optimized solution uses backtracking with constraint propagation. This approach significantly reduces the number of possibilities by eliminating invalid choices early.

Algorithm

Here is a step-by-step breakdown of the backtracking algorithm:

Find an empty cell.
Try placing each number from 1 to 9 in the empty cell.
Check if the number placement is valid (i.e., it doesn't violate Sudoku rules).
If valid, recursively attempt to solve the rest of the board.
If the board is solved, return true.
If not, backtrack by removing the number and trying the next one.
If no number is valid, return false.

Code Implementation

/**
 * Solves the Sudoku puzzle.
 * @param {character[][]} board - The 9x9 Sudoku board.
 * @return {void} Do not return anything, modify board in-place instead.
 */
function solveSudoku(board) {
    // Helper function to check if placing num at board[row][col] is valid
    function isValid(board, row, col, num) {
        for (let i = 0; i < 9; i++) {
            // Check row, column, and 3x3 sub-box
            if (board[row][i] === num || board[i][col] === num || 
                board[Math.floor(row / 3) * 3 + Math.floor(i / 3)][Math.floor(col / 3) * 3 + i % 3] === num) {
                return false;
            }
        }
        return true;
    }

    // Helper function to solve the board using backtracking
    function solve(board) {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    for (let num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (solve(board)) {
                                return true;
                            }
                            board[row][col] = '.'; // Backtrack
                        }
                    }
                    return false; // No valid number found, trigger backtracking
                }
            }
        }
        return true; // Solved
    }

    solve(board);
}

Complexity Analysis

The time complexity of the backtracking algorithm is O(9^(n*n)), where n is the size of the board (9 in this case). The space complexity is O(n*n) due to the recursion stack.

Edge Cases

Potential edge cases include:

A nearly completed board with only one empty cell.
A board with multiple empty cells in a single row, column, or sub-box.

Each algorithm handles these cases by ensuring all constraints are checked before placing a number.

Testing

To test the solution comprehensively, use a variety of test cases:

Simple cases with only a few empty cells.
Complex cases with many empty cells.
Edge cases as mentioned above.

Testing frameworks like Jest or Mocha can be used for automated testing.

Thinking and Problem-Solving Tips

When approaching such problems:

Break down the problem into smaller, manageable parts.
Use diagrams or pseudo-code to visualize the solution.
Practice similar problems to improve problem-solving skills.

Conclusion

Solving Sudoku puzzles programmatically is an excellent exercise in understanding backtracking and constraint satisfaction problems. By practicing and exploring further, one can develop strong problem-solving skills.

Additional Resources

For further reading and practice: