Not frequent
0/13
Constraint Satisfaction
Syllabus domain eight: formulating CSPs, backtracking heuristics, and arc consistency.
Syllabus domain eight: formulating CSPs, backtracking heuristics, and arc consistency.
11 multiple choice at 2 marks and 1 fill-in-the-blank at 5, marked exactly as Round 1 marks them. Each answer is explained as soon as you check it. The clock is shown, not enforced.
A constraint satisfaction problem is variables, domains, and constraints. Sudoku, map colouring, -queens, timetabling and assignment are all the same object, and recognising the formulation is most of the skill.
Map colouring with three colours: variables are the regions, each domain is , and the constraints say adjacent regions differ. Written that way, the same solver handles exam scheduling and seating plans.
A question that describes a scheduling scenario and asks for the CSP formulation is asking you to identify these three components explicitly.
Plain backtracking assigns one variable at a time and undoes a choice when a constraint fails. Three heuristics transform its performance:
The question that gets asked: why do MRV and LCV pull in opposite directions? Because you want to fail fast on variables - discovering a dead end near the root is cheap - but succeed fast on values, keeping as many future options open as possible.
An arc is consistent when every remaining value of has at least one compatible value in . AC-3 enforces this across the graph, repeatedly removing unsupported values and re-queueing affected arcs.
Two facts that carry marks:
Sudoku is the accessible example: eliminating a candidate from a cell because it appears elsewhere in the row is exactly arc consistency, and human solving techniques beyond that correspond to stronger consistency notions.
A cheaper alternative: after each assignment, remove inconsistent values from the domains of that variable's unassigned neighbours only. Less pruning than full arc consistency, much less cost, and it still catches many failures early.
If the constraint graph is a tree, the CSP is solvable in with no backtracking at all. A question that mentions a tree-structured constraint graph is asking for this observation.
Identify variables, domains and constraints; the formulation is the work. MRV fails fast on variables, LCV succeeds fast on values - opposite by design.
An empty domain proves unsolvability; arc consistency alone proves nothing positive. Tree-structured CSPs need no backtracking.
Minimum remaining values selects…
The smallest current domain. Fail fast, near the root.
Select an answer