Sudoku Solver

A backtracking algorithm implementation with conflict tracking and optimization strategies.

Algorithm Details

Backtracking with Conflict Tracking: This solver uses an optimized backtracking algorithm that maintains conflict matrices for rows, columns, and 3x3 squares to quickly determine valid moves.

Key Features:

• Conflict Matrices: Tracks which numbers are already used in each row, column, and square
• Best Cell Selection: Always chooses the cell with the fewest possible valid numbers
• Early Termination: Stops when a cell has only one possible value
• Backtracking: Undoes moves when a path leads to a dead end

Performance Metrics:

• Recursion Count: Number of recursive calls made
• Backtrack Count: Number of times the algorithm had to undo moves
• Solve Time: Total time taken to solve the puzzle

Bit Masking Optimization

Advanced Performance Technique: The current implementation uses MRV (Minimum Remaining Values) heuristic but can be significantly optimized by adding bit masking, a technique that uses individual bits in integers to represent data more efficiently.

Current vs Optimized Approach:

MRV (Minimum Remaining Values) Heuristic:

The findBestBlank() function implements the MRV heuristic, which is a crucial optimization for constraint satisfaction problems:

• Purpose: Always selects the cell with the fewest possible valid values
• Benefit: Reduces the branching factor of the search tree
• Early Termination: If a cell has only 1 valid option, it's immediately selected
• Current Implementation: Uses boolean arrays to count valid options
• Optimized Implementation: Uses bit operations to count valid options faster

Bit Representation:

Optimized findBestBlank() Function (MRV + Bit Masking):

findBestBlank() {
    let minOptions = 10;
    let bestRow = -1;
    let bestCol = -1;

    for (let i = 0; i < this.boardSize; i++) {
        for (let j = 0; j < this.boardSize; j++) {
            if (!this.isBlank(i, j)) continue;

            // COMBINE ALL CONSTRAINTS USING BITWISE OR
            const square = this.getSquareNumber(i, j);
            const usedMask = this.rowMasks[i] | this.colMasks[j] | this.squareMasks[square];
            
            // COUNT UNUSED NUMBERS (UNSET BITS) - MRV HEURISTIC
            let options = 0;
            for (let val = 1; val <= 9; val++) {
                const valMask = 1 << (val - 1); // Convert number to bit mask
                if (!(usedMask & valMask)) {    // If bit is NOT set, number is valid
                    options++;
                }
            }

            // MRV: Choose cell with minimum remaining values
            if (options < minOptions) {
                minOptions = options;
                bestRow = i;
                bestCol = j;
                if (minOptions === 1) return [bestRow, bestCol]; // Early termination
            }
        }
    }

    return [bestRow, bestCol];
}

Key Bit Operations:

• Combining constraints: usedMask = rowMask | colMask | squareMask (bitwise OR)
• Checking validity: !(usedMask & valMask) (bitwise AND with NOT)
• Setting values: mask |= valMask (bitwise OR assignment)
• Clearing values: mask &= ~valMask (bitwise AND with NOT mask)

Performance Benefits:

Real Example:

If row 0 has numbers [1,3,5], column 0 has numbers [2,4], and square 0 has numbers [7,9]: