Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. 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.

LeetCode

• https://leetcode.com/problems/sudoku-solver/description/

Examples

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:

Different Approaches

1️⃣ Backtracking

To solve a Sudoku puzzle in real life, imagine the task as filling in a partially completed grid so that every row, column, and 3x3 sub-box contains the digits from 1 to 9 exactly once. This involves trial and error, checking for conflicts with existing digits, and backtracking when a conflict arises. Think of it as trying to fit pieces into a jigsaw puzzle, where each piece (digit) must fit perfectly without violating any rules.

Intuition:

Solving this question can be likened to fitting pieces into a jigsaw puzzle where each piece must fit perfectly without violating any rules. In real life, this means filling in the partially completed grid so that every row, column, and 3x3 sub-box contains the digits from 1 to 9 exactly once. This is done through trial and error: identifying empty cells, attempting to place digits, and checking for conflicts. When a conflict arises, backtrack and try a different digit. This process is naturally recursive, as solving the grid involves solving smaller sub-problems (filling in each cell) that depend on previous placements. By treating each empty cell as a sub-problem and recursively attempting to solve the entire grid, the puzzle can be systematically and efficiently solved.

Approach:

1. Traverse the grid to find the first empty cell. For the empty cell, try placing digits from '1' to '9' one by one.
2. For each digit, check if it is valid according to Sudoku rules (i.e., it doesn't conflict with any digit in the same row, column, or 3x3 sub-box). If a digit is valid, place it in the cell.
3. Recursively attempt to solve the rest of the grid with the current digit placed. If placing the current digit doesn't lead to a solution, reset the cell and try the next digit.
4. Repeat the process until the entire grid is correctly filled, or determine that the puzzle is unsolvable.

Code:

class Solution {
public:
    // This function is called to start solving the Sudoku
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }

    // Recursive function that solves the board using backtracking
    bool solve(vector<vector<char>>& board) {
        // Loop over every cell in the 9x9 board
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                // If the current cell is empty ('.'), we need to fill it
                if (board[row][col] == '.') {

                    // Try placing every digit from '1' to '9'
                    for (char digit = '1'; digit <= '9'; digit++) {

                        // Check if placing this digit at (row, col) is valid
                        if (isValid(board, row, col, digit)) {

                            // Place the digit in the cell
                            board[row][col] = digit;

                            // Recursively solve the rest of the board
                            if (solve(board)) return true;

                            // If it didn’t work out, backtrack: remove the digit
                            board[row][col] = '.';
                        }
                    }

                    // If no digit could be placed in this cell, return false
                    return false;
                }
            }
        }

        // If the loop finishes without finding any empty cell, the board is solved
        return true;
    }

    // Function to check if a digit can be safely placed at (row, col)
    bool isValid(vector<vector<char>>& board, int row, int col, char digit) {
        for (int i = 0; i < 9; i++) {

            // Check if digit already exists in the current row
            if (board[row][i] == digit) return false;

            // Check if digit already exists in the current column
            if (board[i][col] == digit) return false;

            // Check if digit already exists in the current 3x3 subgrid
            // This formula maps 'i' from 0 to 8 into the 3x3 box
            int boxRow = 3 * (row / 3) + i / 3; // Top-left corner of box + row offset
            int boxCol = 3 * (col / 3) + i % 3; // Top-left corner of box + col offset

            if (board[boxRow][boxCol] == digit) return false;
        }

        // If digit is not found in row, column, or box, it's valid
        return true;
    }
};

Complexity Analysis:

• Time Complexity:O(9^(N*N)), as each cell can be filled with 1 to 9 digits and there are n*n cells.
• Space Complexity:O(n), where n is the depth of the recursion stack.