ROUGH DRAFT authorea.com/104070

# Question 3

On arc-consistency:

$$X_{i}$$ is arc-consistent with respect to another variable $$X_{j}$$ if for every value in the current domain $$D_{i}$$ there is some value in the domain $$D_{j}$$ that satisfies the binary constraint on the arc ($$X_{i}, X_{j}$$)

On constraint graph:

The nodes of the graph correspond to variables of the problem, and a link connects any two variables that participate in a constraint.

## Constraint Graph

Assuming that we have no other arcs to process, the following is the constraint graph constructed:

[A]— $$[A = B + 1]$$ —[B]— $$[B = 2C]$$ —[C]

## Tracing

### $$(A, B)$$

Since $$A = B + 1$$ is the constraint, Domain $$D_A$$ will be reduced to {1, 2, 3, 4} to be make arc $$(A, B)$$ arc-consistent.

State:

$$D_A = \{1, 2, 3, 4\}$$

$$D_B = \{0, 1, 2, 3, 4\}$$

$$D_C = \{0, 1, 2, 3, 4\}$$

### $$(B, A)$$

Since $$B = A - 1$$ is the constraint, Domain $$D_B$$ will be reduced to {0, 1, 2, 3} to be make arc $$(B, A)$$ arc-consistent.

State:

$$D_A = \{1, 2, 3, 4\}$$

$$D_B = \{0, 1, 2, 3\}$$

$$D_C = \{0, 1, 2, 3, 4\}$$

### $$(B, C)$$

Since $$B = 2C$$ is the constraint, Domain $$D_B$$ will be reduced to {0, 2} to be make arc $$(B, C)$$ arc-consistent. This change causes arc $$(A, B)$$ to be re-inserted to the arc queue.

State:

$$D_A = \{1, 2, 3, 4\}$$

$$D_B = \{0, 2\}$$

$$D_C = \{0, 1, 2, 3, 4\}$$

### $$(C, B)$$

Since $$C = \frac{B}{2}$$ is the constraint, Domain $$D_C$$ will be reduced to {0, 1} to be make arc $$(C, B)$$ arc-consistent.

State:

$$D_A = \{1, 3\}$$

$$D_B = \{0, 2\}$$

$$D_C = \{0, 1\}$$

### $$(A, B) : revise$$

Since Domain $$D_B$$ has been changed, based on the constraint graph, Domain $$D_A$$ will be reduced to {1, 3} to be make arc $$(A, B)$$ arc-consistent again.

State:

$$D_A = \{1, 3\}$$

$$D_B = \{0, 2\}$$

$$D_C = \{0, 1\}$$