The solver can solve sudoku puzzles (hopefully =)) but it should also be
able to handle more general csp instances where the constraints are not
symmetric. In the case of a sudoku puzzle, I think a single symmetric
not-equal constraint would suffice.
n=: 81
d=: 9
] C=: a: , < (i.d) ~:/ (i.d)
++-----------------+
||0 1 1 1 1 1 1 1 1|
||1 0 1 1 1 1 1 1 1|
||1 1 0 1 1 1 1 1 1|
||1 1 1 0 1 1 1 1 1|
||1 1 1 1 0 1 1 1 1|
||1 1 1 1 1 0 1 1 1|
||1 1 1 1 1 1 0 1 1|
||1 1 1 1 1 1 1 0 1|
||1 1 1 1 1 1 1 1 0|
++-----------------+
A is a little bit beyond me to define at the moment. It would be an 81x81
matrix. For a variable x, it would be 1 for all variables on the same row,
column and box as x and 0 otherwise.
Side note: as you can see, not-equal is not a very strong constraint.
Interleaving AC with search would probably be necessary to solve harder
sudoku instances.
Would changing:
NB. a single constraint (note: constraints are not symmetric, for example
x<y).
to
NB. a single constraint (note: constraints may be asymmetric, for example
x<y).
resolve the confusion?
Mike
On Sun, Nov 4, 2012 at 1:31 PM, Raul Miller <rauldmil...@gmail.com> wrote:
> I think I am having a problem envisioning how a sudoku-style puzzle
> can work with a relationship which is not commutative, and I am also
> having a problem having to do with the transitive character of the
> relationship.
>
> As you have put it:
>
> "(note: constraints are not symmetric, for example x<y)"
>
> I think I understand that in the general case we can have asymmetrical
> relationships, but taking sudoku as an example... I believe I
> understand "5 is not equal to any other value in the same row, in the
> same column, or in the same square". But I am having a problem
> understanding "5 is less than any other value in the same row, in the
> same column, or in the same square" -- it seems to me that even if
> that is true for 5, that it cannot be true for any other value in that
> row, column, nor square.
>
> So obviously I'm missing something important here. I just do not know
> what question to ask.
>
> Thanks,
>
> --
> Raul
>
> On Sun, Nov 4, 2012 at 3:54 PM, Michal D. <michal.dobrogost@I tgmail.com>
> wrote:
> > The adjacency matrix A is important because it tells us which constraint
> to
> > look up in C. This also explains why the lower diagonal is doubled.
> >
> > For example, take the less than constraint:
> >
> > c =: |: (i.n) </ (i.n)
> > 2 2 $ '' ; 'Dx' ; 'Dy' ; c
> > +--+-------+
> > | |Dx |
> > +--+-------+
> > |Dy|0 0 0 0|
> > | |1 0 0 0|
> > | |1 1 0 0|
> > | |1 1 1 0|
> > +--+-------+
> >
> > This constraint is useful for filtering Dx given Dy. Let's look at how
> > revDom works (revDom is the heart of the algorithm). Let's generate a
> > domain for x and y.
> >
> > Dx=: 1 1 1 1 NB. {0,1,2,3}
> > Dy=: 1 1 1 0 NB. {0,1,2}
> >
> > To visualize, stick Dy on the left, and Dx on top:
> >
> > 2 2 $ '' ; Dx ; (|:,:Dy) ; c
> > +-+-------+
> > | |1 1 1 1|
> > +-+-------+
> > |1|0 0 0 0|
> > |1|1 0 0 0|
> > |1|1 1 0 0|
> > |0|1 1 1 0|
> > +-+-------+
> >
> > Now we use Dy to select the relevant rows of c (each row represents the
> set
> > of values compatible with that value of Dy).
> >
> > Dy # c
> > 0 0 0 0
> > 1 0 0 0
> > 1 1 0 0
> >
> > Take the logical-or of these rows to compute the set of values of Dx that
> > have some compatible value in Dy.
> >
> > +./ Dy # c
> > 1 1 0 0
> >
> > Finally, take the logical-and with Dx so we don't add values that weren't
> > there in the first place.
> >
> > Dx *. +./ Dy # c
> > 1 1 0 0
> >
> > Now, with all this done, what if we want to filter Dy on Dx? We need to
> > take the transpose of c. To prevent constant transposing, A and C store
> > these for us.
> >
> > Mike
> >
> > On Sun, Nov 4, 2012 at 9:53 AM, Mike Day <mike_liz....@tiscali.co.uk>
> wrote:
> >
> >> As far as I can understand the "revise" verb, you don't need the
> >> adjacency matrix a, although it does help to have a 2-column matrix of
> >> index pairs.
> >>
> >> I think Raul has overlooked your use of the right argument ys within
> that
> >> verb, though he's right about selecting with it. Here's a derivation of
> >> arcs without explicit recourse to the adjacency matrix (I've just
> noticed
> >> that Raul presents a similar idiom):
> >>
> >> arcs=. ys (]#~ (e.~ {."1)) ($#: I.@,) *|:A
> >>
> >> I. returns a vector of indices to the ravelled boolean; $ #: turns them
> >> into a matrix of pairs of indices to an array of the shape of |:A.
> >>
> >> (]#~ (e.~ {."1)) selects those arcs with an element of ys as the
> from-node
> >> (or perhaps they're the to-nodes?)
> >>
> >> This form renders the arcs array already sorted, but note that if you
> do
> >> need to sort the elements of an array, it's sufficient to use the idiom
> >> /: ~ (rather than ({~ /:) . Presumably sorting "arcs" is
> merely a
> >> matter of taste.
> >>
> >> It's quite nice to be able to input several components of an argument by
> >> (local) name with
> >> 'A a C'=.x
> >> 'ys D'=. y
> >> rather than
> >> A=. > 0{x
> >> a=. > 1{x
> >> ys=. > 0{y
> >> D=. > 1{y
> >>
> >> As A is invariant in "ac", you could of course preset the array of
> >> indices for all arcs in A, aix =: ($#: I.@,) *|:A and use aix as
> an
> >> input to "revise" instead of a .
> >>
> >> I used *|:A or (0<|:A) here and wonder why you need to double its lower
> >> diagonal elements.
> >>
> >> I also wonder whether your example will still work if there are binary
> >> constraints involving variables (say z and t) indexed with 2 or 3. And
> >> what happens if there are more than one binary constraints on a pair of
> >> variables? eg, X+Y=4 AND X>Y ?
> >>
> >> I'd have been very pleased with myself if I'd come up with code as good
> as
> >> this when I started J - would be pretty pleased if I managed it now!
> >>
> >> Mike
> >>
> >>
> >>
> >> On 04/11/2012 2:40 PM, Raul Miller wrote:
> >>
> >>> In
> >>> A=. 0= ? (2$n)$2 NB. generate random matrix of [0,1]
> >>>
> >>> The 0= is unnecessary, and probably reflects a habit based on the
> >>> false idea that boolean algebra is does not have an integer domain.
> >>> Boolean rings have (subset of) integer domains, and [even after
> >>> redefinition] boolean algebra is a boolean ring.
> >>>
> >>> If you ever want to treat Heyting Algebras or Bayesian Probability you
> >>> might also want to consider what happens when you replace the $2 with
> >>> $0.
> >>>
> >>> I think I would also be more comfortable with
> >>> 2 2 $ ''; 'y'; 'x'; A
> >>> for the displayed table, but that's a minor quibble.
> >>>
> >>> An alternative definition for adj might be
> >>> adj=: <@I.@:*
> >>>
> >>> But somewhere around here, I get lost. Your use pattern for arcsX is:
> >>>
> >>> (i.n) arcsX A
> >>>
> >>> where A has the shape n,n
> >>>
> >>> What is the domain of the left argument of arcsX? I am guessing that
> >>> it's either i.n or a single element choosen from i.n but if that is
> >>> the case, I think I'd define arcsX to only work for the i.n case --
> >>> the name says "arcs" after all. Also, if I wanted to extract the
> >>> values from the result of arcsX which correspond to a single value
> >>> from i. n, that's simple enough -- I can select on the first column of
> >>> the result.
> >>>
> >>> In other words, perhaps something like this:
> >>>
> >>> arcs=: $ #: I.@,
> >>> arcs *A
> >>>
> >>> Also, I have not taken the time yet, to read "revise", so I will stop
> >>> here.
> >>>
> >>>
> >>
> ------------------------------**------------------------------**----------
> >> For information about J forums see
> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
> >>
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
