arc consistency in J #2

NB. ----------------------------------------------------------------------------
NB. Arc consistency for constraint satisfaction problems (CSP).
NB. ----------------------------------------------------------------------------
NB. Michal Dobrogost 2012-11-03
NB.
NB. A CSP can model various satisfaction problems such as sudoku puzzles.
NB. A CSP consists of a set of variables X, each with an associated domain D of
NB. values. In sudoku, X = {1,2,...,81} and for each x in X, Dx = {1,2,...,9}.
NB. There are also a set of constraints C between pairs of variables.
NB. In sudoku, Cxy is simply the 'not equal' constraint and applies to all pairs
NB. of variables in rows, columns, and 3x3 squares.
NB.
NB. Arc consistency (AC) is a filtering algorithm that removes values, from the
NB. domain of a variable, that can not participate in any solution. In sudoku,
NB. if a variable x1 has domain {1,2,6} and is on the same row as x2 with domain
NB. {6} we can remove the value 6 from the domain of x1 because there can not
NB. be a solution where Dx1 = Dx2 = {6}.
NB.
NB. Filtering algorithms are usually combined with backtracking search which
NB. guesses a specific value for a variable with multiple available values.
NB. Guesses are interleaved with filtering (commonly refered to as maintaining
NB. arc consistency (MAC) search).
NB.
NB. Thanks to:
NB.   Raul M. for better arcsX, arcsY.
NB.   [email protected] for misc suggestions.

NB. ----------------------------------------------------------------------------
NB. Generate a random CSP instance and filter it.

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

NB.* 'D' is the domain of each variable, one row per variable.
] D=. (n%2) > (?]) n$d

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

NB.* 'C' is all of our constraints with the 0'th entry being the empty.
] C=. a: , c1 ; (|:c1)

NB.* 'A' an adjacency matrix (which constraint is between a pair of variables).
A=. 0= ? (2$n)$2       NB. generate random matrix of [0,1]
A=. A *. (i.n) </ i.n  NB. make it upper diagonal, zeros on diagonal
] A=. A + |: 2*A       NB. make it symmetrix referencing transpose in C.
2 2 $ a: , 'y' ; 'x' ; A

NB. ----------------------------------------------------------------------------
NB. Utility functions.

NB.* 'adj A' computes adjacency list from an adjacency matrix.
adj=: ((<@#)&(i.n)) @ (0&<)
NB.* 'a' is an adjacency list: which variables are adjacent to a given variable.
] a=. adj A

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=: [  ((#~ #@>) ,. ;@]) {
arcsY=: [  (;@] ,. (#~ #@>)) {
] (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 domains are non-empty.
isValid=: <./ @: (>./"1)

NB. ----------------------------------------------------------------------------
NB. The arc consistency algorithm itself.

NB.* '(A;a;<C) revise (xs;D)' filter domains of all variables (ys) adjacent to
NB.                           xs. Returns (newYs;newD) where newYs are those
NB.*                          variables that are different across newD and D.
revise=: 4 : 0
    A=. > 0{x
    a=. > 1{x
    C=. > 2{x

    ys=. > 0{y
    D=.  > 1{y

    if. 0 < # ys
    do.
        arcs=. ({~ /:) ys arcsY a
        ax=. 0{"1 arcs
        xs=. ~. ax

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

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

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

NB.* '(A;a;<C) ac (xs;D)' return D filtered into an arc consistent state given
NB.*                      that the the variables in xs have been changed.
NB.*                      Use (i.#D);D as right argument to filter from scratch.
ac=: 4 : 0
    > (1&{) ((x&revise)^:_) y
)

NB. ----------------------------------------------------------------------------
NB. Filter the random instance.

NB. Recall the random instance.
(A;a;<C)
D

NB. Filter the random instance.
] D=. (A;a;<C) ac ((i.#D);D)

NB. Are all the filtered domains non-empty?
isValid D