LeetCode //C - 37. Sudoku Solver

37. Sudoku Solver

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.
 

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.

From: LeetCode
Link: 29. Divide Two Integers

Solution:

Ideas:

1. Sudoku Rules: To solve Sudoku, the code must respect the three main rules of the game:

• Each number from 1 to 9 must appear exactly once in each row.
• Each number must appear exactly once in each column.
• Each number must appear exactly once in each of the nine 3x3 subgrids of the grid.

2. Backtracking Framework:

• The code systematically tries to fill the board with valid numbers.
• It starts from the top-left cell and moves row by row, left to right.
• When it finds an empty cell (marked with a ‘.’), it tries to place a valid number (from ‘1’ to ‘9’) in that cell.
• The validity of a number placement is checked by ensuring that the same number does not already exist in the same row, column, or 3x3 subgrid.
• If a valid number is found, the code places the number and moves to the next cell.
• If no valid number can be placed in a cell, it means the previous number placements have led to a dead end. In such a case, the algorithm backtracks, which means it goes back to the previous cell and tries a different number.
• This process continues until the board is either completely filled with valid numbers (solved) or it is determined that no solution is possible with the current number placements (unsolvable).

3. The isValid Function: This helper function checks if a certain number can be placed at a given row and column without breaking the Sudoku rules.

4. The solve Function: This is the recursive function that implements the backtracking. It tries to place every number from ‘1’ to ‘9’ in each empty cell and calls itself to try to solve the rest of the board from that point. If it eventually hits a point where no numbers can fit, it returns false, causing the previous level of recursion to try the next number.

5. The solveSudoku Function: This is the function you call to solve the board. It calls the solve function and passes the board to it.

6. In-Place Modification: The board is modified in place. This means that the original 2D array of characters that you pass to the solveSudoku function will be changed to reflect the solution to the puzzle by the time the function returns. There is no need to print or return the board from the function because it directly modifies the array you pass to it.

7. Guaranteed Solution: The problem statement you provided guarantees that there is one and only one solution for the input board, so the code does not handle multiple solution scenarios or no-solution scenarios.

Code:

bool isValid(char** board, int row, int col, char num){
    for(int i = 0; i < 9; i++) {
        // Check if the number is already used in the current row or column
        if(board[row][i] == num || board[i][col] == num) return false;
        // Check if the number is in the current 3x3 box
        if(board[3*(row/3) + i/3][3*(col/3) + i%3] == num) return false;
    }
    return true;
}

bool solve(char** board) {
    for(int row = 0; row < 9; row++) {
        for(int col = 0; col < 9; col++) {
            // Skip non-empty cells
            if(board[row][col] != '.') continue;
            
            for(char num = '1'; num <= '9'; num++){
                // If placing the current num in board[row][col] doesn't violate Sudoku rules
                if(isValid(board, row, col, num)) {
                    board[row][col] = num;
                    
                    // Recursively proceed to fill the rest of the board
                    if(solve(board)) return true;
                    
                    // If the decision leads to a dead end, undo it
                    board[row][col] = '.';
                }
            }
            // If no number can be placed in this cell, backtrack
            return false;
        }
    }
    // If all cells are filled, the puzzle is solved
    return true;
}

void solveSudoku(char** board, int boardSize, int* boardColSize) {
    solve(board);
}