सुडोकू सॉल्वर LeetCode: एल्गोरिदम मास्टरी का संपूर्ण मार्गदर्शक 🧠✨

// C++ में सुडोकू सॉल्वर का बेसिक इम्प्लीमेंटेशन
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
    
    bool solve(vector<vector<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;
                            board[i][j] = '.'; // बैकट्रैक
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for(int i = 0; i < 9; i++) {
            if(board[i][col] == c) return false;
            if(board[row][i] == c) return false;
            if(board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;
        }
        return true;
    }
};

// ऑप्टिमाइज्ड सॉल्यूशन - बिट मास्किंग के साथ
class OptimizedSudokuSolver {
    int[] rows = new int[9];
    int[] cols = new int[9];
    int[] boxes = new int[9];
    
    public void solveSudoku(char[][] board) {
        // Initialize bit masks
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int mask = 1 << num;
                    rows[i] |= mask;
                    cols[j] |= mask;
                    boxes[(i/3)*3 + j/3] |= mask;
                }
            }
        }
        solve(board, 0, 0);
    }
    
    private boolean solve(char[][] board, int row, int col) {
        if (row == 9) return true;
        if (col == 9) return solve(board, row+1, 0);
        if (board[row][col] != '.') return solve(board, row, col+1);
        
        int boxIdx = (row/3)*3 + col/3;
        int used = rows[row] | cols[col] | boxes[boxIdx];
        
        for (int num = 0; num < 9; num++) {
            int mask = 1 << num;
            if ((used & mask) == 0) {
                // Assign number
                board[row][col] = (char)('1' + num);
                rows[row] |= mask;
                cols[col] |= mask;
                boxes[boxIdx] |= mask;
                
                if (solve(board, row, col+1)) return true;
                
                // Backtrack
                board[row][col] = '.';
                rows[row] ^= mask;
                cols[col] ^= mask;
                boxes[boxIdx] ^= mask;
            }
        }
        return false;
    }
}