A constraint-satisfaction problem, or CSP, contains variables, a domain of values for each variable and constraints ruling out joint assignments. Scheduling, frequency allocation and hardware configuration can all take this form. A complete solution assigns every variable without violating a constraint; proving that no such assignment exists is also a valid solving outcome.

Backtracking constructs an assignment depth first. It chooses a variable, tries a value, propagates the consequences and retreats when a domain empties. Variable order therefore determines which contradictions appear early and which remain hidden beneath a large subtree. A helpful choice can save millions of constraint revisions.

No single heuristic has to be best on every structure. Minimum domain favours immediate scarcity; maximum degree favours connectedness; conflict-based scores seek danger. These intuitions overlap but are not equivalent. The same rule can be incisive in one region and wasteful in another.

The algorithm-selection tradition treats that variation as learnable. Store how several methods behaved on past instances, describe a new instance with features, then choose the historically suitable method. Sophisticated portfolios often make this relation hard to inspect. Moreno-Scott and colleagues pursue an unusually transparent alternative: a two-dimensional map whose cells are labelled by the average winner.

The study has two linked aims. First, systematically explore where six dynamic variable-ordering heuristics excel or fail. Second, convert the observed regions into selectors for unseen random and structured problems. The point is not merely higher performance; it is an interpretable account of why a rule is being applied.

At a node, the solver selects one unassigned variable, tries values in their default domain order and checks consistency. Constraint propagation removes unsupported values. If a domain becomes empty, backjumping retreats to a relevant earlier decision rather than mechanically stepping back one level.

Removing values changes domain sizes. Assigning a variable changes which constraints remain active and therefore degrees. The fraction of currently forbidden value pairs can change as domains contract. A variable that looked safe at the root may become urgent after one assignment.

Every heuristic assigns a score to each remaining variable, sorts according to its own preference and selects first. All ties in the experiment are broken lexically by variable name. Values are always tried in their original order. Those controls isolate variable ordering from value-order effects.

The performance metric is consistency checks. Each time a constraint is revised, a counter increases. This is a machine-independent proxy for search work and makes comparisons less sensitive to implementation noise, though it is not wall-clock time and does not include every cost of score computation equally.

An algorithm selector sits outside this loop. A static selector chooses one of the six scoring rules from initial features and keeps it. A dynamic selector recomputes the instance position before every variable assignment and may replace the scoring rule. The selected heuristic remains dynamic internally either way.

DOM chooses the smallest current domain d_v. It follows fail-first reasoning: try the variable with least room to manoeuvre. DEG chooses maximum current degree deg_v, the number of constraints involving v, seeking the variable that can affect most neighbours.

DOMDEG minimises d_v/deg_v. Small domains lower the ratio; large degree lowers it too. The combination tries to balance present scarcity against future reach, although the quotient fixes one particular way of trading them.

For every constraint c involving v, let p_c be its current fraction of forbidden value pairs. RHO minimises ρ_v=∏(1−p_c). This approximates local solution density under an independence-like multiplication: many tight constraints drive the product towards zero.

SOL minimises sol_v=d_vρ_v. It extends RHO by also accounting for how many values v retains. The authors later connect this richer combination to SOL’s strong performance near the hardest transition.

MXC maximises cf_v=∑p_c. It seeks variables exposed to the greatest aggregate conflict fraction. Unlike RHO’s multiplicative survival view, MXC adds local tightness. Two variables can therefore swap order depending on whether several moderate constraints or one severe constraint matters more.

Variable v₀ has domain size two and degree one. v₃ also has two values but degree two. DOM sees a tie and lexical ordering selects v₀. DOMDEG gives v₃ ratio one and also gives v₅ ratio one; lexical order selects v₃.

DEG chooses v₅, the sole variable with degree three. MXC assigns v₄ and v₅ conflict sums of nine in the table’s scale, then lexical order makes v₄ first.

RHO gives its minimum, .1111, to v₃. SOL multiplies that density by domain size two, producing .2222, also its minimum. Thus DOMDEG, RHO and SOL converge on v₃ for different reasons.

The values matter less than the discipline they reveal. A reported “heuristic winner” depends on exact scoring direction and tie-breaking. Reimplementations that use random ties or a different variable naming order are testing a different policy, especially where broad score ties occur.

Value order is held constant too. If a variable ordering reaches the same node count but its values are permuted, the first solution may arrive earlier or later. Fixing default value order keeps the study focused on which variable is selected.

For |V| variables there are |V|(|V|−1)/2 possible unordered binary constraints. Constraint density p₁=2|C|/[|V|(|V|−1)] is the fraction present. Zero means no constrained pairs; one means a complete constraint graph.

Each present constraint c explicitly lists forbidden value pairs. Its tightness p_c is the forbidden fraction among all pairs in the two incident domains. Global p₂ averages p_c across C. It describes how restrictive present edges are, not how many edges exist.

A sparse network can have severe individual constraints; a dense network can have lenient ones. Separating the axes lets the map distinguish these cases. The paper’s illustrative six-variable CSP has p₁=.4 and p₂=.4815.

The representation is intentionally narrow. Every experimental problem is binary and constraints are in extension, meaning forbidden pairs are enumerated. Higher-arity CSPs need features that respect multi-variable relations. Density and mean tightness also discard topology: two graphs with equal coordinates can have hubs, chains or communities and behave very differently.

That information loss explains the selector’s probabilistic status. A cell records the best average heuristic among sampled instances, not a guarantee for every graph at the coordinates. The instance-space map makes expected regions visible while leaving unusual cases unresolved.

Model B generates a binary CSP in two stages. First choose which variable pairs receive constraints to meet target density. Then choose forbidden value pairs on those edges to meet target tightness. This division gives precise control over both coordinates.

The survey uses a 50×50 grid with .02 steps on each axis: 2,500 sampling points. At every point, 50 independent instances contain twenty variables and ten values per domain. The training landscape therefore contains 125,000 instances.

Every instance is solved six times, once per ordering heuristic, by the same Java solver with constraint propagation and backjumping. Hardware is an AMD 4.0 GHz eight-core Windows machine with 32 GB memory. Solving stops at the first solution or when unsatisfiability is proved.

All six cost surfaces show a satisfiable–unsatisfiable phase transition. Most instances on one side have solutions, most on the other do not, and maximum uncertainty forms a narrow hard strip. The greatest average cost for every heuristic occurs at p₁=1 and p₂=.22.

At that point SOL averages 3.87 million checks, DOM 4.76 million, RHO 4.86 million, DEG and DOMDEG 11.17 million and MXC 16.14 million. Yet within the same cell, individual costs range widely. Coordinates predict an average distribution, not exact difficulty.

SOL dominates the phase-transition band. Moving left into mostly satisfiable space reveals strips where RHO and then MXC lead. On the right, where instances are mostly unsatisfiable, DOM and DOMDEG have small specialist regions; much of this side has no unique winner because methods tie.

DEG never becomes the sole average winner at any training cell. That does not make it useless on every individual instance. It says the two-feature regional average always contains another heuristic at least as good.

The anti-map is equally instructive. DOM is worst through much of satisfiable space. MXC performs worst near the phase transition. DOMDEG has a narrow poor strip on the unsatisfiable side. Elsewhere ties again produce “no dominance”.

Cell averages cannot promise an individual result. At the hardest cell, SOL is best on 42 of fifty instances and MXC worst on 46. Yet instance 27 reverses the story: MXC uses.04 million checks while SOL uses.13 million: more than a threefold ratio in MXC’s favour.

The exception is diagnostic. Density and tightness identify broad regimes, but they cannot distinguish every topology or conflict arrangement. More features may locate such outliers. The authors treat this limitation as a route to improvement rather than hiding it behind average accuracy.

For a new instance, compute density and tightness, locate the closest mapped grid point and use the heuristic that achieved lowest average cost there. Each decision can be explained with a coordinate, a distance and a cell label. There is no opaque classifier boundary.

The static heuristic selector, SHS, performs this once at the initial state. The chosen heuristic then controls every variable decision, dynamically recomputing its own score but never being replaced by another member.

The dynamic heuristic selector, DHS, recalculates p₁ and p₂ whenever a variable must be assigned. As propagation shrinks the remaining subproblem, its point may move and a different cell label may fire. Feature computation is cheap here, so selection overhead is not the main concern.

The deeper mismatch is supervision. Every training cell is labelled by the heuristic that solved whole instances from beginning to end. It contains no evidence about transitions between heuristics after partial search. DHS treats a whole-run performance map as if it were a switching policy.

Heuristics can undo one another’s progress by steering search into incompatible subtrees. That interaction increases variance. A genuinely dynamic selector would need training examples describing problem states, prior decisions and safe hand-offs, not only root-instance coordinates.

Two metrics prevent a shallow victory count. The first is the percentage of sampling points where a selector’s average cost beats an individual heuristic. The second is the total percentage of consistency checks saved across all instances. A method may win many easy points yet lose heavily on a few hard ones.

Across test grids, SHS beats SOL at 83.40–84.72 per cent of points, but saves only 1.76–1.89 per cent of checks because SOL is already excellent on the costly ridge. Against DEG, SHS beats about 68.6 per cent of points and saves 64.80–70.34 per cent.

Against DOM it saves 35.90–42.36 per cent; against MXC 59.38–60.39; against RHO 13.56–14.23; and against DOMDEG 51.47–56.87. The selector’s benefit is largest when it avoids disastrous specialist mismatches on hard cells.

DHS beats SOL at roughly 66 per cent of points, an apparently respectable frequency. Yet it increases total checks against SOL by 8.55–9.51 per cent. Its losses are concentrated where being wrong is expensive. This is the study’s cleanest demonstration that win rate and aggregate cost answer different questions.

SHS outperforms DHS on average. The result does not establish that switching can never help. It shows that switching with this map: trained on uninterrupted heuristic runs and only two current features: is not reliably beneficial.

The set combines fifteen QCP-10 and fifteen QCP-15 instances, twenty composed instances, one hundred unsatisfiable ehi cases encoded from 3-SAT and one hundred geometrical cases. Sizes range from fifty variables with twenty values to 297 variables with eight values. Their points concentrate in particular regions rather than filling the plane.

Against SOL, SHS wins on 51.83 per cent and saves 19.22 per cent of checks. Against DEG it wins 76.73 per cent and saves 71.62 per cent. Against MXC it wins 91.84 per cent and saves 74.82 per cent.

An oracle comparison asks how often a method ties the minimum cost among all six heuristics. SHS reaches that minimum on more than 40 per cent of structured instances; SOL, the closest individual, on 23 per cent. Ties mean the displayed method percentages can sum above one hundred.

SHS is also compared with Activity-Based Search and Weighted Degree, neither in its portfolio. Its median is lower than ABS and similar to WDEG, with greater WDEG variance. Mean check reductions are 44.18 per cent versus ABS and 66.86 per cent versus WDEG.

Yet a one-sided paired t-test at five per cent does not provide enough evidence to claim SHS is better than ABS or WDEG. Mean savings coexist with uncertainty and distributional sensitivity. The authors explicitly avoid calling their simple grid the best selection model.

Scope remains binary extensional CSPs, two coarse features, one solver and consistency checks rather than time. Training and random tests share Model B. Structured transfer is encouraging but concentrated and modest in size. The work demonstrates useful, interpretable matching: not universal dominance.

Six prototype cells encode synthetic whole-run winners. Every trace point selects the prototype with minimum Euclidean distance. Coordinates, distances and labels are visible; there is no learned boundary hidden from inspection.

Under SHS, only the first point matters. The label is held across all later decision states, matching the paper’s static commitment. Under DHS, every point is reclassified and the displayed rule may switch.

The synthetic cost illustrates interaction rather than reproducing consistency-check tables. A base cost belongs to each trace and switching adds a penalty. This embodies the paper’s warning that individually sensible heuristics can cancel one another’s progress.

Ridge approach begins near SOL and remains near the hard frontier. Easy satisfiable stays close to MXC and RHO prototypes. Cross-region drift moves from MXC through RHO to SOL and DOM, creating multiple DHS switches.

The exact tests verify the mechanism: every fired rule is the true nearest prototype; its heuristic equals the stored cell winner; SHS makes one decision while DHS recomputes once per trace state. The page does not pretend that the synthetic labels are the paper’s unpublished cell table.

Recreate Model B’s 50×50 grid, .02 spacing, fifty training instances per cell, twenty variables and domain size ten. Use identical generated instances for all six heuristics, fixed lexical ties, fixed value order, the same propagation and backjumping, and exact consistency-check instrumentation.

Publish random seeds, per-instance check counts, satisfiability, selected variable traces and cell labels. Report cell means with quantiles and tails. Preserve all three independent test grids rather than merging them before assessing stability.

For transfer, stratify structured families and show instance coordinates. Add wall time, score-computation cost and memory beside checks. Use bootstrap intervals or distribution-appropriate paired tests, correcting for multiple comparisons where necessary.

Expand features cautiously: degree variance, clustering, domain-size dispersion, constraint-tightness variance and graph components could distinguish star from cycle or locate instance 27. Compare nearest-cell rules with trees, calibrated classifiers and portfolio methods while retaining human-readable explanations.

Train a truly dynamic selector on partial states and transitions. A label should estimate the counterfactual cost of switching after a history, not replay root-level winners. Include a no-switch option and model switching cost. This directly tests the paper’s most important negative result.

Review one: scholarly fidelity and teaching. The reconstruction was checked against the complete PMC journal text. It retains binary extensional CSP scope; all six scoring directions and formulas; lexical ties and default value order; p₁ and p₂ definitions; Model B; grid dimensions; solver controls; phase-transition result; best and worst regions; static and dynamic selector mechanics; and random and structured tests.

The central teaching risk was calling SHS static without explaining that its chosen ordering remains dynamic. That distinction is explicit. A second risk was presenting density and tightness as sufficient instance identity. The page repeatedly frames them as a legible projection that predicts cell averages while hiding topology and outliers.

Review two: evidence, language and accessibility. Counts distinguish 125,000 training instances from 75,000 independent random tests and 250 structured cases. Point-win percentages are separated from aggregate check savings. The negative DHS–SOL savings and statistically insufficient ABS/WDEG superiority claim are preserved.

Consistency checks are never equated with time. The qualitative territory diagram is labelled as reconstruction, and the laboratory’s prototype map as synthetic. All figures have titles, descriptions and captions; animation honours reduced-motion settings; controls are labelled; and the demonstration exposes its three exact tests.

Soutchanski and Young separate the authority of the Basic Action Theory from relaxed guidance. Moreno-Scott and colleagues separate CSP semantics from variable-order policy. Both show that a search rule can change effort drastically without changing what counts as a solution.

The new level is meta-decision. A heuristic scores variables; a selector scores heuristics using instance features and historical costs. Its failure mode is correspondingly subtle: DHS can choose a locally suitable heuristic from an empirically valid map and still worsen the whole search because the map never modelled switching.

Canon 0090 returns to planning with Gerevini, Saetti and Serina’s LPG: stochastic local search over temporal action graphs. The sequence joins three scales of guidance: ranking proof histories, assigning variable-order specialists and repairing an entire plan representation through local changes.

The grid’s labels answer a specific counterfactual: if one heuristic controls a whole run for instances near these coordinates, which has lowest average checks? SHS asks that exact question at deployment. Its simplicity is a form of alignment between evidence and action.

DHS asks a different question: after a partial history produced under perhaps several heuristics, which rule should control the next assignment? Root-level cell winners are not answers to that query. More frequent reconsideration cannot repair missing causal evidence and can amplify incompatible commitments.

Interpretability makes the mismatch visible. Because the rule is a coordinate and label rather than an opaque score, researchers can see what was measured, what is extrapolated and why outliers matter. The lasting contribution is therefore both computational and epistemic: map competence, but preserve the unit of decision the map actually supports.