Talk:AC-3 algorithm
The pseudocode seems wrong to me, the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y (and arc-reduce(x,y) again if the domain of y was indeed reduced, and arc-reduce(y,x) again if the domain of x was reduced again, and so on...) if you want to treat an (x,y) in the worklist as a couple of variables for which there exists a R2(x,y) or R2(y,x) rather than just a directed constraint from x to y R2(x,y). The code would be much simpler with the latter solution (and I bet this is how it was before it was improperly modified). You just need to change
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
to
worklist := { (x, y) | there exists a relation R2(x, y) }
(you'll get a second couple (y,x) in the worklist if there exists a relation R2(y,x)) and
worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
to
worklist := worklist + { (z, x) | there exists a relation R2(z, x) }
(therefore if the domain of x is reduced when checking a constraint R2(x,y), (y,x) is put in the worklist too and you don't have to go through the process I mentionned at the beginning).
I don't think I've missed something, but I won't correct it before someone double-checks that.