arc consistency in J

NB. Michal Dobrogost 2012-10-30

NB. ----------------------------------------------------------------------------
NB. Generate a random CSP instance.

NB. Constants
n =: 4 NB. # variables
d =: 4 NB. domain size

NB. all variable domains (each one half full).
] D =: (n%2)> (]?]) n$d

NB. Our single constraint (note: constraints are not symmetric, for example x<y).
c1 =: 0= ? (2$d)$(>. d%2)
2 2 $ a: , 'x' ; 'y' ; c1

NB. all constraints.
] C =: a: , c1 ; (|:c1)

NB. adjacency matrix (pairs of variables are constrained by which constraint)
X   =: 0= ? (2$n)$2       NB. generate random matrix of [0,1]
X   =: X *. (i.n) </ i.n  NB. make it upper diagonal, zeros on diagonal
] X =: X + |: 2*X         NB. make it symmetrix referencing transpose in C.

NB. ----------------------------------------------------------------------------
NB. Generally useful functions.

NB. Compute adjacency list from an adjacency matrix.
adj =: ((<@#)&(i.n)) @ (0&<)
] A =: adj X

NB.'xs arcsX A' computes a list of all adjacent variables to those in xs.
NB.`ys arcsY A' computes a list of all adjacent variables to those in ys.
arcsX =: [: (> @ (,&.>/)) ([ (,.&.>)"0 {)
arcsY =: ({~ /:) @ (0 1&|.) @ arcsX
] (i.n) arcsX A
] (i.>.n%2) arcsY A

NB.'c revDom (Dx,Dy)' will return the domain of y supported by x.
getx   =: 0{ ]
gety   =: 1{ ]
revDom =: getx *. +./ @ (gety # [)

NB.'isValid D' Decides if all variables have at least one value in their domain.
isValid =. <./ @: (>./"1)

NB. ----------------------------------------------------------------------------
NB.'revise (xs;D)' will revise all domains of variables adjacent to those in xs
NB.                and return (newXs;newD) where newXs are those variables that
NB.                have been modified between D and newD.
revise =: 3 : 0
    ys =: (> 0{y)
    D  =. > 1{y
    if. 0 < # ys
    do.
        a  =. ys arcsY A
        ax =. 0{"1 a
        xs =. ~. ax

        NB. revLookup [x,y]  <=>  Cxy revDom (Dx;Dy)
        revLookup =. (> @ {&C @ {::&X) revDom ({&D)

        NB. produce modified domains and the variables they correspond to.
        newD =. ax *.//. revLookup"1 a

        ((newD ([: >./"1 -.@=) xs{D) # xs) ; (newD xs} D)
    else.
        (0$0) ; D
    end.
)

ac =: > @ (1&{) @ (revise^:_) @ ((i.n)&;)

NB. ----------------------------------------------------------------------------
NB. Let's run arc consistency on our generated data.
D
isValid D
] D =. ac D
isValid D