Sodoku Solver

XXX. Sudoku Solver

Backtracking

Matrix

Problem Statement:

Write a program to solve a Sudoku puzzle by filling the empty cells, represented as '.' in the board.

• Each row must contain digits 1-9 without repetition
• Each column must contain digits 1-9 without repetition
• Each 3x3 sub-box must contain digits 1-9 without repetition

Implementation:

public void solveSudoku(char[][] board) {
    if(board == null || board.length == 0)
        return;
    solve(board);
}

public boolean solve(char[][] board) {
    // Try each cell
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == '.') {
                // Try each number 1-9
                for (char c = '1'; c <= '9'; c++) {
                    if (valid(board, i, j, c)) {
                        board[i][j] = c;                // Place number
                        if (solve(board)) return true;  // Recursively solve
                        board[i][j] = '.';             // Backtrack
                    }
                }
                return false;                          // No valid number found
            }
        }
    }
    return true;                                       // Board is solved
}

public boolean valid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        // Check row
        if (board[row][i] == c) return false;
        // Check column
        if (board[i][col] == c) return false;
        // Check 3x3 box
        int x = 3 * (row/3) + i/3;
        int y = 3 * (col/3) + i % 3;
        if (board[x][y] == c) return false;
    }
    return true;
}
                

Complexity:

Time Complexity: O(9^m) where m is number of empty cells
Space Complexity: O(1) as board is modified in place

Explanation:

• **Solution Strategy**:
  • Find empty cell ('.')
  • Try numbers 1-9 in that cell
  • Validate each attempt
  • Backtrack if solution not found
• **Validation Check**:
  • Check entire row for duplicates
  • Check entire column for duplicates
  • Check 3x3 sub-box for duplicates
• **Backtracking Logic**:
  • Place number if valid
  • Recursively solve rest of board
  • Remove number if solution not found
  • Try next number