In constraint satisfaction, the AC-3 algorithm (short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problems (or CSP's). It was developed by Alan Mackworth in 1977. The earlier AC algorithms are often considered too inefficient, and many of the later ones are difficult to implement, and so AC-3 is the one most often taught and used in very simple constraint solvers.

The algorithm 

AC-3 operates on constraints, variables, and the variables' domains (scopes). A variable can take any of several discrete values; the set of values for a particular variable is known as its domain. A constraint is a relation that limits or constrains the values  a variable may have. The constraint may involve the values of other variables.

The current status of the CSP during the algorithm can be viewed as a directed graph, where the nodes are the variables of the problem, with edges or arcs between variables that are related by symmetric constraints, where each arc in the worklist represents a constraint that needs to be checked for consistency. AC-3 proceeds by examining the arcs between pairs of variables (x, y). It removes those values from the domain of x that aren't consistent with the constraints between x and y. The algorithm keeps a collection of arcs that are yet to be checked; when the domain of a variable has any values removed, all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection. Since the domains of the variables are finite and either one arc or at least one value are removed at each step, this algorithm is guaranteed to terminate.

For illustration, here is an example of a    very simple constraint problem:
X (a variable) has the possible values {0, 1, 2, 3, 4, 5}—the set of these values are the domain of X, or D(X). The variable Y has the domain D(Y) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Together with the constraints C1 = "X must be even" and C2 = "X + Y must equal 4" we have a CSP that AC-3 can solve.  Notice that the actual constraint graph representing this problem must contain two edges between X and Y since C2 is undirected but the graph representation being used by AC-3 is directed.

AC-3 solves the problem by first removing the non-even values from of the domain of X as required by C1, leaving D(X) = { 0, 2, 4 }. It then examines the arcs between X and Y implied by C2. Only the pairs (X=0, Y=4), (X=2, Y=2), and (X=4, Y=0) match the constraint C2. AC-3 then terminates, with D(X) = {0, 2, 4} and D(Y) = {0, 2, 4}.

AC-3 is expressed in pseudocode as follows:

  Input:
    A set of variables X
    A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x
    A set of unary constraints R1(x) on variable x that must be satisfied
    A set of binary constraints R2(x, y) on variables x and y that must be satisfied
    
  Output:
    Arc consistent domains for each variable.
  
  function ac3(X, D, R1, R2)
      // Initial domains are made consistent with unary constraints.
      for each x in X
          D(x) := { vx in D(x) | vx satisfies R1(x) }   
      // 'worklist' contains all arcs we wish to prove consistent or not.
      worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
  
      do
          select any arc (x, y) from worklist
          worklist := worklist - (x, y)
          if arc-reduce (x, y) 
              if D(x) is empty
                  return failure
              else
                  worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
      while worklist not empty
  
  function arc-reduce(x, y)
      bool change = false
      for each vx in D(x)
          find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
          if there is no such vy {
              D(x) := D(x) - vx
              change := true
          }
      return change

The algorithm has a worst-case time complexity of O(ed3) and space complexity of O(e), where e is the number of arcs and d is the size of the largest domain.

References 

 A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977.
 Stuart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach, 202-233, 2003.

Constraint programming
Articles with example pseudocode
AC-3 알고리즘()은 제약 만족 문제 (약어로 CSP)를 풀기 위한 일련의 알고리즘 중 하나이다. 1977년 앨런 맥워스가 고안하였다. 이전의 AC 알고리즘은 효율적(efficient)이지 않다고 여겨져 왔다. AC-3 이후의 것들은 구현하기 너무 복잡하다고 간주된다. 따라서 간단한 제약 만족 문제 해법으로서는 AC-3이 가장 많이 사용되는 알고리즘의 하나이다.

알고리즘 
AC-3 알고리즘은, 주어진 제약, 변수, 변수의 정의역(domains) 내에서 동작한다. 변수는 여러 이산(discrete) 값을 가질 수 있다; 어떤 변수가 가질 수 있는 값들의 집합을 가리켜 정의역(혹은 변역)이라 한다. 제약이란 변수가 가질 수 있는 값을 제한하거나 제약하는 관계를 말한다. 제약은 어떤 다른 변수의 값에 관계된 것을 수도 있다.

제약 만족 문제는 유향 그래프로서 표현될 수 있다. 꼭짓점이 변수가 된다. 꼭짓점 사이의 변들은 제약조건을 나타낸다. AC-3 알고리즘은 변수들 (x, y)의 순서쌍 변을 하나하나 보며 진행된다. x와 y 사이의 제약 조건과 불일치(inconsistent)한 x와 y의 값들이 있으면 x와 y의 정의역에서 각각 제거해나간다.

설명을 위해, 간단한 제약 문제 하나를 예로 들겠다:
X (변수)는 값으로서 {0, 1, 2, 3, 4, 5} 중 하나를 가질 수 있다. -- 이러한 값들의 집합이 X의 정의역이 된다. D(X)라고 적는다. 마찬가지로 변수 'Y가 정의역 D(Y) = {0, 1, 2, 3, 4, 5}를 갖는다고 하자. 제약 C1 = "X는 짝수이어야 한다.", C2 = "X + Y는 4이어야 한다."를 추가하면, 이제 AC-3으로 해결할 수 있는 제약 조건 문제(CSP)가 된다. 여기서, 앞서 말한 문제의 그래프 그림에서는, 제약 C2가 무방향성(undirected)이므로 X와 'Y 간의 두 개의 변(edge)이 방향이 없는 변(undirected edge)인 것인 데 반해, 일반적으로 AC-3 알고리즘이 이용하는 그래프 그림은 방향이 있는 변(directed edge)을 쓴다는 것에 유의해야 한다.

우선, X의 정의역에서 제약 C1에 맞추어 짝수가 아닌 수들을 제거한다. D(X) = { 0, 2, 4 }가 된다. 그런 다음 X와 Y 사이의 호(arc)를 제약 C2에 따라 조사한다. 순서쌍 (X=0, Y=4), (X=2, Y=2), (X=4, Y=0)만이 C2에 만족한다. AC-3 알고리즘은 D(X) = {0, 2, 4}, D(Y) = {0, 2, 4}임을 결정하고 이제 종료한다.

AC-3의 슈도-코드는 다음과 같다:

  Input:
    A set of variables X
    A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x
    A set of unary constraints R1(x) on variable x that must be satisfied
    A set of binary constraints R2(x, y) on variables x and y that must be satisfied

  Output:
    Arc consistent domains for each variable.

  function ac3 (X, D, R1, R2)
  // Initial domains are made consistent with unary constraints.
      for each x in X
          D(x) := { x in D(x) | R1(x) }
      // 'worklist' contains all arcs we wish to prove consistent or not.
      worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }

      do
          select any arc (x, y) from worklist
          worklist := worklist - (x, y)
          if arc-reduce (x, y)
              if D(x) is empty
                  return failure
              else
                  worklist := worklist + { (z, x) | z != y }
      while worklist not empty

  function arc-reduce (x, y)
      bool change = false
      for each vx in D(x)
          find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
          if there is no such vy {
              D(x) := D(x) - vx
              change := true
          }
      return change

이 알고리즘은 워스트-케이스 타임 컴플렉시티(worst-case time complexity)가 O(ed³)이다. 여기서 e는 변(edge)의 개수이고, d는 가장 사이즈가 큰 정의역(domain)의 사이즈이다.

각주 
 A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977.

알고리즘
제약 프로그래밍