Sudoku Solver
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Sudoku Solver * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Sudoku Solver * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Write a program to solve a Sudoku puzzle by filling the empty cells. * - Empty cells are indicated by the character '.'. * - You may assume that there will be only one unique solution. * * Sudoku 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. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * This is a classic Exact Cover / Constraint Satisfaction Problem. * * Algorithm (Backtracking): * We try to fill cells one by one. * * 1. Find Empty: Scan the board to find the first cell (r, c) containing '.'. * - If no empty cells are left, the board is solved. Return true. * * 2. Try Digits: Iterate through digits '1' to '9'. * - Check Validity: Is it safe to place digit 'k' at (r, c)? * Safe if: * a) 'k' is not in Row 'r'. * b) 'k' is not in Column 'c'. * c) 'k' is not in the 3x3 Subgrid covering (r, c). * Subgrid Start: (r / 3) * 3, (c / 3) * 3. * * 3. Recurse: * - If safe, place 'k' at (r, c). * - Recursively call solve() for the rest of the board. * - If the recursive call returns true, propagate true up the stack. * * 4. Backtrack: * - If the recursive call returns false (meaning 'k' led to a dead end), * reset cell (r, c) to '.' and try the next digit. * * 5. Failure: * - If all digits 1-9 fail for a specific empty cell, return false (triggering backtrack in previous step). * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * Grid Size: Fixed 9x9. * * Time Complexity: * O(9^M) where M is the number of empty cells. * Since the board is fixed at 9x9, this is technically O(1) in asymptotic terms, but practically exponential. * Pruning (validity checks) significantly reduces the actual operations. * * Space Complexity: * O(1) - The recursion stack depth is at most 81. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - A 2D character array representing the board. * * Output: * - Modify the array in-place to contain the solution. * * --------------------- * 5. Example * --------------------- * Input: * ["53..7....", "6..195...", ...] * * Logic at (0, 2): * - Try '1': Check row, col, subgrid. Valid? No (1 exists in row 1, col 2, etc). * - Try '2': ... * - Try '4': Valid. Place '4'. Recurse. * * Output: * ["534678912", "672195348", ...] * * ============================================================================================ */ public class SudokuSolver { public int solve(int A) { // TODO: Implement solution return 0; }
public void solveSudoku(char[][] board) {
}
}