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

Author

Restricting equivalent solutions inside the search (B-Prolog)

Ecirbaf

2007-11-03, 10:15 pm

Hi !

I see it was a recent "redundancy" topics.

But maybe is this a different problem :

You can find all solutions of a magic square for example, and then
filter rotated or symmetrical solutions.
( For a 3x3 -> 8 solutions -> 1 solution indeed )

However, how speeding up things in avoiding equivalent patterns
inside the search ?

Thanks for any hint.

Fabrice

Chip Eastham

2007-11-04, 4:28 am

On Nov 3, 8:37 pm, Ecirbaf <fabrice.march...@orange.fr> wrote:
> Hi !
>
> I see it was a recent "redundancy" topics.
>
> But maybe is this a different problem :
>
> You can find all solutions of a magic square for example, and then
> filter rotated or symmetrical solutions.
> ( For a 3x3 -> 8 solutions -> 1 solution indeed )
>
> However, how speeding up things in avoiding equivalent patterns
> inside the search ?
>
> Thanks for any hint.
>
> Fabrice

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.

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.

regards, chip

Ecirbaf

2007-11-04, 7:08 pm

> 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

Chip Eastham

2007-11-11, 10:08 pm

On Nov 4, 4:41 pm, Ecirbaf <fabrice.march...@orange.fr> wrote:
>
>
> Thanks a lot !
>
> I see. that's perfect for the magic square.
>
>
> 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

Markus Triska

2007-11-12, 7:10 pm

Ecirbaf <fabrice.marchant@orange.fr> writes:

> 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.

Lots of options; for example, if the board looks like:

A ... D
: ... :
: ... :
B ... C

you can impose the constraints A #>= B, A #>= C, A #>= D, and D #>= B.
For magic squares, you can use #>/2 instead.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Sponsored Links