How a Solver Thinks

🎓 How a Solver Thinks

How does a solver actually find solutions? After all, it can’t just try every possibility at random — that would be hopelessly slow for real-world problems.

Instead, solvers combine logical deduction and systematic search. They “think” in two powerful ways:

  • Constraint Propagation — shrinking the space of possibilities through logic, before making guesses.
  • Optimization — exploring possibilities strategically, while discarding whole regions of the search tree that cannot lead to better solutions.

Let’s unpack both ideas.

🔍 The Core Idea: Constraint Propagation and Domain Pruning

Imagine you’re solving a Sudoku puzzle. You place a “5” in one cell. Immediately, you know:

  • No other cell in the same row can be “5”.
  • No other cell in the same column can be “5”.
  • No other cell in the same 3×3 block can be “5”.

This is the essence of domain pruning: the moment a choice is made (or implied), the possible values of other variables shrink.

Constraint Propagation Defined

Constraint Propagation is the iterative process of using constraints to eliminate impossible values from variable domains.

  • Whenever a domain shrinks, connected constraints are re-evaluated.
  • This often triggers a chain reaction: one variable prunes another, which prunes another, and so on.

Mini-Example: Inequality CSP

Variables:

  • X ∈ {1, 2, 3}
  • Y ∈ {1, 2, 3} Constraint: X > Y.

Steps:

  1. Initial state: X = {1, 2, 3}, Y = {1, 2, 3}.
  2. Check X = 1: If X = 1, then Y must be less than 1. But Y has no such values. → Prune 1 from X. So now X = {2, 3}.
  3. Check Y = 3: If Y = 3, then X must be greater than 3. No such values exist. → Prune 3 from Y. So now Y = {1, 2}.

Result after propagation:

  • X = {2, 3}, Y = {1, 2}.
  • The search space has already been cut in half without guessing.

Another Example: Map Coloring Propagation

Variables: A, B, C with domains {Red, Green, Blue}. Constraint: A ≠ B, B ≠ C.

  • Suppose we assign B = Green.
  • Propagation removes Green from A’s and C’s domains.
  • Now: A = {Red, Blue}, C = {Red, Blue}.
  • This cascades forward: each step tightens possibilities before explicit branching.

🌳 Optimization, or searching for the Best: Branch and Bound

Propagation prunes domains, but often multiple values remain possible. How do we decide? That’s where search comes in.

The Search Tree

Think of every variable choice as a branching point.

  • Branching: Pick a variable, split into subproblems for each possible value.
  • Tree structure: Each complete assignment is a leaf of the tree.

A brute-force search would explore every leaf. That’s exponential — hopeless for large problems. So solvers use Bounding to avoid exploring hopeless branches.

Bounding Explained

Bounding is about using an optimistic estimate to decide whether a branch is worth exploring.

  • If the best possible outcome in a branch is already worse than the best solution found so far, the solver prunes the branch.
  • This prevents wasted effort on dead ends.

Example: Knapsack Optimization

Problem: choose items to maximize value without exceeding weight.

Steps:

  1. Branching: Solver considers including/excluding each item.
  2. First complete solution: Suppose value = 50. This becomes the incumbent best.
  3. Bounding: In another branch, even if solver assumes “all remaining items are included,” the maximum possible value is only 45. Since 45 < 50, this branch is abandoned.
  4. Better branch: In a new branch, the optimistic bound is 65. That’s better than 50, so solver continues. Eventually it finds a real solution worth 60, improving the incumbent.
  5. Repeat: Until no unexplored branch can beat 60. At this point, 60 is proven optimal.

🧩 Propagation + Branching = Efficiency

  • Propagation removes impossibilities early.
  • Branching explores what remains.
  • Bounding skips wasteful paths.

Together, they transform an intractable “brute-force search” into something practical — though in the worst case, CSPs and optimization problems remain computationally hard.

📖 Glossary

  • Constraint Propagation: Logical inference that prunes variable domains.
  • Domain Pruning: Removing impossible values from a variable’s set.
  • Search Tree: The branching structure formed by exploring variable assignments.
  • Branching: Splitting into subproblems based on variable choices.
  • Bounding: Estimating the best possible result down a branch to decide whether to explore it.
  • Incumbent Solution: The best solution found so far.
  • Optimization Problem: A problem where the goal is to maximize or minimize an objective function subject to constraints.