TheAlgorithms/Java · error · Error

No satisfying assignment exists for the given expression.

Error message

No satisfying assignment exists for the given expression.

What it means

Thrown by `TwoSat.getSolutions` when the formula is unsatisfiable (`hasSolution == false`). After `solve()` runs, if any variable and its negation share an SCC the formula has no satisfying assignment, so returning one is impossible. This is an `Error` reflecting that the problem instance, not the call, is contradictory.

Source

Thrown at src/main/java/com/thealgorithms/datastructures/graphs/TwoSat.java:217

        if (!isSolved) {
            throw new Error("Please call solve() before checking for a solution.");
        }
        return hasSolution;
    }

    /**
     * Returns one valid assignment of variables that satisfies the boolean formula.
     *
     * @return a boolean array where {@code result[i]} represents the truth value of
     *         variable {@code xᵢ}
     * @throws Error if called before {@link #solve()} or if no solution exists
     */
    boolean[] getSolutions() {
        if (!isSolved) {
            throw new Error("Please call solve() before fetching the solution.");
        }
        if (!hasSolution) {
            throw new Error("No satisfying assignment exists for the given expression.");
        }
        return variableAssignments.clone();
    }

    /** Performs DFS to compute topological order. */
    private void dfsForTopologicalOrder(int u, boolean[] visited, Stack<Integer> topologicalOrder) {
        visited[u] = true;
        for (int v : graph[u]) {
            if (!visited[v]) {
                dfsForTopologicalOrder(v, visited, topologicalOrder);
            }
        }
        topologicalOrder.push(u);
    }

    /** Performs DFS on the transposed graph to identify SCCs. */
    private void dfsForScc(int u, boolean[] visited, int[] component, int sccId) {
        visited[u] = true;

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Check `isSolutionExists()` before calling `getSolutions()`
2. Relax/remove contradictory clauses so the formula becomes satisfiable
3. Catch the Error and report unsatisfiability to the user

Example fix

// before
boolean[] s = ts.getSolutions(); // throws if unsat
// after
ts.solve();
if (ts.isSolutionExists()) {
    boolean[] s = ts.getSolutions();
} else {
    // report unsatisfiable
}

ts.solve();
if (!ts.isSolutionExists()) {
    // no solution; do not call getSolutions()
}

try {
    ts.getSolutions();
} catch (Error e) {
    // formula is unsatisfiable
}

When it happens

Trigger: Calling `getSolutions()` on a solved TwoSat instance whose clauses are contradictory (e.g. clauses forcing `(x1) and (not x1)`).

Common situations: Over-constrained formulas; clauses generated from mutually exclusive requirements; feeding an inherently unsatisfiable problem to the solver.

Related errors

• Graph contains a negative weight cycle
• Graph contains a cycle, topological sort not possible
• Number of variables cannot be negative.
• Variable number must be between 1 and {numberOfVariables}
• Please call solve() before checking for a solution.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/8904dedec3b768e9. Report an issue: GitHub.