No column constraint needed — our variables already encode “one queen per column”.
Q: which constraints do we need?
Q. Given the variables \(x_0, \ldots, x_3\) and their domains, which row/column/diagonal constraints must we enforce?
No two queens in the same row
No two queens in the same column
No two queens on the same diagonal
Two of (A), (B), (C)
All of (A), (B), (C)
D — row + diagonal only. The column constraint is already implied by our choice of variables: there's exactly one \(x_i\) per column, so no two queens can ever share a column.
Two ways to express a constraint
Constraint: queens in columns 0 and 2 are not in the same row or diagonal.
As a formula
\((x_0 \ne x_2) \;\land\; (|x_0 - x_2| \ne 2)\)
As a table
\(x_0\)
\(x_2\)
0
1
0
3
1
0
1
2
2
1
2
3
3
0
3
2
Implementations usually pick the formula form — faster to check, no table to store.
Q: encode \((x_0, x_2)\) as a formula
Q. Which formula encodes "queens in columns 0 and 2 are not in the same row or diagonal"?
\((x_0 \ne x_2)\)
\((x_0 \ne x_2) \;\land\; ((x_0 - x_2) \ne 1)\)
\((x_0 \ne x_2) \;\land\; ((x_0 - x_2) \ne 2)\)
\((x_0 \ne x_2) \;\land\; (|x_0 - x_2| \ne 1)\)
\((x_0 \ne x_2) \;\land\; (|x_0 - x_2| \ne 2)\)
E. The two columns are 2 apart, so diagonal conflict means \(|x_0 - x_2| = 2\). We need both the row and diagonal exclusions, and the absolute value because the queens could be above or below each other.
4-queens as an incremental search problem
State: one queen per column in the leftmost \(k\) columns, no pair attacking each other.
Initial state: empty board _ _ _ _.
Goal state: 4 queens placed, no pair attacking. e.g. 1 3 0 2.
Successor: place a queen in the leftmost empty column that no current queen attacks.
e.g. 0 _ _ _ → 0 2 _ _, 0 3 _ _.
Any search algorithm works on this state space. Backtracking = DFS + one rule: skip any partial assignment that already violates a constraint.
Backtracking search
Backtracking = DFS through partial assignments +
prune any partial that already violates a constraint.
backtrack(assignment, csp)
If assignment is complete → return it.
Pick an unassigned variable var.
For each value in domain(var) that satisfies every constraint:
Add {var = value} and go deeper; if a solution is found, return it.
Otherwise undo and try the next value.
If no value worked → returnfailure.
Trace: backtracking on 4-queens
Each node = partial assignment. Yellow = dead end. Green = solution.
Found in 9 expansions — vs 1024 generate-and-test calls.
Partial assignment, fatal future
After placing \(x_0 = 0\), is \(x_1 = 2\) safe?
\(x_0\)\(x_1\)\(x_2\)\(x_3\)
0123
Q
x
x
x
x
x
x
x
Q
x
x
x
x
x
x
Every cell of column \(x_3\) is attacked → no future for the remaining queens.
Knowing this before trying \(x_2\) = arc consistency.
Binary constraints only
Arc consistency is defined on binary constraints \(c(X, Y)\).
Unary constraints \(c(X)\): drop disallowed values directly from \(D_X\).
The CSPs in this course (4-queens, the homework problems) are all binary.
Notation: arcs
An arc \(\langle X, c(X,Y) \rangle\) pairs a constraint with one of its variables.
\(X\) is the primary variable (the one we'll prune); \(Y\) is the secondary.
Each binary constraint defines two arcs — one per primary choice.
Arc-consistency definition
Arc consistency. The arc \(\langle X, c(X,Y) \rangle\) is arc-consistent iff for every \(v \in D_X\) there exists a \(w \in D_Y\) such that \((v, w)\) satisfies \(c(X, Y)\).
Intuition: every value in the primary domain has a partner in the secondary domain.
If some \(v \in D_X\) has no partner, remove \(v\) from \(D_X\) to make the arc consistent.
Q: is this arc consistent?
Q. Constraint \(X < Y\), with \(D_X = D_Y = \{1, 2\}\). Is \(\langle X, X < Y \rangle\) arc-consistent?
Yes
No
B — No. For \(v = 2 \in D_X\), there is no \(w \in D_Y\) with \(2 < w\). We can remove \(2\) from \(D_X\) to make the arc consistent.
The AC-3 algorithm
Process arcs one at a time. After each shrink, re-queue neighbours whose consistency may have broken.
AC-3(arcs)
S ← set of all arcs. initialise the queue
While S is not empty:
Pop an arc <X, c(X, Y)> from S.
For each v ∈ DX with no w ∈ DY satisfying c(X, Y) → remove v from DX.
If DX is now empty → returnfalse. infeasible — no value works
If DX shrank → for every neighbour Z ≠ Y, add <Z, c'(Z, X)> back into S. re-queue — its consistency may have broken
Returntrue. every arc is consistent
Why re-queue arcs?
Shrinking one domain can break a previously-consistent neighbouring arc.
Initially: arc \(\langle X, X{<}Z \rangle\) is consistent (1<2, 1<3, 2<3 all work).
Now: \(\langle Z, X{<}Z \rangle\) is broken — for \(w = 2 \in D_Z\), no \(v < 2\) remains in \(D_X\). Must re-queue.
Trace: AC-3 on 4-queens with \(x_0 = 0\)
Initial domains: \(D_{x_0} = \{0\}\), others \(= \{0, 1, 2, 3\}\).Step 1. Process \(\langle x_1, c_{01} \rangle\): drop 0, 1 from \(D_{x_1}\). \(D_{x_1} = \{2, 3\}\).Step 2. Process \(\langle x_2, c_{02} \rangle\): drop 0, 2. \(D_{x_2} = \{1, 3\}\).Step 3. Process \(\langle x_3, c_{03} \rangle\): drop 0, 3. \(D_{x_3} = \{1, 2\}\).Step 4. Process \(\langle x_2, c_{23} \rangle\): no \(w \in D_{x_3}\) works for \(v = 1\). \(D_{x_2} = \{3\}\).Step 5. Re-process \(\langle x_3, c_{23} \rangle\): now drops 2. \(D_{x_3} = \{1\}\).Step 6. Re-process \(\langle x_1, c_{13} \rangle\): drops 3. \(D_{x_1} = \{2\}\).Step 7. Re-process \(\langle x_1, c_{12} \rangle\): drops 2. \(D_{x_1} = \emptyset\). Return false — no solution with \(x_0 = 0\).
Three outcomes of AC-3
A domain becomes empty → no solution.
Every domain has exactly one value → solution found, no search needed.
Some domains have multiple values → need backtracking search on what remains.
AC-3 — properties
Terminates?
Yeseach arc enqueued at most \(d\) times
Order of arcs?
Doesn't matter same final domains
Time complexity
\(O(c\,d^3)\) \(c\) constraints × \(d\) re-queues per arc × \(O(d^2)\) per check
Combining backtracking with AC-3
Run backtracking search.
After each value assignment, run AC-3.
If a domain becomes empty → fail this branch, backtrack.
If every domain has exactly one value → solution found.
Otherwise → continue backtracking on the remaining unassigned variables.
Trace: backtracking + AC-3 on 4-queens
BT starts at the root with 4 candidate values for \(x_0\).Try \(x_0 = 0\). Run AC-3 on the propagated domains.AC-3 empties \(D_{x_1}\) (slide 24) → this branch is dead. Backtrack.Try \(x_0 = 1\). Run AC-3.AC-3 reduces every domain to a single value: \(x_1 = 3, x_2 = 0, x_3 = 2\).Solution found without any further search!
Empty board.
Q
Try \(x_0 = 0\).
Q
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
AC-3: every \(x_1\) row blocked. Fail.
x
Q
x
x
x
x
x
Try \(x_0 = 1\).
x
x
Q
x
Q
x
x
x
x
x
x
Q
x
Q
x
x
AC-3: every domain size 1.
x
x
Q
x
Q
x
x
x
x
x
x
Q
x
Q
x
x
Solved: 1 3 0 2.
Why combine BT with AC-3?
AC-3 prunes branches BT would otherwise explore — it kills bad partial assignments before they grow.
BT decides what AC-3 can't — when AC-3 leaves multi-value domains, BT picks a value and triggers another AC-3 pass.
On 4-queens with \(x_0 = 1\), AC-3 alone reduced everything to a single solution — zero further search.
Three techniques for CSPs
Technique
How
Finds a solution?
Best at
Backtracking
DFS through assignments, prune on constraint violation