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.

Solutions

This problem can be solved using backtracking, which is a common technique for solving constraint satisfaction problems like Sudoku. The idea is to fill the cells one by one, and whenever we find that current cell cannot lead to a solution, we empty the cell (backtrack) and move on to the next cell.

public class Solution {
    public void SolveSudoku(char[][] board) {
        Solve(board);
    }

    private bool 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] = '.'; // undo the choice if it leads to no solution
                            }
                        }
                    }
                    return false; // return false if no valid numbers can be placed in the current cell
                }
            }
        }
        return true; // sudoku is solved
    }

    private bool IsValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false; // check column
            if (board[row][i] == c) return false; // check row
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; // check 3*3 box
        }
        return true;
    }
}

In this code, Solve is a recursive function that tries to fill the cells from top to bottom and left to right. For each empty cell, it tries all possible numbers from 1 to 9, and calls itself to fill the next cell. If it finds that the current cell cannot lead to a solution (no valid numbers can be placed or the recursive call returns false), it empties the cell (backtracks) and continues with the next number. If it has tried all numbers and none of them work, it returns false to backtrack to the previous cell. The process continues until all cells are filled.

IsValid is a helper function that checks if a number can be placed in a certain cell according to the Sudoku rules.

The time complexity of this solution is O(9^(nn)), where n is the number of empty cells, because in the worst case we need to try 9 numbers for each empty cell. The space complexity is O(nn) because of the recursion stack (depth-first search).