# Exercise 4: AC-3 Arc Consistency (25 Marks)
## The Task
We want you to implement the AC-3 inference procedure to enforce global arc
consistency. The implementation needs to be invoked via the function
“`python
def arc_consistency(var: Optional[str], assignment: Assignment, gamma: CSP) -> Optional[Pruned]:
“””Implement the AC-3 inference procedure.
Parameters
———-
var : Optional[str]
The name of the variable which has just been assigned. In the case that
AC-3 is used for preprocessing, `var` will be `None`.
assignment : Dict[str, str]
A Python dictionary of the current assignment. The dictionary maps
variable names to values. The function cannot change anything in
`assignment`.
gamma : CSP
An instance of the class CSP, representing the constraint network
to which we are looking for a solution. The function cannot change
anything in `gamma`.
Returns
——-
pruned_list : Optional[Pruned]
In the case that the algorithm detects a conflict, the assignment and
CSP should remain unchanged and the function should return None.
Otherwise, the algorithm should return a pruned_list, which is a list
of (variable, value) pairs that will be pruned out of the domains of
the variables in the problem. Think of this as the “edits” that are
required to be done on the variable domains.
“””
“`
This function will be called every time a variable `x` is assigned a value (you
can retrieve this value by accessing `assignment[x]`) or as a
**pre-processing** step.
## Grading Guide
Your implementation should expand a similar number of nodes and take the same
amount of time (within an order of magnitude) to the benchmark below:
| Instance | Time (s) | Nodes Expanded | Preprocessed values |
| —————- | ——– | ————– | ——————- |
| sudoku_01.csp | 0.004 | 81 | 273 |
| sudoku_02.csp | 0.006 | 86 | 317 |
| sudoku_03.csp | 0.005 | 81 | 348 |
| sudoku_04.csp | 0.004 | 81 | 440 |
| sudoku_05.csp | 0.005 | 81 | 380 |
| sudoku_06.csp | 0.007 | 81 | 356 |
| sudoku_07.csp | 0.02 | 90 | 289 |
| sudoku_08.csp | 0.14 | 572 | 294 |
| sudoku_09.csp | 0.05 | 211 | 299 |
| sudoku_10.csp | 0.01 | 82 | 319 |
| 3_color_50_l.csp | 0.0008 | 50 | 0 |
| 8_queens.csp | 0.0008 | 11 | 0 |
The above benchmarks were tested on a 2.3 GHz Intel Core i9.
For example, to get the results for solving the first Sudoku problem:
“`sh
python3 solver.py -v lex -l lex -i arc -p arc test_problems/sudoku_01.csp
“`
## What To Submit
The file `inference.py` with the your implementation in the function
`arc_consistency`.
## Implementation Notes And Hints
1. To implement Arc Consistency, you will have to keep track of the domains
that are being changed by the inference procedure yourself. Remember that
the `gamma` object **needs to remain unchanged**.
2. The caller expects your code to comply with the following
**post-condition**: `arc_consistency` never reduces any variable domain to
an **empty set**.
3. In the case that AC-3 is used for preprocessing, `var` will be
`None`. You will have to kickstart the process of enforcing arc consistency.
4. We suggest that you use a
[`collections.deque`](https://www.geeksforgeeks.org/deque-in-python/) object
for your queue as it allows for **constant time** addition and removal of
elements from both ends.
5. Note that you can read but are not allowed to change any attribute inside
the CSP instance `gamma`. Thus you might need to copy some information from
`gamma`. But only copy what you need. Unnecessary copying will significantly
slow down your program.
## Index
1. [Getting Started](1_getting_started.md)
2. [CSP File Format](2_csp_syntax.md)
3. [Exercise 1: Variable Selection Heuristics (10 Marks)](3_variable_selection_heuristics.md)
4. [Exercise 2: Value Selection Heuristics (5 Marks)](4_value_selection_heuristics.md)
5. [Exercise 3: Forward Checking (10 Marks)](5_forward_checking.md)
6. **Exercise 4: AC-3 (25 Marks)**
7. [Exercise 5: Compiling n-ary Constraints into Binary Constraints (20 Marks)](7_compilation.md)
8. [Exercise 6: Wumpus Where Are You? (30 Marks)](8_wumpus_world.md)
9. [Wumpus World Maps Layouts](8a_map_layouts.md)