Building a Sudoku Solver: Challenges and Learnings

sudoku Game

I recently decided to tackle the Sudoku solver problem I saw on LeetCode and enhance it with a user interface (UI). After spending about 20 minutes brainstorming how to create the grid lines, I watched a video that helped clarify my approach. This experience taught me an important lesson: setting a time limit for problem-solving and seeking help when needed can save you valuable time.

Challenges Faced

While working on the project, I encountered several challenges, but none were too major:

1. Using innerText: I initially struggled with how to correctly use innerText to manipulate the displayed numbers.
2. Integer Division: I had to switch to Math.floor() since JavaScript doesn't support integer division natively. In many programming languages, dividing two integers would yield the floor of the result (e.g., 5/2 equals 2), but JavaScript will return 2.5. While this behavior is mathematically correct, it required me to adapt my approach.
3. Understanding Backtracking: It took some time for me to fully grasp how backtracking works and how to implement it effectively in my Sudoku solver.

Understanding Backtracking and Recursion

Backtracking is a powerful algorithmic technique often implemented using recursion. In the context of the Sudoku solver, here’s how it works:

1. Recursive Function: We loop through the Sudoku grid to find empty cells. For each empty cell, we try numbers from 1 to 9 to see if any are valid according to Sudoku rules.
2. Inserting Valid Numbers: When we find a valid number, we insert it into the cell and call the function recursively to continue solving the rest of the board.
3. Backtracking: If we reach a point where no valid number can be placed in the current cell, we return false and backtrack. This involves removing the last inserted number and trying the next number in the sequence.

“For you to be able to go back you have to know where you came from”

While going through this i had questions that helped me understand the solution.

How Recursion Works in the Solver

When a recursive function is called, it is added to the stack with its local variables. This means that when we backtrack, we can still access those variables. Here’s a step-by-step overview of how the algorithm proceeds:

• Insert a number into the current cell.
• Call the function again to try and insert numbers into the next cells.
• If no valid number can be placed, return false, remove the last inserted number, and try the next number.
• This process continues until the board is completely filled or no numbers can be placed.

function solveSudoku(grid):
    # Find the next empty cell (denoted by 0 in the grid)
    empty_cell = findEmptyCell(grid)
    
    # Base case: if there are no more empty cells, we are done!
    if no empty cells:
        return True
    
    # Extract row and column of the empty cell
    row, col = empty_cell

    # Try placing numbers 1 to 9 in the empty cell
    for num from 1 to 9:
        
        # Check if the number is valid (doesn't violate Sudoku rules)
        if isValid(grid, row, col, num):
            
            # Place the number in the cell
            grid[row][col] = num
            
            # Recursively try to solve the rest of the grid
            if solveSudoku(grid):
                return True  # Solution found, return success
            
            # If placing the number didn't lead to a solution, backtrack
            grid[row][col] = 0  # Undo the current choice and try the next number
    
    # If no number from 1 to 9 can be placed, return failure (backtrack further)
    return False

Keeping Track of Previous Numbers

A common question I had was how the algorithm keeps track of the numbers inserted in previous cells. The process works as follows:

• As we loop through numbers 1 to 9, if we find that a number (e.g., 1) is valid, we place it in the current cell and move to the next cell.
• If we encounter a cell where no valid numbers can be placed, we backtrack to the previous cell, reset its value to 0, and then try the next number (e.g., 2).
• This systematic approach ensures that we explore all possibilities until a solution is found or all options are exhausted.

Conclusion

In conclusion, developing the Sudoku solver was a rewarding challenge. The combination of implementing the UI and solving the algorithm itself made it an enriching experience.

Key Takeaways:

• Recursion and backtracking are essential for solving problems like Sudoku, though they can consume more memory due to the function stack.
• Setting a time limit for problem-solving can help manage frustration and encourage seeking assistance when necessary.
• Understanding the nuances of JavaScript, such as the lack of native integer division, is crucial for effective coding.

You can view my complete solution here on CodePen sudoku (codepen.io). Feel free to leave a comment with your thoughts or questions!