Go backward to Natural Language Analysis
Go up to Top
Go forward to Introduction to functional programming and ML

Generate and Test

The general idea is to begin with a characterization of what a solution looks like, and try to push this well-formedness test on candidate solutions as far as possible into the generator: 

find(X) :- generate(X), test(X).

n-queens

Here is the code for the n-queens problem that we discussed in class. The predicate queens/2 is the solution shown in The Art of Prolog on page 253, while qqueens/2 is the solution shown in The Art of Prolog on page 255. I have added several write/1 goals to show what is going on. Take them for a spin! queens(8,A) finds the first solution in about 12 seconds, while qqueens(8,A) finds the first solution in less than 1 second (probably about 0.5 seconds). 

permutation(Xs,[Z|Zs]) :-                             range(M,N,[M|Ns]) :-
        select(Z,Xs,Ys),                                      M < N,      
        permutation(Ys,Zs).                                   M1 is M + 1,   
permutation([],[]).                                           range(M1,N,Ns).
                                                      range(N,N,[N]). 
select(X,[X|Xs],Xs).                                                  
select(X,[Y|Ys],[Y|Zs]) :-                                           
        select(X,Ys,Zs).                                                         
                                                                  
queens(N,Qs) :-                                       qqueens(N,Qs) :-                   
        range(1,N,Ns),                                        range(1,N,Ns),                
        permutation(Ns,Qs),                                   qqueens(Ns,[],Qs),            
        nl,nl,                                                nl,write('Found a solution!'),
        write('Generated a potential solution: '),            nl.                         
        write(Qs),                                                                          
        nl,                                           qqueens(UnplacedQs,SafeQs,Qs) :-      
        write('Testing if actual solution.'),                 nl,                           
        safe(Qs),                                             nl,write('Unplaced queens: '),
        nl,write('Found a solution!'),nl.                     write(UnplacedQs),            
                                                              nl,write('    Safe queens: '),
safe([Q|Qs]) :-                                               write(SafeQs),                
        safe(Qs),                                             select(Q,UnplacedQs,UnplacedQs1),
        \+ attack(Q,Qs).                                      nl,nl,                         
safe([]).                                                     write('        Trying queen '),
                                                              write(Q),                      
attack(X,Xs) :-                                               \+ attack(Q,SafeQs),           
        attack(X,1,Xs).                                       nl,nl,write('        Queen '), 
                                                              write(Q),write(' is safe.'),   
attack(X,N,[Y|Ys]) :-                                         qqueens(UnplacedQs1,[Q|SafeQs],Qs).
        X is Y+N,
        nl,write('  Not safe: '),                     qqueens([],Qs,Qs).
        write(X),write(' attacks '),write(Y).
attack(X,N,[Y|Ys]) :-
        X is Y-N,
        nl,write('  Not safe: '),
        write(X),write(' attacks '),write(Y).
attack(X,N,[Y|Ys]) :-
        N1 is N+1,
        attack(X,N1,Ys).
horsch@cs.ubc.ca

Go backward to Natural Language Analysis
Go up to Top
Go forward to Introduction to functional programming and ML