AI Search vs. Constraint Solving: Navigating the Boundaries of Complex Puzzles

1. Starting with a Complex Puzzle: The Challenge is Proving, Not Guessing

In cross-border technical exchanges, quantitative research, and intelligent development, we often encounter problems that seem recreational but severely test engineering capabilities. These problems feature rules composed of shapes, numbers, regional boundaries, and continuity conditions, ultimately requiring a global solution that satisfies all conditions.

The essence of such problems is not a natural language Q&A, but a typical Combinatorial Constraint Satisfaction Problem (CSP). It simultaneously includes:

• Discrete variables: Each cell, boundary segment, or region state can only take a finite number of values;
• Geometric constraints: Whether curves are tangent, boundaries are continuous, or local shapes are closed;
• Counting constraints: A region must contain exactly a specified number of smooth segments, intersections, or area units;
• Adjacency constraints: When adjacent regions share a boundary, their choices must be compatible;
• Global constraints: After all local solutions are assembled, no fractures, overlaps, extra closed loops, or undefined regions can occur.

Therefore, the real difficulty lies not in “generating a few plausible candidates,” but in continuously verifying whether each step preserves the possibility of reaching a globally feasible solution.

This is a point often overlooked by developers using AI coding tools: models can help understand rules, produce code drafts, and suggest pruning strategies. However, once the problem size crosses a certain threshold, solving still relies on rigorous data structures, search strategies, and resource management.

---

2. Formalizing Visual Puzzles as Constraint Satisfaction Problems

To solve complex visual puzzles, the first step is to establish a computable formal model rather than immediately enumerating. If the modeling is inaccurate, the faster the search, the further it diverges from the correct answer.

1. Defining Variables and State Space

Assume a board consists of multiple numerical regions, within which several arcs or boundary fragments are allowed to be drawn. The problem can be broken down into three layers of variables:

1. Basic Graphic Variables
   Indicate whether an arc segment exists on a specific cell, vertex, or edge, as well as its direction and connection method.

2. Region Local Solution Variables
   All basic graphic combinations within a region collectively form a candidate shape for that region.

3. Region Selection Variables
   Each region selects one shape from its candidate set, requiring mutual compatibility among all regions.

Formally, this can be written as:

For each region Ri:
    Xi ∈ Candidates(Ri)
Satisfy:
    LocalValid(Xi) = True
    Compatible(Xi, Xj) = True
    GlobalConstraints(X1, X2, ..., Xn) = True

Here, Candidates(Ri) is the set of all locally legal solutions for region Ri. Local legality does not guarantee global legality, but the quality of local candidates determines the upper limit of subsequent searches.

2. Geometric Rules Must Be Transformed into Discrete Judgments

Human intuitive descriptions like “smooth curve,” “two segments connected,” or “continuous boundary” cannot be directly fed to a search program. They must be converted into deterministic boolean checks.

For example, whether a boundary is smooth can be represented by endpoint tangent directions, connection angles, or discrete adjacency templates:

def is_smooth_connection(segment_a, segment_b):
    # Example: represents modeling concept only, not tied to specific puzzle rules
    if segment_a.end != segment_b.start:
        return False
    return segment_a.tangent_at_end == segment_b.tangent_at_start

If the curves in the problem are not continuous geometric curves but simply quarter-circle arcs or fixed-type arc segments within a grid, a more efficient approach is to use a lookup table: pre-list all legal connection combinations, transforming continuous geometric checks into constant-time set queries.

This step is crucial. If geometric calculations are repeatedly executed during the search, it not only introduces floating-point errors but also severely degrades search efficiency.

3. Numerical Rules Must Be Broken Down into Incrementally Maintainable Constraints

Numbers in many puzzles do not correspond to “regional area,” but might represent a structural count within the region, such as:

• Number of smooth connected segments;
• Number of closed curves;
• Number of intersections with the region’s boundary;
• Number of arcs in a specific direction;
• Occurrence count of a specific local pattern.

If the entire region is rescanned after every assignment, the complexity quickly spirals out of control. A more reasonable approach is to maintain an incremental state for each region:

RegionState:
    assigned_edges      # confirmed boundaries
    open_endpoints      # unclosed endpoints
    smooth_count        # currently confirmed smooth segments
    possible_min        # minimum achievable value in unassigned parts
    possible_max        # maximum achievable value in unassigned parts

When a candidate is selected or eliminated, only the affected regions are updated. If the target number is found to be outside the [possible_min, possible_max] range, pruning can occur immediately.

---

3. Why Local Enumeration Explodes

When implementing such solvers for the first time, many people adopt an intuitive strategy: enumerate all legal geometric shapes for each region, and then splice them together via backtracking. This approach isn’t wrong in itself, but one must face the growth rate of local candidate quantities.

Suppose a region involves k selectable boundary positions, each with an average of d states. The naive search space is approximately:

O(d^k)

Even if d is small, as long as the region’s shape is complex, its boundary is long, or internal rules are numerous, the number of candidates can quickly reach the thousands or tens of thousands. More dangerously, the candidate count of a single region does not equal the overall difficulty.

If there are multiple regions, each with candidate sets:

|C1|, |C2|, ..., |Cn|

In the worst case, the joint combination size approaches:

|C1| × |C2| × ... × |Cn|

This is combinatorial explosion. Locally, things seem controllable, but after splicing, they may exceed the memory and time budget of an ordinary machine.

Therefore, when seeing that “a certain central region already has thousands of local solutions,” the real cause for alarm is not those thousands of solutions themselves, but the state flooding caused by the Cartesian product combinations with neighboring region candidates.

---

4. Constraint Propagation Trumps Blind Backtracking

In complex constraint problems, excellent solvers do not try all combinations first. Instead, they ensure that determining one variable triggers a massive contraction in surrounding variables. This process is called constraint propagation.

1. Basic Propagation: Shared Boundary Consistency

If two adjacent regions share an edge, the choice for that edge must be consistent. Compatibility relations can be established in advance:

CompatibleCandidates[RegionA_Candidate] = {All compatible candidates in Region B}

When Region A is reduced to only one candidate, all incompatible candidates in Region B can be deleted. Conversely, Region B’s contraction will continue to affect other neighbors.

2. Using Candidate Domains Instead of Immediate Assignment

Maintain a candidate domain for each region:

Domain(Ri) = {ci1, ci2, ci3, ...}

Initially, the domain might be large. As constraint propagation proceeds, the domain gradually shrinks:

Domain(Ri): 1200 → 87 → 6 → 1

When a region’s candidate domain is empty, it indicates a contradiction in the current path and backtracking is required. When the domain has only one element left, the region is forced to be determined.

The advantage of this strategy is that erroneous branches can often be detected at very shallow levels, without having to fill the entire board before discovering a conflict.

3. Selecting the Most Constrained Variable

When backtracking, do not select the next variable in region number order. A more effective heuristic is to prioritize the region with the fewest candidates, known as the “Minimum Remaining Values” (MRV) principle:

next_region = min(
    unassigned_regions,
    key=lambda region: len(domain[region])
)

The reason is simple: regions with fewer candidates expose contradictions earlier, avoiding massive wasted computation on broad branches.

This can also be combined with a “degree heuristic”: when two regions have the same number of candidates, prioritize the one adjacent to more undetermined regions, as its assignment propagates more constraints.

---

5. Memory Exhaustion is Not Accidental: State Management Determines Success

In actual engineering, search programs often fail not because the algorithm “cannot do it at all,” but because the state representation is too expensive.

Suppose each search node copies the complete board, all region candidate sets, and numerous geometric objects. Even if a single state only takes up a few dozen kilobytes, accumulating to hundreds of thousands or millions of states will quickly exhaust memory.

1. Avoid Saving Complete Historical States

A common inefficient practice is:

new_state = deepcopy(old_state)
apply_choice(new_state, candidate)
search(new_state)

While deepcopy is easy to implement, it creates a lot of duplicate data. A more suitable approach for large-scale backtracking is the “modification log + undo” pattern:

trail = []
def assign(region, candidate):
    trail.append(record_old_domain(region))
    domain[region] = {candidate}
def rollback(mark):
    while len(trail) > mark:
        undo(trail.pop())

Record the log position before each recursion, and roll back to that position upon failure. This only saves the delta, rather than copying the entire state.

2. Use Compact Encoding

If local geometric states are represented using objects, strings, or nested lists, the memory overhead will be huge. More efficient methods include:

• Using bitmaps to indicate edge existence;
• Encoding local patterns with integers;
• Using array indices instead of object references;
• Replacing runtime geometric object comparisons with precomputed compatibility tables;
• Using immutable integer tuples as cache keys.

For example, when a region’s boundary has 16 binary positions, it can be directly represented by a single integer:

0011010010110101

This representation naturally serves as a hash key and is convenient for bitwise pruning.

3. Use Global Visited State Sets Carefully

To avoid duplicate searches, developers often maintain a “visited states” set. However, if the state keys are designed too comprehensively, the set itself can become a memory killer.

Two questions should be evaluated:

1. Does state deduplication significantly reduce duplicate branches?
2. Can the state key retain only the necessary information that affects future decisions?

If certain historical information does not affect future feasibility, it should not be included in the state key. Otherwise, you end up with a situation where “theoretically caching is done, but practically the cache swallows all the memory.”

---

6. Why Generative Models Fail in Such Tasks

AI coding tools still hold value in these problems, but their role boundaries must be clear.

1. What Models Excel At

Generative models are typically good at assisting with:

• Extracting variables and constraints from natural language rules;
• Providing data structure design suggestions;
• Drafting local enumeration and validation functions;
• Proposing search heuristics and pruning strategies;
• Analyzing program logs and locating obvious logical errors;
• Explaining complex processes into actionable development plans.

These capabilities can significantly shorten the time from “understanding the problem” to “building a solving prototype.”

2. What Models Struggle With

However, when the problem requires maintaining consistency across hundreds of constraints over time, and precise progression through a massive search tree, generative models face limitations:

• Difficulty in losslessly maintaining states within the context;
• Hard to manually exhaust all combination branches;
• Prone to mistaking local plausibility for global feasibility;
• Less rigorous than programs in verifying hidden conflicts;
• Lack real-time control over time, memory, and search depth.

In other words, models can be excellent “modeling assistants” and “code collaborators,” but they are not inherently equivalent to reliable “combinatorial solvers.”

When a model provides multiple candidate fillings, these can be treated as heuristic starting points, but they cannot replace rigorous verification. If the problem requires a unique solution, a reproducible validation program must ultimately provide the proof.

---

7. A Robust Human-Machine Collaborative Workflow

For high-difficulty logic puzzles, resource scheduling, shift optimization, or rule validation tasks, the following workflow can be adopted.

Phase 1: Rule Decomposition

Break down natural language rules into four categories:

1. Variable definitions;
2. Local legality;
3. Adjacent compatibility;
4. Global targets and prohibitions.

The goal of this phase is not to write a complete program, but to eliminate ambiguity. Any rule that cannot be written as a judgment function indicates that the understanding is not precise enough.

Phase 2: Build an Independent Verifier

Write the verifier before the solver. The verifier should at least be able to check:

• Whether a single region is legal;
• Whether two adjacent regions are compatible;
• Whether the entire board satisfies numerical and connectivity conditions;
• Whether input candidates contain undefined boundaries or duplicate counts.

The verifier is the referee for all subsequent attempts. Without a verifier, it is impossible to distinguish between “looks like an answer” and “is actually an answer.”

Phase 3: Generate Local Candidates and Analyze Distributions

Do not start with a global search immediately. First, output the candidate count, shape classification, and constraint strength for each region, for example:

Region A: 12 candidates
Region B: 47 candidates
Region C: 1680 candidates
Region D: 9 candidates

If a region’s candidates are exceptionally large, prioritize researching whether local pruning can be added, rather than recklessly pushing forward with global combinations.

Phase 4: Propagation, Search, and Resource Observation

During the search process, continuously record:

• Number of visited nodes;
• Current search depth;
• Size of each region’s candidate domain;
• Number of backtracks;
• Memory usage trends;
• Most frequently triggered conflict types.

These metrics help determine whether the bottleneck comes from modeling errors, candidate explosion, insufficient propagation, or runaway state caching.

Phase 5: Result Verification and Failure Post-Mortem

If the answer cannot be found, it does not mean the work was valueless. The following conclusions should be documented:

• Which local rules have been accurately implemented;
• Which regions are the primary source of complexity;
• Which heuristic brought the greatest pruning benefits;
• Where memory bottlenecks occur in which type of state;
• Which constraints should be prioritized or what solving strategy should be changed next round.

A high-quality failure post-mortem often has more engineering value than an unverified “guessed answer.”

---

8. Conclusion: AI Has Boundaries, Engineering Methods Have Paths

The value of complex logic puzzles lies not only in the final answer, but in how they completely expose the boundaries of intelligent systems in reasoning, search, verification, and resource management.

When the problem scale is small, generative models can quickly provide ideas and prototypes; when local candidates expand drastically, reliance must be placed on constraint propagation, compact encoding, incremental rollback, and heuristic search; when global consistency is extremely strong, more specialized solving frameworks and verifiable mathematical models need to be introduced.

For developers, the most important lesson is not “letting the model think a bit longer,” but establishing a correct division of labor: letting intelligent tools handle understanding, expression, and auxiliary design, while letting deterministic programs handle enumeration, verification, and proof. Only by translating natural language reasoning into executable constraints, and translating intuitive judgments into repeatable tests, can reliable results be truly achieved in complex problems.