ESIEEParis
Projet de Programmation Logigue
Professeur du Matiere : René Natowicz
Travail du
BLERIOT Sebestian
LEOW Chee Kiong
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, [XTail], Tail).
delone( X, [YTail], [YTailp]) :
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( [XL], 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( [XL1], [YL2], [(X,Y)C]) :
couple( L1, L2, C).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% naturels( +N, L)
%
%L is the list of natural numbers from 0 to N1
%
%L est une liste de nombre naturel de 0 a N1
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
naturels( 0, []).
naturels( N, L) : N1 is N1, N1 >= 0, naturels( N1, L1), append(L1,[N1],L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% selectNumber( K, +N)
%
%K is a number from 0 to (N1).
%
%K est un numero appartinant de 0 a (N1).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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 

1 
2 
3 
4 
1 
0 
1 
2 
3 
2 
1 
0 
1 
2 
3 
2 
1 
0 
1 
4 
3 
2 
1 
0 
YX diagonal
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^{n}_{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 = [XR] is stable if R is stable and X does not attack
%the rest of the queens in R.
%
% Cas general:
%
%L = [XR] est stable si la liste R est stable
%et la reine X ne prendre pas des autres reines en la liste R.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
stable( [XR] ) : 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
YYp =\= XXp, % diagonal different
YYp =\= XpX,
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).
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 (K1)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 K1 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 K1, K1 >= 0,
stable( R, K1, N),
Ax is NK,
selectNumber( Ay, N),
nonprise((Ax,Ay),R).
nonprise( _, []).
nonprise( (X,Y), [(Xp,Yp) Rp] ) :
X =\= Xp, Y =\= Yp, % colonne et ligne different
YYp =\= XXp, % diagonal different
YYp =\= XpX,
nonprise( (X,Y), Rp).
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 metapredicate <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 nonattacking 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, YYp =\= XXp)))),
geler(X, geler(Xp, geler(Y, geler(Yp, YYp =\= XpX)))),
nonprise( (X,Y), Rp).
solutionG( N,C) : dg( solu( C,N)).
solu(L,N) : stableG( L, N), reines( L, N).
stableG([],_).
stableG( [_], _).
stableG( [X,YXs], N) : nonprise( X,[YXs]) ,stableG( [YXs], N).
reines( C, N) : naturels(N,L), permutation(L,P), couple(L,P,C).
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)
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 N1, 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 KX.
%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, [XC], R, Rf) :
Ka + Xa =:= Kb+X, !, reduitD( Ka + Xa, Kb, C, R, Rf).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Remove columns on the same YX Diagonal
%Enlever col incompatible par rapport au YX diagonal
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
reduitD( Ka  Xa, Kb, [XC], R, Rf) :
Ka  Xa =:= KbX, !, reduitD( Ka  Xa, Kb, C, R, Rf).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Compatible cases come here
%traitment des case compatible
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
reduitD( N, Kb, [XC], 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,JbLa], [Ja,JoR]) :
reduit( Ja, Jb, Jo),
reduitList( [JaLa], [JaR]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% placerReduire( +L, R) <
%generer une placement de la premiere domaine de la liste L
%et reduire les domaines des reines suivant avec celleci.
%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, [XR]) :
Np is N1, Np >= 0,
placerReduire( D, [XXs]),
placerTous( Np, Xs, R).
solution( N, P) : genDomaines( N, D), placerTous( N, D, P).
Strategy RDC.
Here we try to crop the tree by testing for the condition of 2compatibility. The definition of 2Compatibility 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)
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 2compatibilite.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
: 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
YaYb =\= XaXb, % diagonal different
YaYb =\= XbXa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% gendomaines( +N, R) <
%
%gendomaines/2 est un wrapper pour gendomaines/4 definit cidessous.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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 N1, 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, [XC], R, Rf) :
Ka + Xa =:= Kb+X, !, reduitD( Ka + Xa, Kb, C, R, Rf).
reduitD( Ka  Xa, Kb, [XC], R, Rf) :
Ka  Xa =:= KbX, !, reduitD( Ka  Xa, Kb, C, R, Rf).
reduitD( N, Kb, [XC], R, Rf) :
append( R, [X], Rp), reduitD( N, Kb, C, Rp, Rf).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Commentaire comme pour le question avant
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
reduitList( [_],[_]) : !.
reduitList( [Ja,JbLa], [Ja,JoR]) :
reduit( Ja, Jb, Jo),
reduitList( [JaLa], [JaR]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%placerReduire( +L, R)
%
%generer une placement de la premiere domaine de la liste L
%et reduire les domaines des reines suivant avec celleci.
%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, [X1R]) :
Np is N1, Np >= 0,
placerReduire( D, [X1,X2Xs]),
compatibleList( X2, Xs),
placerTousComp( Np, [X2Xs], R).
solution( N, P): genDomaines( N, D), placerTousComp( N, D, P).
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)
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.
%
% PlacementReduction 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 N1, 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, [XC], R, Rf) :
Ka + Xa =:= Kb+X, !, reduitD( Ka + Xa, Kb, C, R, Rf).
reduitD( Ka  Xa, Kb, [XC], R, Rf) :
Ka  Xa =:= KbX, !, reduitD( Ka  Xa, Kb, C, R, Rf).
reduitD( N, Kb, [XC], 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,JbLa], [Ja,JoR]) :
reduitT( Ja, Jb, Jo),
reduitListT( [JaLa], [JaR]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%placerReduire( +L, R)
%
%generer une placement de la premiere domaine de la liste L
%et reduire les domaines des reines suivant avec celleci.
%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, [XR]) :
Np is N1, Np >= 0,
placerReduireT( D, [XXs]),
sort( Xs, Xp),
placerTousT( Np, Xp, R).
solution( N, P) :
genDomainesT( N, D), placerTousT( N, D, Pp), sort(Pp, P).
Size / Strategy 
Q6. RD with Heuristique 
Q4. RD 
Q5. RD with 2comp 
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 
 
 
Listing of FREEZE.pl
/**************************************
mars 2001
Metapredicate 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 metapredicate < 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 builtin 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), !,
B,
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 builtin 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)).