🧩 Sudoku Solver – Complete In-Depth Explanation

Sudoku is a popular logic-based number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids (also called "boxes" or "regions") contain all of the digits from 1 to 9 exactly once.

📌 Why is Sudoku Important?

• 💡 Demonstrates backtracking algorithms.
• 🧩 Classic constraint satisfaction problem.
• ⚙️ Good example for understanding recursive problem-solving.

📌 Understanding Sudoku with an Example

Here's an example of a Sudoku puzzle:

                  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
                  . . . | . . . | . . .
                

The goal is to fill in the empty cells (represented by '.') with digits from 1 to 9 so that the rules of Sudoku are satisfied.

🔹 Key Points

• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each 3x3 subgrid must contain the digits 1-9 without repetition.

🛠 Solution Approach (Backtracking)

The most common approach to solving Sudoku is using backtracking:

1. Find an empty cell.
2. Try filling it with a digit from 1 to 9.
3. Check if the digit is valid (doesn't violate Sudoku rules).
4. If valid, recursively try to solve the rest of the puzzle.
5. If the recursive call is successful, the puzzle is solved!
6. If the recursive call is not successful, backtrack: reset the cell to empty and try a different digit.
7. If all digits have been tried and none work, the puzzle has no solution (or the current path is incorrect).

                  #include 
                  #include 
              
                  using namespace std;
              
                  bool isSafe(vector>& grid, int row, int col, int num) {
                      // Check row
                      for (int x = 0; x < 9; x++)
                          if (grid[row][x] == num) return false;
              
                      // Check column
                      for (int x = 0; x < 9; x++)
                          if (grid[x][col] == num) return false;
              
                      // Check 3x3 box
                      int startRow = row - row % 3;
                      int startCol = col - col % 3;
                      for (int i = 0; i < 3; i++)
                          for (int j = 0; j < 3; j++)
                              if (grid[i + startRow][j + startCol] == num) return false;
              
                      return true;
                  }
              
                  bool solveSudoku(vector>& grid) {
                      for (int row = 0; row < 9; row++) {
                          for (int col = 0; col < 9; col++) {
                              if (grid[row][col] == 0) { // Find an empty cell
                                  for (int num = 1; num <= 9; num++) {
                                      if (isSafe(grid, row, col, num)) {
                                          grid[row][col] = num;
              
                                          if (solveSudoku(grid)) return true; // Recursively solve
                                          else grid[row][col] = 0; // Backtrack
                                      }
                                  }
                                  return false; // No valid number found
                              }
                          }
                      }
                      return true; // Puzzle solved
                  }
              
                  int main() {
                      vector> grid = {
                          {5, 3, 0, 0, 7, 0, 0, 0, 0},
                          {6, 0, 0, 1, 9, 5, 0, 0, 0},
                          {0, 9, 8, 0, 0, 0, 0, 6, 0},
                          {8, 0, 0, 0, 6, 0, 0, 0, 3},
                          {4, 0, 0, 8, 0, 3, 0, 0, 1},
                          {7, 0, 0, 0, 2, 0, 0, 0, 6},
                          {0, 6, 0, 0, 0, 0, 2, 8, 0},
                          {0, 0, 0, 4, 1, 9, 0, 0, 5},
                          {0, 0, 0, 0, 0, 0, 0, 0, 0}
                      };
              
                      if (solveSudoku(grid)) {
                          cout << "Solution:\n";
                          for (int i = 0; i < 9; i++) {
                              for (int j = 0; j < 9; j++)
                                  cout << grid[i][j] << " ";
                              cout << endl;
                          }
                      } else {
                          cout << "No solution exists.\n";
                      }
              
                      return 0;
                  }
                

⏳ Time Complexity Analysis

The worst-case time complexity of the backtracking Sudoku solver is exponential. However, with proper constraints and pruning (checking `isSafe` efficiently), the practical runtime is often much faster.

🌍 Real-World Applications of Constraint Satisfaction

• 📅 Scheduling (timetables, appointments).
• 🏭 Resource allocation.
• 🤖 Artificial intelligence (planning).

🔗 Next Topics

• 🔙 Backtracking
• 🧩 Constraint Satisfaction Problems