valid Sudoku

#include <bits/stdc++.h> // Includes common standard libraries like iostream, vector.
using namespace std;     // Use the standard namespace.

// Function to check if placing 'val' at (row, col) is safe according to Sudoku rules.
// 'row', 'col': The coordinates of the cell to check.
// 'suduko': The current state of the Sudoku board. Passed by value, consider 'const &' for efficiency.
// 'val': The digit (1-9) to try placing.
bool isSafe(int row, int col, vector<vector<int>> suduko, int val) {
    // Iterate from 0 to 8 (for 9x9 grid).
    for(int i = 0; i < 9; i++) {
        // 1. Row Check: Check if 'val' already exists in the current row.
        if(suduko[row][i] == val) {
            return false; // Not safe.
        }

        // 2. Column Check: Check if 'val' already exists in the current column.
        if(suduko[i][col] == val) {
            return false; // Not safe.
        }

        // 3. 3x3 Matrix Check: Check if 'val' already exists in the current 3x3 sub-grid.
        // Formula to calculate starting row and column of the 3x3 block:
        // (row / 3) * 3 and (col / 3) * 3
        // i/3 gives row offset (0, 0, 0, 1, 1, 1, 2, 2, 2)
        // i%3 gives col offset (0, 1, 2, 0, 1, 2, 0, 1, 2)
        if(suduko[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == val) {
            return false; // Not safe.
        }
    }

    return true; // If no conflicts found, it's safe to place 'val'.
}

// Recursive backtracking function to solve the Sudoku puzzle.
// 'suduko': The Sudoku board (passed by reference so modifications persist across calls).
// Returns true if a solution is found, false otherwise.
bool solve(vector<vector<int>> &suduko) {
    // Iterate through each cell of the 9x9 Sudoku grid.
    for(int row = 0; row < 9; row++) {
        for(int col = 0; col < 9; col++) {

            // If the current cell is empty (marked by 0).
            if(suduko[row][col] == 0) {

                // Try placing digits from 1 to 9 in the empty cell.
                for(int val = 1; val <= 9; val++) {
                    // Check if 'val' can be safely placed at (row, col).
                    if(isSafe(row, col, suduko, val)) {
                        suduko[row][col] = val; // Make a move: Place 'val'.

                        // Recursive call: Try to solve the rest of the Sudoku.
                        bool nextSol = solve(suduko);
                        if(nextSol) {
                            return true; // If recursive call returns true, a solution is found.
                        } else {
                            // Backtrack: If 'val' didn't lead to a solution, undo the move.
                            suduko[row][col] = 0; // Reset the cell to empty.
                        }
                    }
                }
                // If this point is reached, it means no digit from 1-9 could be placed
                // in the current empty cell that leads to a solution.
                return false; // Current path is invalid, backtrack to previous call.
            }
        }
    }

    // If the nested loops complete without finding any empty cells,
    // it means the Sudoku is completely filled and is a valid solution.
    return true;
}

// Wrapper function to initiate the Sudoku solving process.
// 'suduko': The Sudoku board to be solved (passed by reference, will be modified in place).
void validSuduko(vector<vector<int>> &suduko) {
    solve(suduko); // Call the recursive solver.
}

int main() {
    vector<vector<int>> suduko(9, vector<int>(9, 0)); // Initialize 9x9 Sudoku grid with zeros.

    cout << "Enter the Sudoku puzzle (use 0 for empty cells):" << endl;
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> suduko[i][j]; // Read the Sudoku puzzle from input.
        }
    }

    // Solve the Sudoku. The 'suduko' matrix will be modified in place.
    validSuduko(suduko);

    cout << "Solved Sudoku :" << endl;
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cout << suduko[i][j] << " "; // Print the solved Sudoku.
        }
        cout << endl; // Newline after each row.
    }

    return 0; // Indicate successful execution.
}

/* Example Input for a 9x9 Sudoku:
3 0 6 5 0 8 4 0 0
5 2 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 5 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 0 5 2 0 6 3 0 0
*/

1. Problem Statement

• Goal: Given a partially filled 9x9 Sudoku grid, where 0 represents an empty cell, fill the empty cells such that the resulting grid is a valid Sudoku solution.
• Sudoku Rules:
  • Each row must contain digits 1-9 exactly once.
  • Each column must contain digits 1-9 exactly once.
  • Each of the nine 3x3 sub-grids must contain digits 1-9 exactly once.

2. Approach: Backtracking

• Core Idea: Sudoku is a classic constraint satisfaction problem, perfectly suited for backtracking. We iterate through the cells, and whenever we find an empty cell, we try to place a valid digit (1-9). If placing a digit leads to a solution, we keep it. Otherwise, we “backtrack” (undo the placement) and try another digit.

3. Algorithm Steps

1. isSafe(row, col, suduko, val) Function:

   • Checks if placing val in suduko[row][col] is valid according to Sudoku rules.
   • Checks:
     • Row Check: Iterate through the current row to see if val already exists.
     • Column Check: Iterate through the current col to see if val already exists.
     • 3x3 Sub-grid Check: Determine the starting (row, col) of the 3x3 sub-grid (e.g., 3 * (row / 3) and 3 * (col / 3)). Then, iterate through all 9 cells of that 3x3 sub-grid to see if val already exists.
   • Return: true if val can be safely placed, false otherwise.
   • Note on passing suduko: Passing suduko by value to isSafe (vector<vector<int>> suduko) causes a full copy of the entire 9x9 grid for every check, which is inefficient. It should be passed by constant reference (const vector<vector<int>>& suduko) for better performance.

2. solve(suduko) (Recursive Backtracking Function):

   • Parameters: suduko board (passed by reference to allow modification).
   • Traversal: Uses nested loops to iterate through all cells (row, col) of the 9x9 suduko grid.
   • Finding Empty Cell:
     • If suduko[row][col] == 0 (empty cell):
       • Try Digits: Iterate val from 1 to 9.
       • Check Safety: If isSafe(row, col, suduko, val):
         • Make a Move: Place val in suduko[row][col] = val.
         • Recurse: Call solve(suduko).
         • Success Path: If the recursive call solve(suduko) returns true (meaning a solution was found for the rest of the puzzle), then return true immediately as we found a valid path.
         • Backtrack: If the recursive call returns false (meaning val didn’t lead to a solution), then undo the move: suduko[row][col] = 0. This clears the cell to try the next val.
       • No valid val for current empty cell: If the inner for (val=1 to 9) loop finishes and no val led to a solution for this empty cell, it means the current path is invalid. return false.
     • If not an empty cell: Continue to the next cell.
   • Base Case: If the nested loops complete without finding any empty cells (if(suduko[row][col] == 0) block is never entered), it means the entire Sudoku is filled. This implies a valid solution has been found. return true.

3. validSuduko(vector<vector<int>>& suduko) Function:

   • A simple wrapper function that calls solve(suduko). The function name “validSuduko” is a bit misleading, as it actually solves the Sudoku, not just checks validity.

4. Complexity Analysis

• Time Complexity: Very difficult to precisely determine for Sudoku due to its branching factor and pruning.
  • In the worst case, it can be exponential. A very loose upper bound might be O(9^(N*N)) where N=9.
  • However, with effective pruning from isSafe checks, the practical performance is much better. For a standard 9x9 Sudoku, the number of operations is manageable.
• Space Complexity: O(N*N)
  • suduko board: O(N*N).
  • Recursion stack depth: O(N*N) in the worst case (if every cell needs to be filled and we fill them one by one recursively).

5. Key Concepts

• Backtracking: The core algorithmic technique. We try a candidate, explore possibilities, and undo if it leads to a dead end.
• Recursion: The solve function naturally expresses the recursive nature of trying to fill one cell and then solving the rest.
• Constraint Satisfaction: Sudoku is about satisfying local constraints (row, column, 3x3 box uniqueness) to find a global solution.

---