N-QUEENS problem with some differences

[Bob]

Hi, I need some help to do an exercice which is like N-Queens problem
but with some differences :

My first problem is that I must do n-queen problem with a rectangle
(nxm) and not a square (n).
But I don't see how to transform queens(n) code with queen(n,m)

For example with this n-queen code :
queens(N,Qs):-
range(1,N,Rs),
permu(Rs,Qs),
test(Qs).

/* range(A,B,L) :- L is the list of numbers A..B*/

range(A,A,[A]).
range(A,B,[A|L]) :-
A < B,
A1 is A+1,
range(A1,B,L).

/* permu(Xs,Zs) :- the list Zs is a permutation of the list Xs*/

permu([],[]).
permu(Qs,[Y|Ys]) :-
del(Y,Qs,Rs),
permu(Rs,Ys).

del(X,[X|Xs],Xs).
del(X,[Y|Ys],[Y|Zs]) :-
del(X,Ys,Zs).

/* test(Qs) :- the list Qs represents a non-attacking queens
solution*/

test(Qs) :-
test(Qs,1,[],[]).

/* test(Qs,X,Cs,Ds) :- the queens in Qs, representing columns X to N,
are not in conflict with the diagonals Cs and Ds*/

test([],_,_,_).
test([Y|Ys],X,Cs,Ds) :-
C is X-Y, \+ memberchk(C,Cs),
D is X+Y, \+ memberchk(D,Ds),
X1 is X + 1,
test(Ys,X1,[C|Cs],[D|Ds]).

The exact problem is : an area (nxm), divided in square, and men must
be placed to see all square of the area. The number of men must be the
least possible.
it must be done in 3 case :
- no restriction of placement of men (for exemple, they can be placed
to be seen each other)
- a man cannot be placed on a square seen by another man
- there is obstacles on some square which block visibility (we
generate manualy the obsacles)

I'm newbie in prolog and I have great difficulties to resolve it.
I'll be very pleased if you can help me.
Thx.

[Chip Eastham]

Similarities aside, I think the N-queens
code you are looking at is specialized to
that problem to an extent that makes it not
very helpful for reuse on your new problems.

Note that if the board is mxn, and there are
n queens or "men", then m < n implies more
than one piece on some row. That's not a
problem for the first "case" (no restriction),
but it means for the second case (assuming
being "seen by another man" doesn't allow
more than one on the same row), that m is
at least n.

So the shortcut of the N-queens problem,
wherein the positions can be tracked as a
permutation (the row(i) of the queen in
column i), breaksdown on an mxn board for
different reasons in the first and second
cases.

The first case asks that the positions be
unrestricted. So in any case rows are
not restricted to be a function of columns.

Even in the second case, where one can say
only one piece per row (and one per column),
the row range will be contained in {1,..,m},
not {1,..,n}.

So the second case can benefit from choosing
an n-tuple or list of length n from entries
in the range {1,..,m}, rather than merely a
permutation of {1,..,n} like the N-queens
code used.

With the third case you may be better off
looking at how to choose n-subsets of the
mxn board positions disjoint from obstacle
positions.

regards, chip

[Bob]

Thank you for your response.
and you're right, it's not the same problem.

For the first step, men without restriction but they must be the less
large number as possible :
How can we say in Prolog that I want to have the minimum number of men
as possible ?

there is a simple method or the problem is more complicated ?

[Chip Eastham]

There is no shortcut in Prolog to finding the
"minimum" solution in general. Prolog's search
strategy is often described as "depth first",
meaning that in seeking to satisfy a goal, the
Prolog engine pursues subgoals of the goal, and
their subgoals and so on, until ultimately a
"leaf" of the search tree is satisfied.

With some forethought we may be able to arrange
the search tree so that the first solution that
gets found will be minimal. For example:

attackAllSquares(M,N,List) :-
M <= N, /* by reflection */
buildBoard(M,N,Board), /* list of cells */
for(K,2,M), /* note as below */
choose(K,Board,Queens),
checkAllSquaresAttacked(Board,Queens).

Here the idea is set a subgoal for(K,2,M) that
constrains the number of Queens (whose placing
is determined by the next subgoal choose/3).
The first solution found will necessarily use
the minimum number K of Queens.

This may not be the most efficient approach,
but it is clear in why it attains a minimal
solution.

Preliminarily you should consider if a Queen
is considered to "attack" the square it sits
on. If it does not (as I would guess), then
at least two Queens are needed, even for a
board with a single row, as each Queen must
be "attacked" by another. Thus I started my
range for K at 2 (going up to M).

For M > 1 there will always be a solution
with M pieces. A more efficient strategy
might be to count downwards from M-1, looing
for the largest K such that no solution
exists. But efficiency is secondary to
clarity when you are learning the ropes!

regards, chip

[Thriller]

This problem reminds me a more classic one, which is how to place a
minimum number of museum attendants (watchmen), the museum has NxM
corridors and some corridors may have staues/objects that block
visibility.
The unique differnce is that there is no diagonal visibility in the
museum problem.

Bob a ï¿œcrit :

[Chip Eastham]

On Nov 22, 6:56 am, Chip Eastham <hardm...@gmail.com> wrote:
> On Nov 21, 4:23 pm, Bob <beber...@gmail.com> wrote:
>
> > Thank you for your response.
> > and you're right, it's not the same problem.
>
> > For the first step, men without restriction but they must be the less
> > large number as possible :
> > How can we say in Prolog that I want to have the minimum number of men
> > as possible ?
>
> > there is a simple method or the problem is more complicated ?
>
> There is no shortcut in Prolog to finding the
> "minimum" solution in general.  Prolog's search
> strategy is often described as "depth first",
> meaning that in seeking to satisfy a goal, the
> Prolog engine pursues subgoals of the goal, and
> their subgoals and so on, until ultimately a
> "leaf" of the search tree is satisfied.
>
> With some forethought we may be able to arrange
> the search tree so that the first solution that
> gets found will be minimal.  For example:

Oops! The head of my rule should use Queens
rather than List as the third argument (to
match how subgoals were coded):

Should have been:

attackAllSquares(M,N,Queens) :-

>     M <= N,                  /* by reflection */
>     buildBoard(M,N,Board),   /* list of cells */
>     for(K,2,M),              /* note as below */
>     choose(K,Board,Queens),
>     checkAllSquaresAttacked(Board,Queens).

regards, chip

[PrologBob]

Ok, thank you, I see... not so easy... for me well understanding the
problem, if we don't talk about code, and just thinking on writing CSP
with define variables and domain :
space[N,M] where N and M are integer who define length of the space
Men are defined by Mx=[I,J] where x is the identifier of a man and I,J
the emplacement on the space.
and I Є {1..N}, and J Є {1..M}.

And a basic constraint, for example, to haven't two men placed on the
same square : Constraint1={ Mx[I,J] ≠ Mk[I,J] }

How can we express the other constraints like "all the squares must be
seen" and "The minimum number of man must be used" ?
I have great difficulties to write the CSP, I don't find how express
constraints with variables and I think if I have the answer of these
question, all will be more cleary for me.

regards,

[Chip Eastham]

Hi, Bob:

At top you mentioned you were doing an exercise,
you were a "newbie in prolog", and you posted
some snippets of Prolog. So I assumed you were
asking about a solution by Prolog programming.
Now you seem to be refocusing on constraint
satisfaction programming (CSP).

There's some overlap, but in general if the
purpose of your exercise is to help you learn
Prolog programming, it may be best to stick to
basics.

Here again is the snippet I posted, answering
the question of how Prolog can provide among
all solutions, that which has the minimum
number of pieces:

attackAllSquares(M,N,List) :-

M <= N, /* by reflection */
buildBoard(M,N,Board), /* list of cells */
for(K,2,M), /* note as below */
choose(K,Board,Queens),
checkAllSquaresAttacked(Board,Queens).

Recall that I asked if a piece is considered to
guard the square it is on. This is something
you have to address. But the questions you've
asked are these:

> How can we express the other constraints like
> "all the squares must be seen" and "The minimum
> number of man must be used" ?

The last constraint is satisfied in the approach
I gave because the first solution found (Prolog
can backtrack to find multiple solutions) will
be one that uses the minimum number of pieces.

The "all the squares must be seen" constraint is
to be handled by the (as yet unwritten) predicate

checkAllSquaresAttacked(Board,Queens)

whose details of course depend on your answer to
my question above, whether a piece "sees" the
square it sits on.

Finally you mentioned the constraint that the
pieces should all be positioned on distinct
squares. This constraint was represented in my
approach by the (as yet unwritten) predicate

choose(K,Board,Queens)

The idea here is that Board is a list of cells
(squares) of length K or more, and Queens is
a sublist of K entries taken from Board and
kept in the same order.

Let me suggest how such a predicate can be
written. The theme of Prolog coding is often
reducing a problem to simpler terms, until a
"base case" is reached, similar to mathematical
induction (recursion in programming terms).

choose(0,_,[]) :- !.
choose(K,[H|T],[H|L]) :-
K > 0,
M is K-1,
choose(M,T,L).
choose(K,[_|T],L) :-
K > 0,
choose(K,T,L).

Assuming all entries of Board are distinct,
then any sublist Queens found by choose/3 as
above will also have distinct entries.

regards, chip

[Bob]

Hi Chip,

first, thank you once more for your help.
I have tried to do a beginning of code with all you told me.
I confirm you that a "queen" who is on a square, see this square.

I don't really have undestand the predicat "choose", spécificly the
difference between two last "choose" : when does the choose(K,[_|T],L)
is called instead of choose(K,[H|T],[H,L]). ? I know that _ means a
sort of "nothing", but I don't see how it works in this case.
And I don't see for the moment how checking the squares to know if
they are all attacked.

Let me show you my beginning code :

:- lib(ic).

main(M,N) :-
MN is M*N, %Number of squares
dim(Board, [M,N]), %board construction
dim(Queens, [M,N]), %queens construction
Board :: 1..MN, %Board domain
Queens :: 1..MN, %Queens domain
testlength(M,N,Board,Queens), %To determinate if M>N
labeling(Queens), %instanciation of variables
print_Queens(Queens). %Print solution

testlength(M,N,Board,Queens):-
M#=<N,
mainloop(M,N,Board,Queens).

testlength(M,N,Board,Queens):-
M#>N,
mainloop(N,M,Board,Queens).

mainloop(M,N,Board,Queens):-
(
for(K,1,M), %K start at 1 because queen see the square where she is
param(Board,Queens) %To not losing variables
do
choose(K,Board,Queens)
),

queenNotSeenByOtherQueen(M,N,Queens). %for the second part of
exercice witch no "queen" must be seen by another

%checkAllSquaresAttacked(M,N,Queens).

choose(0,_,[]) :- !.

choose(K,[H|T],[H|L]) :-

K #> 0,
M is K-1,
choose(M,T,L).

choose(K,[_|T],L) :-

K #> 0,
choose(K,T,L).

%checkAllSquaresAttacked(M,N,Queens):- %don't see how doing that ;
perhaps with affecting values for each square. But if I know how to
affect values, I don't know how to do after that.

queenNotSeenByOtherQueen(M,N,Queens):-
( for(I,1,M), param(M,N,Queens) do
( for(J,1,N), param(I,M,Queens) do
Queens[I,J] #\= Queens[I+(1..M-I),J], %not the
same row forward
Queens[I,J] #\= Queens[I-(1..M-I),J], %not the same row backward
Queens[I,J] #\= Queens[I,J+(1..N-J)], %not the same column downward
Queens[I,J] #\= Queens[I,J-(1..N-J)], %not the same column upward
Queens[I,J] #\= Queens[I+(1..M_I),J+(1..N-I)], %not the same diag
down/forward
Queens[I,J] #\= Queens[I+(1..M_I),J-(1..N-I)], %not the same diag
up/forward
Queens[I,J] #\= Queens[I-(1..M_I),J+(1..N-I)], %not the same diag
down/backward
Queens[I,J] #\= Queens[I-(1..M_I),J-(1..N-I)] %not the same diag up/
backward
)
).

print_Queens(Queens) :-
dim(Queens, [N,M]),
( for(I,1,N), param(M,Queens) do
( for(J,1,M), param(I,Queens) do
CaseQueen is Queens[I,J],
printf("%d", CaseQueen)
), nl
),nl.

regards,

[Joachim Schimpf]

Bob wrote:
>
> Let me show you my beginning code :

Before you write so much code, first get a clearer idea
of how you want to model the problem in terms of variables
and mathematical relations. I can't understand what you
intend to do with 2*N*M variables of domain 1..M*N.

I'd suggest you have a look at the "Non-dominating Queens" and
"Crowded Chessboard" examples at http://eclipse-clp.org/examples

-- Joachim

[Chip Eastham]

Hi, Bob:

Thanks for sharing your work so far. It seems
you are writing an ECLiPSe program, which is a
little different from Prolog. A good bit of
syntax is shared, but I'm not in a position
to help with ECLiPSe specific details.

If the syntax for lists and "anonymous variables"
(underscore) in Prolog is unfamiliar to you,
you may benefit from reviewing a tutorial.

This newsgroup's FAQ (frequently asked questions,
see a recent thread by maintainer Markus Triska)
has some links to suggested Prolog tutorials. I
don't see one specifically for ECLiPSe, but the
Documentation link here has one:

[ECLiPSe Home Page]
http://www.eclipse-clp.org/

I had in mind that you would be using "pure"
Prolog and representing the board as a list of
squares and the position of queens as another
list of squares taken from the board by choose/3.
Let me limit my discussion to explaining how my
implementation of choose/3 would work, but it
may not be relevant to a constraint satisfaction
program (your approach):

choose(0,_,[]) :- !.
choose(K,[H|T],[H|L]) :-

K > 0,

M is K-1,
choose(M,T,L).
choose(K,[_|T],L) :-

K > 0,
choose(K,T,L).

The first rule says the only choice of zero
items (first argument) from a list (second
argument) is the empty list (third argument).
The exclamation point is a "cut", which tells
the Prolog engine not to search for further
solutions.

The second rule says that if we want K more
than zero items, one way to do that is to
take the first item ("head") of the list
and reduce the problem to choosing K-1
items from the rest of the list ("tail").

The third rule gives another way, skipping
the "head" of the list and choosing all K
items from the "tail".

Between the second and third rules we have
all the "nonempty" possibilities to choose
K items from a list.

In searching for solutions (and we need to
consider all solutions, potentially), the
Prolog engine tries all the rules in the
order listed. When a predicate's rule
invokes itself, that is recursion, and to
satisfy that "subgoal" the Prolog engine
starts the consideration of rules from the
top again.

regards, chip

[Thriller]

Chip Eastham a exprimￜ avec prￜcision :

> On Nov 25, 6:58ï¿œam, Bob <beber...@gmail.com> wrote:
>> Hi Chip,
>>
>> first, thank you once more for your help.
>> I have tried to do a beginning of code with all you told me.
>> I confirm you that a "queen" who is on a square, see this square.
>>

>> I don't really have undestand the predicat "choose", spï¿œcificly the

>> difference between two last "choose" : when does the choose(K,[_|T],L)
>> is called instead of choose(K,[H|T],[H,L]). ? I know that _ means a
>> sort of "nothing", but I don't see how it works in this case.
>> And I don't see for the moment how checking the squares to know if
>> they are all attacked.
>>
>> Let me show you my beginning code :
>>
>>> - lib(ic).
>>
>> main(M,N) :-

>> ￜ ￜ ￜ ￜ MN is M*N, ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ%Number of squares
>> ￜ ￜ ￜ ￜ dim(Board, [M,N]), ￜ ￜ ￜ%board construction
>> ￜ ￜ ￜ ￜ dim(Queens, [M,N]), ￜ ￜ %queens construction
>> ￜ ￜ ￜ ￜ Board :: 1..MN, ￜ ￜ ￜ ￜ %Board domain
>> ￜ ￜ ￜ ￜ Queens :: 1..MN, ￜ ￜ ￜ ￜ%Queens domain
>> ￜ ￜ ￜ ￜ testlength(M,N,Board,Queens), ￜ %To determinate if M>N
>> ￜ ￜ ￜ ￜ labeling(Queens), ￜ ￜ ￜ ￜ ￜ ￜ ￜ %instanciation of variables
>> ￜ ￜ ￜ ￜ print_Queens(Queens). ￜ %Print solution
>>
>> testlength(M,N,Board,Queens):-
>> ￜ ￜ ￜ ￜ M#=<N,
>> ￜ ￜ ￜ ￜ mainloop(M,N,Board,Queens).
>>
>> testlength(M,N,Board,Queens):-
>> ￜ ￜ ￜ ￜ M#>N,
>> ￜ ￜ ￜ ￜ mainloop(N,M,Board,Queens).
>>
>> mainloop(M,N,Board,Queens):-
>> ￜ ￜ ￜ ￜ (
>> ￜ ￜ ￜ ￜ for(K,1,M), ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ %K start at 1 because queen see the
>> square where she is ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ param(Board,Queens) ￜ ￜ %To not losing
>> variables ￜ ￜ ￜ ￜ do
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ choose(K,Board,Queens)
>> ￜ ￜ ￜ ￜ ),
>>
>> ￜ ￜ ￜ ￜ queenNotSeenByOtherQueen(M,N,Queens). ￜ %for the second part of

>> exercice witch no "queen" must be seen by another
>>

>> ￜ ￜ ￜ ￜ %checkAllSquaresAttacked(M,N,Queens).

>>
>> choose(0,_,[]) :- !.
>>
>> choose(K,[H|T],[H|L]) :-

>> ￜ ￜ K #> 0,
>> ￜ ￜ M is K-1,
>> ￜ ￜ choose(M,T,L).

>>
>> choose(K,[_|T],L) :-

>> ￜ ￜ K #> 0,
>> ￜ ￜ choose(K,T,L).
>>
>> %checkAllSquaresAttacked(M,N,Queens):- ￜ%don't see how doing that ;

>> perhaps with affecting values for each square. But if I know how to
>> affect values, I don't know how to do after that.
>>
>> queenNotSeenByOtherQueen(M,N,Queens):-

>> ￜ ￜ ￜ ￜ ( for(I,1,M), param(M,N,Queens) do
>> ￜ ￜ ￜ ￜ ￜ ￜ ( for(J,1,N), param(I,M,Queens) do
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\= Queens[I+(1..M-I),J], ￜ %not the
>> same row forward
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\= Queens[I-(1..M-I),J], ￜ %not the
>> same row backward ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\=
>> Queens[I,J+(1..N-J)], ￜ %not the same column downward ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ
>> ￜ Queens[I,J] #\= Queens[I,J-(1..N-J)], ￜ %not the same column upward ￜ ￜ ￜ
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\= Queens[I+(1..M_I),J+(1..N-I)], ￜ%not the
>> same diag down/forward ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\=
>> Queens[I+(1..M_I),J-(1..N-I)], ￜ%not the same diag up/forward
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\= Queens[I-(1..M_I),J+(1..N-I)], ￜ%not
>> the same diag down/backward
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ Queens[I,J] #\= Queens[I-(1..M_I),J-(1..N-I)] ￜ %not

>> the same diag up/ backward

>> ￜ ￜ ￜ ￜ ￜ ￜ )
>> ￜ ￜ ￜ ￜ ).
>>
>> print_Queens(Queens) :-
>> ￜ ￜ ￜ ￜ dim(Queens, [N,M]),
>> ￜ ￜ ￜ ￜ ( for(I,1,N), param(M,Queens) do
>> ￜ ￜ ￜ ￜ ￜ ￜ ( for(J,1,M), param(I,Queens) do
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ CaseQueen is Queens[I,J],
>> ￜ ￜ ￜ ￜ ￜ ￜ ￜ ￜ printf("%d", CaseQueen)
>> ￜ ￜ ￜ ￜ ￜ ￜ ), nl
>> ￜ ￜ ￜ ￜ ),nl.

Hello!

This exercice is very intersting and it would be great if we end up
with both solutions (csp and pure prolog).

I don't see how to code the checkAllSquaresAttacked/3.
Here is a snippet from the "Non-dominating Queens" example that seems
to count the number of attacked cells :

flatten_matrix(Attacked, Attacks),
Attacks :: 0..1,
NAttacks #= sum(Attacks),
( multifor([I,J],1,N), param(Board,Attacked,N) do
findall(K-L,
(between(1,N,1,K), between(1,N,1,L), attacks(K,L,I,J)),
AttackPos),
( foreach(K-L,AttackPos), param(Board,Attacked,I,J) do
Attacked[I,J] #>= Board[K,L]
)
),

Any idea of how to count the number of attacked squares? and then if
the number is less than N*M then checkAllSquaresAttacked/3 is false
else it is true.
Or maybe there is a better approach.

Thank you.

[Chip Eastham]

On Nov 25, 11:24 am, Thriller <rthril...@gmail.com> wrote:
> Chip Eastham a exprimé avec précision :

>
>
>
> > On Nov 25, 6:58 am, Bob <beber...@gmail.com> wrote:
> >> Hi Chip,
>
> >> first, thank you once more for your help.
> >> I have tried to do a beginning of code with all you told me.
> >> I confirm you that a "queen" who is on a square, see this square.
>

> >> I don't really have undestand the predicat "choose", spécificly the

> >> difference between two last "choose" : when does the choose(K,[_|T],L)
> >> is called instead of choose(K,[H|T],[H,L]). ? I know that _ means a
> >> sort of "nothing", but I don't see how it works in this case.
> >> And I don't see for the moment how checking the squares to know if
> >> they are all attacked.
>
> >> Let me show you my beginning code :
>
> >>> - lib(ic).
>
> >> main(M,N) :-

> >> MN is M*N, %Number of squares
> >> dim(Board, [M,N]), %board construction
> >> dim(Queens, [M,N]), %queens construction
> >> Board :: 1..MN, %Board domain
> >> Queens :: 1..MN, %Queens domain
> >> testlength(M,N,Board,Queens), %To determinate if M>N
> >> labeling(Queens), %instanciation of variables
> >> print_Queens(Queens). %Print solution
>
> >> testlength(M,N,Board,Queens):-
> >> M#=<N,
> >> mainloop(M,N,Board,Queens).
>
> >> testlength(M,N,Board,Queens):-
> >> M#>N,
> >> mainloop(N,M,Board,Queens).
>
> >> mainloop(M,N,Board,Queens):-
> >> (

> >> for(K,1,M), %K start at 1 because queen see the
> >> square where she is param(Board,Queens) %To not losing
> >> variables do
> >> choose(K,Board,Queens)
> >> ),
>
> >> queenNotSeenByOtherQueen(M,N,Queens). %for the second part of

> >> exercice witch no "queen" must be seen by another
>

> >> %checkAllSquaresAttacked(M,N,Queens).
>
> >> choose(0,_,[]) :- !.
>
> >> choose(K,[H|T],[H|L]) :-

> >> K #> 0,

> >> M is K-1,
> >> choose(M,T,L).
>
> >> choose(K,[_|T],L) :-

> >> K #> 0,
> >> choose(K,T,L).
>
> >> %checkAllSquaresAttacked(M,N,Queens):- %don't see how doing that ;

> >> perhaps with affecting values for each square. But if I know how to
> >> affect values, I don't know how to do after that.
>
> >> queenNotSeenByOtherQueen(M,N,Queens):-

> >> ( for(I,1,M), param(M,N,Queens) do
> >> ( for(J,1,N), param(I,M,Queens) do

> >> Queens[I,J] #\= Queens[I+(1..M-I),J], %not the
> >> same row forward
> >> Queens[I,J] #\= Queens[I-(1..M-I),J], %not the
> >> same row backward Queens[I,J] #\=

> >> Queens[I,J+(1..N-J)], %not the same column downward
> >> Queens[I,J] #\= Queens[I,J-(1..N-J)], %not the same column upward
> >> Queens[I,J] #\= Queens[I+(1..M_I),J+(1..N-I)], %not the

> >> same diag down/forward Queens[I,J] #\=

> >> Queens[I+(1..M_I),J-(1..N-I)], %not the same diag up/forward
> >> Queens[I,J] #\= Queens[I-(1..M_I),J+(1..N-I)], %not
> >> the same diag down/backward

> >> Queens[I,J] #\= Queens[I-(1..M_I),J-(1..N-I)] %not

> >> the same diag up/ backward

> >> )
> >> ).
>
> >> print_Queens(Queens) :-
> >> dim(Queens, [N,M]),
> >> ( for(I,1,N), param(M,Queens) do
> >> ( for(J,1,M), param(I,Queens) do

> >> CaseQueen is Queens[I,J],

> >> printf("%d", CaseQueen)
> >> ), nl
> >> ),nl.
>
> >> regards,

[snip my choose/3 discussion, etc.]

> Hello!
>
> This exercice is very intersting and it would be great if we end up
> with both solutions (csp and pure prolog).
>
> I don't see how to code the checkAllSquaresAttacked/3.
> Here is a snippet from the "Non-dominating Queens" example that seems
> to count the number of attacked cells :
>
> flatten_matrix(Attacked, Attacks),
> Attacks :: 0..1,
> NAttacks #= sum(Attacks),
> ( multifor([I,J],1,N), param(Board,Attacked,N) do
> findall(K-L,
> (between(1,N,1,K), between(1,N,1,L), attacks(K,L,I,J)),
> AttackPos),
> ( foreach(K-L,AttackPos), param(Board,Attacked,I,J) do
> Attacked[I,J] #>= Board[K,L]
> )
> ),
>
> Any idea of how to count the number of attacked squares? and then if
> the number is less than N*M then checkAllSquaresAttacked/3 is false
> else it is true.
> Or maybe there is a better approach.

Hi, Thriller:

In my code checkAllSquaresAttacked(Board,Queens)
is wordy because of the "depth" of auxiliary
predicates needed.

Ultimately we make your way to a relationship
between two squares, attackedBy(Sqr,Qn). But
the logic of checkAllSquaresAttacked/2 concerns
two lists, Board and Queens:

for all Sqr in Board, there exists Qn in Queens
such that attackedBy(Sqr,Qn)

To do the universal quantification (over the
finite domain Board) I make use of negation:

checkAllSquaresAttacked(Board,Queens) :-
not(memberUnattacked(Board,Queens)).

memberUnattacked([H|_],Queens) :-
not(attackedByMember(H,Queens)).
memberUnattacked([_|T],Queens) :-
memberUnattacked(T,Queens).

attackedByMember(Sqr,[H|_]) :-
attackedBy(Sqr,H).
attackedByMember(Sqr,[_|T]) :-
attackedByMember(Sqr,T).

Bob, the original poster, clarified that a
piece does attack the square it sits on,
so I've "commented out" the first rule of
predicate attackedBy/2. I used functor
sqr/2 with integer arguments to represent
squares of the board:

/* attackedBy(SQR,SQR) :- !, fail. */
attackedBy(sqr(I,J),sqr(K,L)) :-
I = K; /* rank */
J = L; /* file */
0 is abs(I-K) - abs(J-L). /* diag */

regards. chip