Re: Restricting equivalent solutions inside the search (B-Prolog)

On Nov 4, 4:41 pm, Ecirbaf <fabrice.march...@xxxxxxxxx> wrote:
Restricting the search of "equivalent solutions" is generally
a problem specific constraint.

With regard to the symmetries of a magic square, one might
deal with this by restricting the location of value 1 to a
location in the upper triangular half of the upper left
quadrant. The symmetries of the square are eight-fold, so
the possible distinct locations of value 1 are reduced by
roughly a factor of 8. However for the 3x3 square this is
only a very rough factor, as the possible locations are in
that case (1,1), (1,2), and (2,2) up to symmetry.

Thanks a lot !

I see. that's perfect for the magic square.

A broad term for imposing a priori some such constraint as
can be met by "equivalent solutions" is "symmetry breaking".
Because of the problem dependent nature of these techniques,
implementing them in a way that really speeds things up as
a consequence of reducing the search space is an art.

So there is no general method to program this symmetry breaking...
And I absolutely do not see now how I could break the symmetry in
the search of still lives for Conway Game of life, where binary state
cells lay on a board.

But I'll think a bit more.

Regards,

Fabrice

I wanted to revisit the topic of detecting equivalent
(by symmetry) solutions in the context of Conway's
Game of Life.

The eight-fold symmetry of the square can be formalized
as the action of a group D4 acting on the entries of an
array with equal numbers N of rows and columns:

[Dihedral Group D4 -- Wolfram MathWorld]
http://mathworld.wolfram.com/DihedralGroupD4.html

Fabrice initially wanted to know how to "[speed] up
things in avoiding equivalent patterns inside the
search." These are actually two distinct objectives
and one does not necessarily accomplish both by the
same means.

The first concept to consider here is the orbit of
a location in the NxN array under the group action.
The size of an orbit is always a divisor of the
group order, in this case 8. So potentially one
can have locations with orbits of size 1,2,4, and 8.
Actually for this particular group action the size
of orbits depends on whether N is even or odd. If
N = 2k is even, there are k orbits of size 4 and
C(k,2) orbits of zize 8. If N = 2k + 1 is odd,
there are in addition to those orbits a singleton
(the center location) and k more orbits of size 4.
No orbits of size 2 are present in either case.

A general approach to eliminating equivalent aka
symmetric solutions is to impose a total order
on all the potential solutions (value-filled
arrays) and reject those which are not least
among their symmetric images. Note that we have
here an enlarged notion of orbit, induced by the
group acting on a collective value-filled array
(rather than simply on the individual locations).

We encounter then the issue of how to perform an
elimination of this kind efficiently. The issue
is compounded by the use of B-Prolog's constraint
handling syntax because it hides from us exactly
how the underlying generate-and-test tree is
arranged.

It seems likely to me that an accomodation to
B-Prolog's constraint solver can be reached by
a limited amount of experimentation, but since
I haven't made that study, let me speak in
terms of what we might do if we were writing
our own generate-and-test rules.

I think what I would do at the upper/outer
levels of generation is determine diagonal
and antidiagonal entries of the array. These
form the orbits of size 4 referred under size
N even and also under size N odd (apart from
the singleton center entry). The four spokes
radiating from the center to the corners are
ordered as binary integer values, and rotated
and/or reflected so that the minimum result,
ordering them clockwise from upper left, is
acheived.

In some fraction of cases, the four corner
spokes possess some degree of symmetry (e.g.
possibly equality = total symmetry) so that
there remains a choice of group actions to
apply on the remaining array entries. But
the majority of cases will have the issue
of symmetry resolved at that upper/outer
level (and no elimination of potential
solutions remains to be implemented at the
lower/inner levels of generation).

At the lower levels, we would treat first
for odd N the four spokes that radiate
from the center to the midpoints of the
sides of the array, using only what
symmetry remains from the outer level.

Finally at the innermost level we would
impose any remaining symmetry ordering
the triangular wedges appearing between
the aforementioned spokes. These are the
entries that have orbits of size 8.

regards, chip

.

Relevant Pages

  • Re: 2D FFT:
    ... I'm not aware that you can perform 64 complex FFTs ... assume you have a 2D array ... by computing x"for m> 0 and using the above symmetry ... There will be a sequence reversal of the Fourier coefficients ...
    (comp.dsp)
  • Re: Imaginary values non-null in FFTW Java wrapper real transform
    ... the format of the array returned by the FFTW real to ... An FFT of a totally real input signal will, in general, return results with nonzero real and imaginary parts. ... If the input signal has even symmetry around 0 then the FFT should be all real, ... Wescott Design Services ...
    (comp.dsp)
  • Re: Lets talk about sex
    ... # Take care of symmetry of the relation. ... # Update the array of first encounters. ...
    (comp.lang.awk)
  • Re: faster impl of atan2 in java...
    ... array of Angle objects. ... The downside to this would be creating an array of approximitly ... out that if you rerpesent that lookup table as a bytearray, ... You can further reduce that to half its size by exploing the symmetry ...
    (comp.lang.java.programmer)