Sudoko Solver

Dec 18, 2024 • 3 mins read

Problem Overview

The problem is to solve a classic Sudoku puzzle using an efficient algorithmic approach. A Sudoku board is a 9x9 grid partially filled with numbers between 1 and 9. The objective is to fill the empty cells so that each row, column, and 3x3 sub-grid (also called boxes or blocks) contains all the numbers from 1 to 9 exactly once. The problem requires implementing a function to modify the input board in-place to achieve the solution.

Understanding the Problem

Sudoku puzzles are a perfect example of constraint satisfaction problems. The rules provide constraints we must adhere to while filling the board, which makes direct approaches inefficient for larger grids. A brute-force method of trying every possible number combination is computationally expensive. Thus, we need an intelligent approach, like recursion paired with backtracking, to find valid solutions efficiently.

Sudoku Constraints:

Each number from 1 to 9 must appear only once per row.
Each number from 1 to 9 must appear only once per column.
Each number from 1 to 9 must appear only once per 3x3 block.

Key DSA Concepts and Theory

Recursion

Recursion is a method of solving problems where a function calls itself. The function does this repeatedly to solve smaller instances of the problem until it reaches a base condition. In the context of Sudoku solving, recursion helps in exploring all possible number placements by trying one possibility at a time.

Backtracking

Backtracking is an algorithmic technique for solving problems incrementally and abandoning solutions ("backtracking") as soon as it determines the solution cannot be valid, thus avoiding unnecessary computations. For Sudoku solving, it means placing a number in an empty cell, and recursively checking if it leads to a solution. If it doesn't, the algorithm removes the number (backtracks) and tries the next possibility.

Solution Approach

The solution uses a combination of recursive function calls and backtracking:

Identify an empty cell: Traverse the Sudoku board to find an empty cell (denoted by '.').
Try all possible numbers (1-9): For each empty cell, try placing numbers from 1 to 9.
Check constraints: After placing a number, check if the board remains valid (i.e., constraints are not violated).
Recursive call: If valid, recursively attempt to solve the rest of the board.
Backtrack if needed: If a recursive call indicates no valid solutions, reset the cell and try the next number.
Repeat: Continue until all cells are filled in a valid arrangement.

Here is the code implementation in both C++ and Java.

C++ Code

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
    
private:
    bool solve(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; ++c) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            
                            if (solve(board))
                                return true;
                            else
                                board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; ++i) {
            if (board[i][col] == c || board[row][i] == c || 
                board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }
};

Java Code

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            
                            if (solve(board))
                                return true;
                            else
                                board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c || board[row][i] == c || 
                board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }
}

Time and Space Complexity Analysis

Time Complexity: The worst-case time complexity of this approach is O(9^(n*n)), where n is the size of the board (n=9 in this case). This is because, for each empty cell, we try all 9 numbers, and this process is repeated recursively for each cell.
Space Complexity: The space complexity is O(n*n) due to the recursion stack, where n is the size of the Sudoku board. Since we're modifying the board in-place, no additional space is used to store board states.

Common Mistakes to Avoid

Not correctly implementing the constraints check: Ensure that all checks for rows, columns, and 3x3 grids are properly implemented in the validity check function.
Missing base condition for recursion: The recursive function must have a condition to stop recursion, which in this case, is when all cells are filled with valid numbers.

Additional Resources and References

This article intends to provide a comprehensive guide to understanding the problem of solving a Sudoku puzzle using recursion and backtracking, with detailed explanations, code implementations, and complexity analysis to aid your learning.

Terms & Conditions Privacy Policy Refund Policy