ESIEE-Paris Projet de la Programmation Logigue en Prolog

ESIEE-Paris

Projet de Programmation Logigue

Professeur du Matiere : René Natowicz

Travail du

BLERIOT Sebestian
LEOW Chee Kiong

Bibliographie :

Sterling and Shapiro - The Art of Prolog

Ivan Bratko - Prolog for AI

DRAFTED by Leow Chee Kiong

( Une traduction completement en Français est disponible)

Outil pour les Programs

We will start by introducing some utitlity predicates that we will use for most of the programs.

Listing pour UTIL.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

conventions:

The predicate are represented in the following form:

myPredicate( +N, -R, ?V)

following some de facto convention

the parameter terms are prefix with either '+','-' or '?'.

'+'means that the term is an input --- it should be bind to a value.

'-'means that the term is an output --- it should be a variable.

'?'means that it can be either input or output.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% delone( +X, ?L, ?Ls)

%Ls is the remainder of the list L with one X removed.

%Ls est la reste de la liste L avec X enlevee.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

delone( X, [X|Tail], Tail).

delone( X, [Y|Tail], [Y|Tailp]) :-

delone( X, Tail, Tailp).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% insert( +X, ?List, ?BiggerList)

%BiggerList is the result of inserting X into List.

%X may be inserted into any position in List.

%BiggerList est le resultat apres la insertion de X

%en List. X peut etre inserer dans tous les position

%de List.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

insert( X, List, BiggerList) :-

delone( X, BiggerList, List).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% permutation( +L, ?R)

%R is a permutation of the list L

%R est une permutation de la liste L

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

permutation([],[]) :- !.

permutation( [X|L], P) :-

permutation( L, Lp),

insert( X, Lp, P).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% couple( ?L1, ?L2, ?R)

%L1 - [X1,X2,X3,...,XN]

%L2 - [Y1,Y2,Y3,...,YN]

%R- [(X1,Y1),(X2,Y2),...,(XN,YN)]

%if L1,L2 inputs, R is the output

%if R is the input, L1 and L2 are the outputs

%soit L1,L2 entrees, R est la sortie

%soit R entree, L1 et L2 sont les sorties

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

couple( [], [], []).

couple( [X|L1], [Y|L2], [(X,Y)|C]) :-

couple( L1, L2, C).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% naturels( +N, -L)

%L is the list of natural numbers from 0 to N-1

%L est une liste de nombre naturel de 0 a N-1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

naturels( 0, []).

naturels( N, L) :- N1 is N-1, N1 >= 0, naturels( N1, L1), append(L1,[N1],L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% selectNumber( -K, +N)

%K is a number from 0 to (N-1).

%K est un numero appartinant de 0 a (N-1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

selectNumber( K, N) :- naturels( N, L), member( K, L).
Diagonals Coordinates

To determines if two queens are onthe same diagonals we look at their diagonal coordinates defined in the figures below:

	1	2	3	4
1	2	3	4	5
2	3	4	5	6
3	4	5	6	7
4	5	6	7	8

Y+X diagonal

	1	2	3	4
1	0	-1	-2	-3
2	1	0	-1	-2
3	2	1	0	-1
4	3	2	1	0

Y-X diagonal

Générer un placement puis tester

Strategy GAT - Generate And Test

Our approche here as well as in the following questions is to try to cast the problem into a general case and its boundary case. For our first naive attempt to the problem, we will generate complete placements and then test them for stability. As each placement are generated entirely before it is tested, the program is not able to profit from early pruning of the state tree. As we will see, to generate all possible solutions the program will basically generate all possible permutation of the queens placement – an enormous amount.

Time taken to generate the first solution for a 12 x 12 checker:

?- time(solution(12,C)).

% 14,482,299 inferences in 46.36 seconds (312410 Lips)

Time taken to generate all the solutions for a 8 x 8 checker :

?- time(bagof(P,solution(8,P),S)).

% 1,721,407 inferences in 5.55 seconds (310276 Lips)

Testing for complete solutions for 10 x 10 took more than several minutes. For the time being the author will not conduct test that last for more than several minutes. The impôrtant indication is actually the number of inferences – the time is machine dependant.

Size inferences

4 x 4 568

6 x 6 24,146

8 x 8 1,721,407

We deduce that the complexity should be in the order of Cⁿ_k , where n = N*N the size of the checker and k = N. However the the actual complexity should be slightly lower as program does not generate placement on the same line or same column, i.e. each x and each y only occurs once.

Following is the listing for the program GAT.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Q1 GAT – Generate And Test

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% load the predicates in util.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- consult(util).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% stable( +L )

%L = [(x1,y1),(x2,y2),...]

%L is a list representing the positions of the queens on the checker.

%L is stable if non of the queens attack any other queen.

%L est une liste representant les positions des reines sur l'echiquier.

%L est stable si tous les reines ne prennent pas aucune des autre.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Boundary case:

%L is stable if the checker is empty.

% Cas bornee:

%L est stable si l'echiquier est vide.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

stable( [] ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% General case:

%L = [X|R] is stable if R is stable and X does not attack

%the rest of the queens in R.

% Cas general:

%L = [X|R] est stable si la liste R est stable

%et la reine X ne prendre pas des autres reines en la liste R.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

stable( [X|R] ) :- stable(R), nonprise(X,R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% nonprise( +X, +R)

%X does not attack the queens in the list R.

%la reine X ne prendre pas des reines en la liste R.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

nonprise( _, []).

nonprise( (X,Y), [(Xp,Yp)| Rp] ) :-

X =\= Xp, Y =\= Yp, % colonne et ligne different

Y-Yp =\= X-Xp, % diagonal different

Y-Yp =\= Xp-X,

nonprise( (X,Y), Rp).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Comment on nonprise(..)

% it may be interesting to note that I try to implement nonprise

% iteratively. According to Sterling and Shapiro,

% a Prolog clause is iterative if there is only one

% recursive call in the body and contains only

% system predicates before the recursive call.

% The second argument is equivalent to the accumulator ---

% in this case an accumulating list.

% The interest being that iterative programs are generally

% more efficient than recursive programs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

solution(N,C) :- naturels(N,L), permutation(L,P), couple(L,P,C), stable(C).

Generer un Placement en Testant

Strategy GTP, Generate, Test and Place

Our second strategy consist of generating a solution progressively in a recursive loop. The placement is generated one at a time. Each time verifying that the placement does not attack those already on the checker.

?- time(solution(12,C)).

% 88,757 inferences in 0.33 seconds (268961 Lips)

Compared with the previous solution, the complexity have been greatly reduced.

?- time(bagof( P, solution( 8,P), S)).

% 339,072 inferences in 1.21 seconds (280225 Lips)

Size inferences

4 x 4 861

6 x 6 15,789

8 x 8 339,072

10 x 10 8,785,346

The number of inference for a 4x4 checker is greater, but for all subsequent greater checker the complexity has been reduced. However the order of complexity is still exponential.

Listing of GTP.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Q2 GTP – Generate, Test and Place

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- consult(util).

% Predicate solution( +N, ?S)

solution( N, S) :- stable( S, N, N).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Predicate stable( ?S, +K, +N)

% declarative meaning of predicate <stable> :

% The state K represented by the list S of K numbers of queens

% in a N x N checker is stable if:

% the (K-1)th state is stable and

% the queen (Ax,Ay) does not attack the queens in the list R.

%OR

% the checker is empty of queens.

% The former is the general case and the later the trivial "boundary" case.

% interpretation de predicate <stable> :

% l'etat K representer par la liste S de K nombres de reines dans

% un echiquier de taille N x N est stable si:

% l'etat K-1 est stable et

% la reine (Ax,Ay) ne prendre pas des reine en la liste R.

%OU

% L'echiquier est videe de reines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

stable( [], 0, _ ).

stable( [(Ax,Ay)|R], K, N ) :-

K1 is K-1, K1 >= 0,

stable( R, K1, N),

Ax is N-K,

selectNumber( Ay, N),

nonprise((Ax,Ay),R).

nonprise( _, []).

nonprise( (X,Y), [(Xp,Yp)| Rp] ) :-

X =\= Xp, Y =\= Yp, % colonne et ligne different

Y-Yp =\= X-Xp, % diagonal different

Y-Yp =\= Xp-X,

nonprise( (X,Y), Rp).

Generer les Contraintes puis Placer

Strategy GCP, Generate Constraint and Place

Personally I’m not very comfortable with this questions. I will explain later, but this is my first approach. Later I’ll present the second approach.

For pedagogical reason assuming that we wish to define the constraint specify in nonprise before selecting a position for our queen.

For example :

ajoutReineG( Eb, Ef, K, N) :-

Kp is K+1, Kp =< N, Ax = K,

nonprise( (Ax,Ay), Eb),

selectNumber( Ay, N),

ajoutReineG( [(Ax,Ay)|Eb], Ef, Kp, N).

The declarative meaning is correct but we will encounter a problem here as the y position of the queen (Ay) is not instantiated yet. Prolog will report an insufficiently instantiated variable. This shows that the procedural

aspect of Prolog cannot be ignored. Its somewhat painful as it requires that we understand how Prolog works.

To overcome this problem we can carry out the prove under the meta-predicate <dg> - which does what is call demonstration sous gel conditionel. Under <dg> we may freeze a goal until its variables have been instantialised.

The implementation is however not seamless and I consider it to be “Ugly”.

The following version of ajoutReine freeze nonprise until Ay is instantialised.

:- consult(freeze).

solutionG( N, S) :- dg(ajoutReineG( [], S, 0, N)).

ajoutReineG( Ef, Ef, N, N).

ajoutReineG( Eb, Ef, K, N) :-

Kp is K+1, Kp =< N, Ax = K,

geler(Ay,nonprise( (Ax,Ay), Eb)),

selectNumber( Ay, N),

ajoutReine( [(Ax,Ay)|Eb], Ef, Kp, N).

The predicate nonprise used here is the same as the one defined in the question before. The implementation for dg(…) is in the appendix. Now, lets talk about he second approach.Assume that we have the following predicates

reines( L, N)

Which will generate a list L of N queens. Assume also that we have the following predicate

stable( L, N)

Which is true if L is a list of N non-attacking queens. We can define our solution as

solution( L, N) :- reines(L, N), stable(L, N).

This however is equivalent to our first naïve solution. Essentially generating all possible combination and then testing them all. Now consider the following

solution(L, N) :- stable(L, N), reines(L, N).

Which should defines the constraint for stability before the generation of the placement. Which will not work as we cannot determine the stability of L before its generation. So lets say we make use of our dg(…).

solutionG( N,C) :- dg( solu( C,N)).

solu(L,N) :- stableG( L, N), reines( L, N).

Voila ! The listing for GCP.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Q3 GCP – Generate Constraints and Place

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- consult(util).

:- consult(freeze).

nonprise( _, []).

nonprise( (X,Y), [(Xp,Yp)| Rp] ) :-

% colonne et ligne different

geler(X, geler(Xp, X =\= Xp)),geler(Y, geler(Yp, Y =\= Yp)),

% diagonal different

geler(X, geler(Xp, geler(Y, geler(Yp, Y-Yp =\= X-Xp)))),

geler(X, geler(Xp, geler(Y, geler(Yp, Y-Yp =\= Xp-X)))),

nonprise( (X,Y), Rp).

solutionG( N,C) :- dg( solu( C,N)).

solu(L,N) :- stableG( L, N), reines( L, N).

stableG([],_).

stableG( [_], _).

stableG( [X,Y|Xs], N) :- nonprise( X,[Y|Xs]) ,stableG( [Y|Xs], N).

reines( C, N) :- naturels(N,L), permutation(L,P), couple(L,P,C).

Reduction des Domaines

Strategy RD, Reduction of Domains

Here we make use of a powerful technique which is widely applied for programming in Prolog. The performance is superior to the previous methods. For the first solution as well as all solutions there is a 3 fold reduction in inferences.

?- time(solution(12,S)).

% 25,243 inferences in 0.17 seconds (148488 Lips)

?- time(bagof(P,solution(8,P),S)).

% 122,520 inferences in 0.55 seconds (222764 Lips)

For the first time, we were able to compute all solutions for 12 x 12 within a reasonable time.

?- time(bagof(P,solution(12,P),S)).

% 57,667,834 inferences in 289.02 seconds (199529 Lips)

Size Inferences

4 x 4 695

6 x 6 8,642

8 x 8 122,520

10 x 10 2,308,453

12 x 12 57,667,834

The listing for RD.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

% Q4. Solution par reduction de Domaines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

:- consult(util).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

% Predicate genDomaines( +N, -L) <-

%L = [d( K1, C1), d(K2, C2), ..., d(KN, CN)]

% We uses an iterative construct for genDomaines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

genDomaines( N, R) :- naturels( N, C), genDomaines( N, C, [], R).

genDomaines( 0, _, R, R).

genDomaines( N, C, L, R) :-

Np is N-1, Np >= 0,

genDomaines( Np, C, [d(Np,C)|L], R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

% Predicate reduit( d(Ka,[Xa]), d(Kb,Cb), R) <-

%R est le domaine reduit de d(Kb,Cb) par la placement (Ka,Xa).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

reduit( d(Ka,[Xa]), d(Kb,Cb), d(Kb,Co)) :-

% supprimer les colonne identique a Xa

delete( Cb, Xa, C1),

% supprimer les colonne diagonal incompatible

reduitD( Ka + Xa, Kb, C1, [], C2),

reduitD( Ka - Xa, Kb, C2, [], Co),

Co \== [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% reduitD( +M, +Kb, +Cin, [], -Cout)

%This is a tricky predicates !

%The first parameter act as a mould - K+X or K-X.

%Kb is the row which we want to produce the compatible

%domain (which are columns in row Kb).

%Cin is the input domain to be process

%The last two parameters function as an accumulating mechanism

%The result is copy to Cout by the boundary predicate below

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitD( _, _, [], Rf, Rf) :- !.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Remove columns on the same Y+X Diagonal

%Enlever col incompatible par rapport au Y+X diagonal

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitD( Ka + Xa, Kb, [X|C], R, Rf) :-

Ka + Xa =:= Kb+X, !, reduitD( Ka + Xa, Kb, C, R, Rf).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Remove columns on the same Y-X Diagonal

%Enlever col incompatible par rapport au Y-X diagonal

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitD( Ka - Xa, Kb, [X|C], R, Rf) :-

Ka - Xa =:= Kb-X, !, reduitD( Ka - Xa, Kb, C, R, Rf).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Compatible cases come here

%traitment des case compatible

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitD( N, Kb, [X|C], R, Rf) :-

append( R, [X], Rp), reduitD( N, Kb, C, Rp, Rf).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% reduitList( +L, -R) <-

%En utilisant la premiere placement reduire les domaines des reines

%suivants.

% entree:

%L est une liste de la forme [ d( y1,[x1]), d( y2, c2), ..., d( yn,cn)]

%ou (y1,x1) est la placement d'une reine

% et ck est la domaine de la yk reine.

% sortie:

%R est la liste de la premiere placement et les domaines reduits

%des reines suivants.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

reduitList( [_],[_]) :- !.

reduitList( [Ja,Jb|La], [Ja,Jo|R]) :-

reduit( Ja, Jb, Jo),

reduitList( [Ja|La], [Ja|R]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% placerReduire( +L, -R) <-

%generer une placement de la premiere domaine de la liste L

%et reduire les domaines des reines suivant avec celle-ci.

%Le resultat est mettre en R.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

placerReduire( [d(Ka,Ca)|La], R) :-

member( Xa, Ca), reduitList( [d(Ka,[Xa])|La], R).

placerTous( 1, R, R) :- !.

placerTous( N, D, [X|R]) :-

Np is N-1, Np >= 0,

placerReduire( D, [X|Xs]),

placerTous( Np, Xs, R).

solution( N, P) :- genDomaines( N, D), placerTous( N, D, P).

Réduction des Domaines avec Vérification de 2-Compatibilité

Strategy RDC.

Here we try to crop the tree by testing for the condition of 2-compatibility. The definition of 2-Compatibility is defined as follow:

Two domains Da and Db are compatible if

There exist Ra and Rb, where Ra an element of Da and Rb an element of Db,

such that:

Ra and Rb does not attack each other.

However in practice we are not able to show that we can make use of this criteria to provide early cropping of the solution tree. In our implementation, the additional processing actually reduce the performance. It will be interesting to see if our colleague manage to harness this property.

Some timing for comparison:

First solution:

?- time(solution(12,S)).

% 86,384 inferences in 0.33 seconds (261770 Lips)

All solutions:

?- time(bagof(P,solution(10,P),S)).

% 4,354,430 inferences in 17.64 seconds (246850 Lips)

?- time(bagof(P,solution(12,P),S)).

% 122,709,956 inferences in 518.94 seconds (236463 Lips)

Size Inferences

4 x 4 897

6 x 6 12,355

8 x 8 206,818

10 x 10 4,354,430

12 x 12 122,709,956

Listing for RDC.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Q5. Solution par reduction de Domaines et verification

%de 2-compatibilite.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- consult(util).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Predicate compatible( Da, Db) <-

%Domaine Da and Db sont compatible.

% Da and Db sont compatible si

%exist element Ra de Da

%exist element Rb de Db

% Tel que Ra et Rb sont non prise.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

compatible( d(Y1,D1), d(Y2,D2)) :-

member(X1,D1),

member(X2,D2),

nonprise((Y1,X1),(Y2,X2)),

compatibleList( _, []).

compatibleList( d(Ya,Da), [d(Yb,Db) | L]) :-

compatible( d(Ya,Da), d(Yb,Db) ),

compatibleList( d(Ya,Da), L),

compatibleList( d(Yb,Db), L).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% nonprise( (X1,Y1), (X2,Y2)) <-

%la reine (X1,Y1) ne prendre pas la reine (X2,Y2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

nonprise( (Xa,Ya), (Xb,Yb)) :-

Xa =\= Xb, Ya =\= Yb, % colonne et ligne different

Ya-Yb =\= Xa-Xb, % diagonal different

Ya-Yb =\= Xb-Xa.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% gendomaines( +N, -R) <-

%gendomaines/2 est un wrapper pour gendomaines/4 definit ci-dessous.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

genDomaines( N, R) :- naturels( N, C), genDomaines( N, C, [], R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Predicate genDomaines( +N, +C, +L, -R) <-

%R = [d( K1, C1), d(K2, C2), ..., d(KN, CN)]

% We uses an iterative construct for genDomaines/4.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

genDomaines( 0, _, R, R).

genDomaines( N, C, L, R) :-

Np is N-1, Np >= 0,

genDomaines( Np, C, [d(Np,C)|L], R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Predicate reduit( d(Ka,[Xa]), d(Kb,Cb), R)

%R est le domaine reduit de d(Kb,Cb) par la placement (Ka,Xa).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduit( d(Ka,[Xa]), d(Kb,Cb), d(Kb,Co)) :-

delete( Cb, Xa, C1),% supprimer les colonne identique a Ca

reduitD( Ka + Xa, Kb, C1, [], C2), % supprimer les colonne diagonal incompatible

reduitD( Ka - Xa, Kb, C2, [], Co),

Co \== [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Commentaire comme pour le question avant

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitD( _, _, [], Rf, Rf) :- !.

reduitD( Ka + Xa, Kb, [X|C], R, Rf) :-

Ka + Xa =:= Kb+X, !, reduitD( Ka + Xa, Kb, C, R, Rf).

reduitD( Ka - Xa, Kb, [X|C], R, Rf) :-

Ka - Xa =:= Kb-X, !, reduitD( Ka - Xa, Kb, C, R, Rf).

reduitD( N, Kb, [X|C], R, Rf) :-

append( R, [X], Rp), reduitD( N, Kb, C, Rp, Rf).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Commentaire comme pour le question avant

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitList( [_],[_]) :- !.

reduitList( [Ja,Jb|La], [Ja,Jo|R]) :-

reduit( Ja, Jb, Jo),

reduitList( [Ja|La], [Ja|R]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%placerReduire( +L, -R)

%generer une placement de la premiere domaine de la liste L

%et reduire les domaines des reines suivant avec celle-ci.

%Le resultat est mettre en R.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

placerReduire( [d(Ka,Ca)|La], R) :-

member( Xa, Ca), reduitList( [d(Ka,[Xa])|La], R).

placerTousComp( 1, R, R) :- !.

placerTousComp( N, D, [X1|R]) :-

Np is N-1, Np >= 0,

placerReduire( D, [X1,X2|Xs]),

compatibleList( X2, Xs),

placerTousComp( Np, [X2|Xs], R).

solution( N, P):- genDomaines( N, D), placerTousComp( N, D, P).

Solution par reduction de Domaines et placement heuristique.

Strategy RDH, Reduction of Domain with Heuristique.

Here we use the size of the domains as the heuristique. We were able to get slightly better timing for the first solution as well as for all solutions for checker of size superior of 6x6. For 6x6 and smaller size checker, the processing time was actually longer as the benefit could not offset the additional processing required. We deduce that this method is the best of the lot and the gain increases with the size of the checker.

First solution:

?- time(solution(12,S)).

% 24,550 inferences in 0.11 seconds (223182 Lips)

All solutions:

?- time(bagof(P,solution(12,P),S)).

% 46,046,094 inferences in 243.32 seconds (189241 Lips)

Size Inferences

4 x 4 751

6 x 6 8,873

8 x 8 117,732

10 x 10 2,011,205

12 x 12 46,046,094

Listing for RDH.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Solution par reduction de Domaines et placement heuristique.

% Placement-Reduction dans l'ordre croissant des

% tailles des domaines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- consult(util).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Predicate genDomaines( +N, -L) <-

%L = [d( N, K1, C1), d( N, K2, C2), ..., d( N, KN, CN)]

% genDomaines/2 is a wrapper predicate for genDomaines/5

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

genDomainesT( N, R) :- naturels( N, C), genDomainesT( N, N, C, [], R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Predicate genDomaines( +T, +N, +C, +L, -R) <-

%R = [d( T, K1, C1), d( T, K2, C2), ..., d( T, KN, CN)]

% We uses an iterative construct for genDomaines/5.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

genDomainesT( _, 0, _, R, R).

genDomainesT( T, N, C, L, R) :-

Np is N-1, Np >= 0,

genDomainesT( T, Np, C, [d(T,Np,C)|L], R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Predicate reduitT( d(Ta, Ka,[Xa]), d( Tb, Kb, Cb), R) <-

%R est le domaine reduit de d(Kb,Cb) par la placement (Ka,Xa).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitT( d(1,Ka,[Xa]), d(Tb,Kb,Cb), d(To,Kb,Co)) :-

% supprimer les colonne identique a Ca

delete( Cb, Xa, C1),

% supprimer les colonne diagonal incompatible

reduitD( Ka + Xa, Kb, C1, [], C2),

reduitD( Ka - Xa, Kb, C2, [], Co),

Co \== [], length( Co, To).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Commentaire pour reduitD comme dans la question avant

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitD( _, _, [], Rf, Rf) :- !.

reduitD( Ka + Xa, Kb, [X|C], R, Rf) :-

Ka + Xa =:= Kb+X, !, reduitD( Ka + Xa, Kb, C, R, Rf).

reduitD( Ka - Xa, Kb, [X|C], R, Rf) :-

Ka - Xa =:= Kb-X, !, reduitD( Ka - Xa, Kb, C, R, Rf).

reduitD( N, Kb, [X|C], R, Rf) :-

append( R, [X], Rp), reduitD( N, Kb, C, Rp, Rf).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% reduitList( +L, -R) <-

%Use the 1st queen in the list L to reduce the domains of the

%remaining queens in the list.

%Utilise la premiere reine en la liste L pour reduire les domaines

%des reines suivants.

% entree:

%L est une liste de la forme [ d( y1,[x1]), d( y2, c2), ..., d( yn, cn)]

%ou (y1,x1) est la placement d'une reine

%et ck est la domaine de la yk reine.

% sortie:

%R est la liste de la premiere placement et les domaines reduits

%des reines suivants.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

reduitListT( [_],[_]) :- !.

reduitListT( [Ja,Jb|La], [Ja,Jo|R]) :-

reduitT( Ja, Jb, Jo),

reduitListT( [Ja|La], [Ja|R]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%placerReduire( +L, -R)

%generer une placement de la premiere domaine de la liste L

%et reduire les domaines des reines suivant avec celle-ci.

%Le resultat est mettre en R.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

placerReduireT( [d(Ta,Ka,Ca)|La], R) :-

member( Xa, Ca), reduitListT( [d(1,Ka,[Xa])|La], R).

placerTousT( 1, R, R) :- !.

placerTousT( N, D, [X|R]) :-

Np is N-1, Np >= 0,

placerReduireT( D, [X|Xs]),

sort( Xs, Xp),

placerTousT( Np, Xp, R).

solution( N, P) :-

genDomainesT( N, D), placerTousT( N, D, Pp), sort(Pp, P).

Comparison of Strategy

Size / Strategy	Q6. RD with Heuristique	Q4. RD	Q5. RD with 2-comp	Q2. GTP	Q1. GAT
4 x 4	751	695	897	861	568
6 x 6	8,873	8,642	12,355	15,789	24,146
8 x 8	117,732	122,520	206,818	339,072	1,721,407
10 x 10	2,011,205	2,308,453	4,354,430	8,785,346	-
12 x 12	46,046,094	57,667,834	122,709,956	-	-

Demonstration sous gel conditionnel

Listing of FREEZE.pl

/**************************************

mars 2001

Meta-predicate dg(..) et geler(V,B)

Demonstration sous gel conditionel

To give us the capacity to handle delayed instantialisation

using freeze or geler we define the meta-predicate < dg >.

The definition was provided by M. Rene Natowicz (ESIEE).

To get an insight into the problem read

[Sterling and Shapiro - The Art of Prolog],

in particular section 10.3 Variable as Objects.

Sterling and Shapiro propose two additional system

predicates freeze and melt which is not implemented

in SWI prolog.

To read also Nakashima and Ueda (1984) for implementation in Prolog 10

and also Colmerauer (1982) for geler.

************************************** */

dg(B) :- dg(B,true,true).

dg(true,Gb,Gb) :- !.

dg((B1,Bs),Gb,Ga) :- !, dg(B1,Gb,G), dg(Bs,G,Ga).

/***************************************

if B is a built-in predicates

prove B,

melt some goal D from the frozen stack Gb,

prove this goal D.

***************************************/

dg(B,Gb,Ga) :- predicate_property(B, built_in), !,

degeler(Gb,Gr,D),

dg(D,Gr,Ga).

/***************************************

if the goal is geler(V,B) and V is a free variable then

push geler(V,B) into the Ga stack.

else

prove B.

***************************************/

dg(geler(V,B),Gb,Ga) :- var(V),!,push(geler(V,B),Gb,Ga).

dg(geler(V,B),Gb,Ga) :- nonvar(V),!, dg(B,Gb,Ga).

/***************************************

if goal B is neither a built-in predicates or geler(V,B) then

get the body --- Corps --- for B

don't understand ...

***************************************/

dg(B,Gb,Ga) :- clause( B, Corps),

degeler(Gb,Gr,D), dg(D,Gr,G),

dg(Corps,G,Ga).

push(B,Pile,(B,Pile)).

/*******************************************

degeler( +G, -Gr, -D) <- D is the list of goals that can be melted from the

the list G of frozen goals. Gr is the result after removing the melted goals D from G.

G is the stack containing the list of frozen goals --- (geler(V1,B1),geler(V2,B2),...,true).

Gr is the output resulting from the removal of terms that can be unfrozen (melted) during this call to degeler.

D are the list of B? that have been melted. It is of the form (B1,B3,...,true).

*******************************************/

degeler(G,Gr,D) :- d(G,Gr,D,true).

d(true,true,D,D) :- !.

d((geler(V,B),G),(geler(V,B),Gr), D, D1) :- var(V), !, d(G,Gr,D,D1).

d((geler(V,B),G),Gr, D, D1) :- d( G, Gr, D, (B,D1)).

Bibliographie :

Générer un placement puis tester

Generer les Contraintes puis Placer

Reduction des Domaines

Size Inferences

Réduction des Domaines avec Vérification de 2-Compatibilité

Size Inferences

Solution par reduction de Domaines et placement heuristique.

Size Inferences

Comparison of Strategy

Size / Strategy

Q6. RD with Heuristique

Q4. RD

Q5. RD with 2-comp

Q2. GTP

Q1. GAT

Demonstration sous gel conditionnel