Overview

The Satisfiability Problem (SAT) is a fundamental decision problem in computer science, asking whether there exists an interpretation that satisfies a given Boolean formula. This implementation details a high-performance SAT solver based on the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, enhanced with modern Conflict-Driven Clause Learning (CDCL) techniques. The solver is designed to parse Conjunctive Normal Form (CNF) files, execute efficient logical inference, and apply heuristic optimizations to solve complex instances, including a practical application in solving Binary Sudoku puzzles.

Core Data Structures

Efficient memory management and fast access are critical for a SAT solver. The implementation utilizes custom data structures optimized for the specific needs of logical inference and backtracking.

1. Dynamic Vector Implementation

A custom dynamic array is implemented to handle variable-sized lists of literals and clauses, offering amortized O(1) push operations.

template <typename T>
class DynamicArray {
private:
    T* elements;
    size_t count;
    size_t capacity;

    void resize() {
        size_t newCap = capacity * 2;
        T* newElements = new T[newCap];
        for (size_t i = 0; i < count; ++i) {
            newElements[i] = elements[i];
        }
        delete[] elements;
            elements = newElements;
        capacity = newCap;
    }

public:
    DynamicArray() : elements(new T[10]), count(0), capacity(10) {}

    void append(const T& item) {
        if (count == capacity) resize();
        elements[count++] = item;
    }

    T& operator[](size_t index) { return elements[index]; }
    size_t size() const { return count; }
    void clear() { count = 0; }
};

2. Literal Representation

A literal represents a Boolean variable or its negation. The structure encodes both the variable index and its sign efficiently.

struct LogicVar {
    int rawValue;

    LogicVar(int v = 0) : rawValue(v) {}

    bool isNegated() const { return rawValue & 1; }
    int getVariable() const { return rawValue >> 1; }
    
    int toIndex() const { return rawValue; }
    LogicVar operator~() const { return LogicVar(rawValue ^ 1); }
    bool operator==(const LogicVar& other) const { return rawValue == other.rawValue; }
};

3. Clause Structure with 2-Literal Watching

The solver employs the 2-literal watching scheme to optimize unit propagation. Each clause maintains two watched literals. If a watched literal is falsified, the clause searches for another non-falsified literal to watch. If none exist, the clause becomes unit or conflicting.

struct Clause {
    double activityScore;
    bool isLearned;
    DynamicArray<LogicVar> literals;

    Clause(bool learned = false) : activityScore(0.0), isLearned(learned) {}

    // Calculates the reason for propagation
    void calcReason(const Solver& ctx, LogicVar p, DynamicArray<LogicVar>& outReason);
    
    // Performs propagation
    bool propagate(Solver& ctx, LogicVar p);
};

Algorithm Design: CDCL and Heuristics

While the basic DPLL algorithm uses recursive backtracking, this implementation adopts an iterative CDCL approach. This allows for non-chronological backtracking (jumping back multiple decision levels) and clause learning.

Main Solver Loop

The core logic iterates through decision, propagation, conflict analysis, and backtracking phases.

enum SolverState { UNKNOWN, SATISFIABLE, UNSATISFIABLE };

SolverState solve() {
    while (true) {
        // 1. Simplify the database based on current assignments
        if (!simplifyDB()) return UNSATISFIABLE;

        // 2. Decision Phase: Select a variable using VSIDS heuristic
        if (!decideNextBranch()) {
            return SATISFIABLE; // All variables assigned
        }

        // 3. Propagation Phase: BCP (Boolean Constraint Propagation)
        while (true) {
            SolverState status = propagate();
            if (status == UNSATISFIABLE) {
                // 4. Conflict Analysis
                int conflictLevel = analyzeConflict();
                if (conflictLevel < 0) return UNSATISFIABLE; // Top level conflict
                backtrack(conflictLevel); // Non-chronological backtrack
            } else if (status == SATISFIABLE) {
                return SATISFIABLE;
            } else {
                break; // Propagation exhausted, continue to next decision
            }
        }
    }
}

Variable State Independent Decaying Sum (VSIDS)

Decision heuristics are crucial for performance. This solver uses VSIDS, where variables involved in recent conflicts have their activity "bumped." Periodically, all activity scores are decayed by multiplying by a constant factor (e.g., 0.95). This prioritizes variables that are currently relevant to the conflict search space.

Conflict-Driven Clause Learning

When a conflict occurs, the solver analyzes the Implication Graph to identify the First Unique Implication Point (UIP). A new clause preventing this conflict is learned and added to the database. This clause effectively prunes large sections of the search space, preventing the solver from revisiting the same logical contradictions.

Application: Binary Sudoku Encoding

The solver is applied to Binary Sudoku (8x8 grid filled with 0s and 1s). The puzzle constraints are encoded into CNF to leverage the SAT solver's capabilities.

Variable Encoding

Each cell in the 8x8 grid is mapped to a unique Boolean variable. A variable being True corresponds to filling the cell with '1', while False corresponds to '0'.

// Maps grid coordinates to a variable index (1-based)
int encodeCell(int row, int col) {
    return row * 8 + col + 1;
}

Constraint Implementation

1. Adjacency Constraint: No more than two identical numbers consecutively in any row or column.
2. Balance Constraint: Each row and each column must contain an equal number of 0s and 1s (four each).
3. Uniqueness Constraint: No two rows can be identical, and no two columns can be identical. This requires auxiliary variables to handle the comparison logic efficiently in CNF.

File Generation

The application generates a DIMACS CNF file representing the puzzle. It includes unit clauses for pre-filled cells and the clauses derived from the three constraints above. The resulting file is passed to the SAT solver core, and the model is translated back into the grid solution.

Performance Analysis

Performance tests were conducted comparing a recursive DPLL implementation against the optimized iterative CDCL solver. The optimization metric is calculated as: Optimization% = (T_basic - T_optimized) / T_basic * 100.

The results demonstrate that the CDCL implementation with non-chronological backtracking and activity-based heuristics significantly outperforms the basic recursive approach, especially as instance size and complexity increase.