Sudoku Solver in C++ (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 is to fill the empty cells such that each digit 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 to overlook the constraints, leading to invalid solutions.

Approach

To solve the Sudoku puzzle, we can use a backtracking algorithm. The idea is to try filling the empty cells one by one and backtrack if we encounter an invalid state. Here's a step-by-step approach:

Find an empty cell.
Try placing digits from 1 to 9 in the empty cell.
Check if the digit placement is valid (i.e., it doesn't violate Sudoku rules).
If valid, recursively attempt to fill the next empty cell.
If invalid or if we can't fill the next cell, backtrack and try the next digit.
Repeat until the board is completely filled.

Let's break down the algorithm and its implementation in C++.

Algorithm

Here's a detailed breakdown of the backtracking algorithm:

Find an empty cell: Iterate through the board to find a cell with the '.' character.
Try placing digits: For each digit from 1 to 9, check if placing the digit in the current cell is valid.
Check validity: Ensure the digit doesn't already exist in the current row, column, or 3x3 sub-box.
Recursive call: If the digit placement is valid, make a recursive call to attempt to fill the next empty cell.
Backtrack: If the recursive call returns false, reset the cell and try the next digit.
Completion: If all cells are filled, the board is solved.

Code Implementation

#include <iostream>
#include <vector>

using namespace std;

// Function to check if placing a number is valid
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
    for (int i = 0; i < 9; i++) {
        // Check row
        if (board[row][i] == num) return false;
        // Check column
        if (board[i][col] == num) return false;
        // Check 3x3 sub-box
        if (board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) return false;
    }
    return true;
}

// Backtracking function to solve the Sudoku
bool solveSudoku(vector<vector<char>>& board) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == '.') {
                for (char num = '1'; num <= '9'; num++) {
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num;
                        if (solveSudoku(board)) return true;
                        board[row][col] = '.'; // Backtrack
                    }
                }
                return false; // No valid number found
            }
        }
    }
    return true; // Solved
}

int main() {
    vector<vector<char>> 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'}
    };

    if (solveSudoku(board)) {
        for (const auto& row : board) {
            for (const auto& cell : row) {
                cout << cell << ' ';
            }
            cout << endl;
        }
    } else {
        cout << "No solution exists" << endl;
    }

    return 0;
}

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). This is because, in the worst case, we might have to try all 9 digits for each cell. The space complexity is O(n*n) due to the recursion stack and the board itself.

Edge Cases

Potential edge cases include:

Boards that are already solved.
Boards with only one empty cell.
Boards with multiple empty cells but only one valid solution.

Each algorithm should handle these cases effectively by ensuring the constraints are always met.

Testing

To test the solution comprehensively, consider the following test cases:

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

Using a testing framework like Google Test can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Use a systematic approach to explore all possibilities.
Practice solving similar problems to improve your skills.

Conclusion

Solving a Sudoku puzzle using backtracking is a classic example of constraint satisfaction problems. Understanding and implementing this algorithm helps improve problem-solving skills and provides a foundation for tackling more complex problems.

Additional Resources

For further reading and practice, consider the following resources: