Some explanation about 8 queen solution that use permutation

Question

I am studyin Prolog for an universitary exam on SWI Prolog implementation.

I have some doubt about how work this version of 8 Queen problem that solve the problem using the permutations:

solution(Queens) :-
 permutation([1,2,3,4,5,6,7,8], Queens),
 safe(Queens).

permutation([],[]).

permutation([Head|Tail],PermList) :-
 permutation(Tail,PermTail),
 del(Head,PermList,PermTail).

del(Item,[Item|List],List).

del(Item,[First|List],[First|List1]) :-
 del(Item,List,List1).

safe([]).

safe([Queen|Others]) :-
 safe(Others),
 noattack(Queen,Others,1).

noattack(_,[],_).

noattack(Y,[Y1|Ylist],Xdist) :-
 Y1-Y=\=Xdist,
 Y-Y1=\=Xdist,
 Dist1 is Xdist + 1,
 noattack(Y,Ylist,Dist1).

In a previous resolution I used this solution template: [1\Y1, 2\Y2, 3\Y3, 4\Y4, 5\Y5, 6\Y6, 7\Y7, 8\Y8] that simply say that every queen have to be on different rows the X calue could be constrained.

This version of the program it's pretty difference because we can observe that to prevent vertical attack all the queens have to be on different rows, so I have a queen for each row.

So without losing information so I can say that the solution will be a permutation of the list: [1,2,3,4,5,6,7,8] in wich every element rappresent the Y coordinate of a queen.

so in this case I am rappresenting a queen position only by its Y coordinate (its row index)

So I have the solution relation than say that a list Queens is a solution if Queens is a premutation of [1,2,3,4,5,6,7,8] original list and if this permutation is safe (every queen in this permutation list don't attack the others queen).

Ok, this is clear...now it is defined the safe relation.

There is a base case that say that if the list is empty then this is safe because there is no attack.

And there is a general case in wich the list is not empty. If the list is not empty I can divide it in [Queen|Others] where Queen is the first queen in the list and Others is the remaining sublist...so the original list [Queen|Others] is safe if the sublist Others it is itself a solution (if it is safe, if there is no attack in Others) and if the first item Queen do not attack the other queen in others sublist...

Ok...until now I think that it is clear for me...

Now I have some problems with the definition of noattack relation !!!

The problem is that I rappresent a queen position only by its Y coordinate and the X coordinate it is not explicity present.

I have understand that for circumvent this limitation of the rappresentation there is the folowing generalizzation (I hope to have understood well...I am not so sure...): ** I know also that there must be a queen on each column of the board, so the X distance from the first queen in the list (Queen) and the sublist Others must be 1**

Where the distance from the first item Queen and the sublist Others is the X distance from the first item Queen and the queen nearest to it, is it righ my reasoning?

So the noattack relation is TRUE if the queen are on different columns (always true for construction) and I can express that have to be on different row sayng that the X distance from Queen and the nearest queen in the Others sublist is 1.

But, if my reasoning is truem I am finding many trouble trying to understand how rappresent this thing in this part of code:

noattack(Y,[Y1|Ylist],Xdist) :-
 Y1-Y=\=Xdist,
 Y-Y1=\=Xdist,
 Dist1 is Xdist + 1,
 noattack(Y,Ylist,Dist1).

Answer 1

i think your problem is only these 2 lines:

Y-Y1=/=Xdist,
Y1-Y=/=Xdist,

it checks whether the queen which has Y, attacks the queen in the row with a distance of Xdist in a diagonal way or not. (|Y - Y1| = Xdist --> diagonal attack ).

the other way to attack other queens is to qttack them in the same row, that doesn't happen simply because the solution is a permutation of [1,2,3,4,5,6,7,8]. so something like [1,1,3,4,5,6,7,8] never happens and thats enough to check diagonals.

I hope it solved the problem.

p.s. note that Y1 is the Y coordinate of the head of the Others from the rule Safe/1. so it is a queen with a Xdist of 1 at first, then it backtracks to other rows.

clarification

we are talking about noattack/3. you give it three arguments:

first: Y coordinate of current queen,

second: a right-most list [Y1| Ylist] the begins somewhere after where Y is in the list, and continues to the end of the primary list.(yes this is a sublist of the solution), and

third: Xdist is the index-distance between current queen (which has Y) and the queen which is gonna be checked with the current queen (which has Y1 and is the head of second argument).

third argument is necessary because without it we can not check diagonal interaction between the current queen and and the queen which has Y1. it is really basic mathematics, you have 2 points in the coordinate system with only natural numbers. lets say these 2 points attack each other in a diagonal way if and only-if abs(x1 - x2) = abs(y1 - y2).

Example #1 . and if you understood my explanations well, check it as Accepted.

P1 = (3, 4) and P2 = (1, 2) --> these points have a diagonal attack because abs(3-1) = abs(4-2) = 2

Example #2

P1 = (3, 4) and P2 = (7, 0) --> these points have a diagonal attack because abs(3-7) = abs(4-0) = 4

this is why we check both Y1-Y =\= Xdist and Y-Y1 =\= Xdist . because whenever there is a diagonal attack at least one of them is gonna be true. when non of them was true, it means that there is no diagonal attack between the queen with Y and the queen with Y1. so we can proceed to checking the next queen which is the head of Ylist.

I hope that's enough. this is a very easy problem, Just read it carefully and if you couldn't understand again try to trace the algorithm on a piece of paper yourself. that's a way always works.

Answer 2

I have the same confusion when solving the same problem in recursion using C. There are two possible directions for diagonal attacks. Number each square with x,y coordinates with top-left being 0,0. You will then see that these two attacking diagonal detection or calculation satisfies the conditions:

• x1 - y1 == x2 - y2
• x1 + y1 == x2 + y2

I annotated the comparison above in C equality notation and not Prolog notation. Between two points (x1,y1) and (x2,y2), there is queen diagonal attack if one of conditions above is meet.