Re: Non dominating queens problem


"Bart Demoen" <bmd@xxxxxxxxxxxxxxxxx> wrote in message news:1114720758.939812@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> TS wrote:
>
>> Place N Queens on an N*N board leaving a maximum number of unattacked
>> cells.
>>

*snip*

> My attempt was purely Prolog - if someone tried a CLP formulation,
> please tell us about it and your experience.
> If someone has some (proven) insights in how to reduce the search space
> drastically, please let us know !

Well, so far the only things I've come up with don't limit the space by
much...

- The first queen has 8-fold symmetry so you only have to
search [[0,0],[0,1],...[0,floor((n+1)/2)],[1,1],[1,2]...[1,floor((n+1)/2)],
...[floor((n+1)/2),floor((n+1)/2)]] for it's position
- After searching a first queen square it's three or seven symmetries can also
be culled from the search space, any solution that uses them can be rotated
and reflected to an already searched position.

What would be nice to have...

- A proof that moving a non-attacking queen can always be moved to an
attacking position without increasing the number of squares attacked.
- A proof that there exists a solution for a board of size n where
the queens form a fully connected graph, attack-wise.
- A proof that at least one solution can be reached by adding queens
one at a time that minimizes the number of additonal squares attacked.

--
Geoff


.