________________ | | | Q | | |___|___|___|___| | Q | | | | |___|___|___|___| | | | | Q | |___|___|___|___| | | Q | | | |___|___|___|___|
Notice the inclusion of file lists.pro discussed in section 2.6. This is a nice, simple specification that uses 'perm' to generate possible solutions to the puzzle. A sample goal issolve(P) :- perm([1,2,3,4,5,6,7,8],P), combine([1,2,3,4,5,6,7,8],P,S,D), all_diff(S), all_diff(D). combine([X1|X],[Y1|Y],[S1|S],[D1|D]) :- S1 is X1 +Y1, D1 is X1 - Y1, combine(X,Y,S,D). combine(,,,). all_diff([X|Y]) :- \+member(X,Y), all_diff(Y). all_diff([X]).
The last goal reflects the fact that there are 92 distinct solutions to the queens challenge puzzle for an 8x8 board. One inefficiency that this program suffers is that each permutation is completely calculated before it is checked to see whether it represents a solution to the puzzle. It is easy to see that this is not necessary. For example, suppose that a "partial solution" P = [1,3,2, ...] is up for consideration. The row and column calculations show already the "2" is not a safe move! A solution that avoids this inefficiency is considered in section 2.13.?- solve(P). P = [5,2,6,1,7,4,8,3] ; P = [6,3,5,7,1,4,2,8] ; ... ?- setof(P,solve(P),Set), length(Set,L). ... L = 92