Must the initial assignment satisfy some constraints?

No. It must be complete, but a sensible starting point may improve practical performance.

Does every step strictly reduce conflicts?

No. The best available value may tie the current conflict count, producing a sideways move or no change depending on tie-breaking.

Can it handle a changing problem?

It can be applied to repair a current assignment after changes, but the resulting feasibility and disruption must still be evaluated.

AI Glossary / Graphs and symbolic AI / Intermediate

Min-conflicts

Definition

Min-conflicts is a local-search method for constraint satisfaction that repeatedly repairs a complete assignment. It selects a variable involved in a violated constraint and assigns it a value that minimizes its conflicts with the current values of other variables. The process seeks an assignment satisfying all constraints, usually within a specified search budget.

What it means

A complete assignment gives every variable a value, but it may be inconsistent. A timetable can assign every meeting a room and time while still placing two incompatible meetings together. Min-conflicts starts from such a candidate and changes individual assignments to reduce violations.

This differs from constructing a solution one variable at a time through systematic backtracking. Min-conflicts keeps a full candidate throughout its repair process. It can be useful when a nearly valid assignment already exists, but it is not guaranteed to solve every satisfiable problem within a finite budget or to prove that an unsolved problem has no solution.

How it works

Initialize a complete assignment, perhaps randomly or with a greedy procedure. Check whether it satisfies every constraint. If not, select a conflicted variable, commonly at random. Evaluate its possible values while holding the remaining variables fixed, and choose one with the lowest conflict count. Break ties according to a stated policy, often randomly.

Repeat until a solution is found or the allotted steps are exhausted. Plateaus and repeated states can occur, so practical variants may add restarts or other escape mechanisms.

The conflict-count definition must match the constraints. For pairwise inequality constraints, counting equal-valued neighboring variables is straightforward. Weighted constraints, global constraints, and preferences require more care; minimizing a raw count is not automatically the correct business objective.

Three practical examples

Timetable repair: change selected assignments in a complete schedule to remove overlapping resource use.
Graph coloring: reassign a conflicted node's color to minimize same-colored adjacent nodes.
Puzzle solving: move a conflicted queen within its allowed positions while retaining a complete n-queens placement.

Think of it this way

Think of adjusting seats at a dinner where a full seating plan already exists but some neighboring guests should be separated. Each move tries to improve one person's placement without rebuilding the entire plan.

The analogy has limits: a local repair can disturb other relationships, and many equally good moves can lead to different future possibilities. Finding no immediate improvement does not prove that the current arrangement is the best or that no valid seating exists.

Worked example

Color nodes A, B, C, and D with Red, Blue, or Green. Edges are A - B, B - C, A - C, and C - D. Every edge requires different endpoint colors. Start with A=Red, B=Red, C=Red, D=Blue. The violated edges are A - B, B - C, and A - C: three conflicts.

Select conflicted B. Its neighbors A and C are both Red. Giving B Red produces two conflicts, while Blue and Green each produce zero conflicts involving B. Choose Blue as the tie-break result. Only A - C remains violated, so the complete assignment now has one conflict.

Select C next. Its neighbors are A=Red, B=Blue, and D=Blue. Red gives one conflict, Blue gives two, and Green gives zero. Set C=Green. The resulting assignment A=Red, B=Blue, C=Green, D=Blue satisfies all four edge constraints.

This is one directly checked repair sequence, not evidence that every variable selection will solve every coloring problem in two steps. The first choice evaluates conflicts involving B; constraints that do not involve B remain unchanged during that move.

Illustrative case study

Fictional case: a training provider has a complete workshop schedule when one room becomes unavailable. A local-search repair system starts from the existing schedule and moves conflicted sessions to alternative assignments.

The first version removes room clashes but moves many sessions away from their announced times. The team recognizes that preserving existing arrangements is a separate preference and modifies its objective and review process accordingly. It also checks every hard constraint before releasing a revised schedule. The fictional case illustrates how a feasible repair and an acceptable operational repair can differ; no measured scheduling result is claimed.

Common misconceptions and mistakes

Min-conflicts does not mean choosing the variable with the fewest conflicts. In the usual algorithm, a conflicted variable is selected and its value is chosen to minimize conflicts. Variable-selection and value-selection rules are separate design choices.

Do not confuse it with the least-constraining-value heuristic used during backtracking, which considers flexibility left for future assignments. Min-conflicts evaluates a current complete assignment. A search timeout is not a proof of inconsistency, and a low conflict count is not a valid solution when even one hard constraint remains violated.

Business use

The method can be useful for fast candidate repair when the final assignment matters more than the route taken to obtain it. A business system can start from an existing plan and attempt targeted changes instead of discarding all prior work.

Evaluate solve rates, runtime, variability across random seeds, and the impact of changes to existing commitments. Keep hard constraints distinct from preferences and use an independent final feasibility check. If users need a proof that no solution exists or a certified optimum, choose a solving approach capable of providing that evidence rather than relying on local-search failure.

Check your understanding

after the first worked move, B has no conflicts but A - C is still violated. Is the problem solved?

Answer: no. The algorithm must check the whole assignment. A value that is locally conflict-free for one variable does not establish global constraint satisfaction.

Related terms

Constraint satisfaction problem
Local search
Complete assignment
Graph coloring
Hill climbing
conflict count
random restart
backtracking
schedule repair

Learn next

trace the worked coloring example with a different tie choice and verify every final constraint. Then try a two-color triangle, which is unsatisfiable, and observe why repeated repair attempts do not themselves prove that fact. Compare local repair with systematic backtracking and constraint propagation.

Constraint propagation

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Chapter 5, local-search discussion and Figure 5.8: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf. The primary algorithm and conflict definition were read. The four-node coloring trace and training-provider case are original teaching examples; no implementation benchmark is claimed.

Previous: Microparallelism Next: Min-max optimization