scheme-n-queens-optimization-stragegies-sicp-chapter-2

gistfile1.prolog

%% http://stackoverflow.com/questions/17010561/scheme-n-queens-optimization-stragegies-sicp-chapter-2
%%                                                    also: http://ideone.com/5SZx2M
nqueens(N,Qs):- findall(I, between(1,N,I), Dom), 
    length( Ds,N), Ds=[Dom|DZ], append( DZ, [[]], D2s), 
    length( Rs,N), Rs=[[] |RZ], append( RZ, [Qs], R2s),
    maplist( putOne, Ds, D2s, Rs, R2s).

%% D - available picks; R - picks made thus far
putOne(D,D2,R,[Q|R]):- select(Q,D,D2), good(Q,R).

good(Q,RPS):- good(Q,1,RPS). % new queen, reversed partial solution
good(_,_,[]).
good(Q,I,[P|PS]):- Q-I =\= P, Q+I =\= P, I2 is I+1, good(Q,I2,PS).

test(N,LEN):-
    time( (findall( S, nqueens(N,S), R), length(R,LEN)) ).

1 ?- test(8,X).
% 68,786 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 3434355 Lips)
X = 92.

2 ?- test(10,X).
% 1,608,241 inferences, 0.591 CPU in 0.591 seconds (100% CPU, 2721913 Lips)
X = 724.

3 ?- test(11,X).
% 8,579,665 inferences, 3.165 CPU in 3.165 seconds (100% CPU, 2711180 Lips)
X = 2680.

4 ?- test(12,X).
% 49,238,074 inferences, 18.196 CPU in 18.206 seconds (100% CPU, 2705959 Lips)
X = 14200.

5 ?- nqueens(12,S).
S = [4, 9, 7, 2, 11, 6, 12, 10, 8, 5, 3, 1] ;
S = [4, 7, 9, 6, 12, 2, 11, 8, 10, 5, 3, 1] ;
S = [6, 4, 9, 7, 12, 2, 11, 8, 10, 5, 3, 1] ;
S = [6, 9, 7, 2, 4, 12, 10, 8, 11, 5, 3, 1] ;
S = [2, 9, 7, 4, 10, 12, 5, 11, 8, 6, 3, 1]