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
