I implemented the N-queen problem with SWI Prolog , but I want to optimize the choice of queen, so it will be more efficient. Here is my code:
safe(_,[],pos(A,B)).
safe(N,[pos(X,Y)|Rest],pos(A,B)):-
safe(N,Rest,pos(A,B)),
between(1,N,Y),
noattack(pos(X,Y),Rest,pos(A,B)).
noattack(Queen,[],pos(A,B)).
noattack(pos(X,Y),[pos(X1,Y1)|Rest],pos(A,B)):-
X=\=X1, Y=\=Y1, Y1-Y=\=X1-X,Y-Y1=\=X-X1,
A=\=X, B=\=Y, A=\=X1, B=\=Y1, Y-Y1=\=A, X-X1=\=B,
noattack(pos(X,Y),Rest,pos(A,B)).
template(N,L):-
findall(pos(I,_),between(1,N,I),L).
execute(N,N1,L,pos(A,B)):-
template(N1,L),safe(N,L,pos(A,B)).
solution(L):-
write('Please give number N and coordinates for super tower:'), nl,
read(N),
read(pos(A,B)),
N1 is N-2,
execute(N,N1,L,pos(A,B)).
Is there a way to change between(1,N,Y) so the choice of Y will be "more intelligent"?
I think as "low hanging fruit", we can enforce that no two queens are on the same column (given in each generation we determine the position of the next row), by reducing the "domain" dynamically. This means that we (a) will never yield a situation where two queens are on the same column; and (b) we also can gain performance, since we no longer need to check this.
We thus for example can start with a list of possible columns like [1, 2, 3, 4]. If we pick 2 for the first queen, we pass a list [1, 3, 4] to the recursive call, and regardless what the recursive call picks, we know that this can not be the same column. For this we need a predicate that picks an item, and at the same time yields a list where we removed that item, like:
pick_rem([H|T], H, T).
pick_rem([H|T], P, [H|R]) :-
pick_rem(T, P, R).
This then will generate:
?- pick_rem([1,2,3], P, R).
P = 1,
R = [2, 3] ;
P = 2,
R = [1, 3] ;
P = 3,
R = [1, 2] ;
false.
An extra bonus is that if the list is empty, we already know that we reached the end of the board, and thus we found a valid solution. So termination can be checked with simple pattern matching instead of numerical comparisons of an index.
We also need a predicate that generates a range, like:
range(X, Y, []) :-
X > Y.
range(X, Y, [X|T]) :-
X =< Y,
X1 is X + 1,
range(X1, Y, T).
As for checking that the queens do not attack diagonally, we can construct a predicate that takes two numbers and each time updates the two, like:
not_attack([], _, _).
not_attack([H|T], C, D) :-
\+ H is C + D,
\+ H is C - D,
D1 is D+1,
not_attack(T, C, D1).
We thus need to keep track of the positions of the queens, and this in "reverse" order (so the nearest row is the head of that list).
So now we can combine this together in a generate predicate:
gen([], _, []).
gen(Dom, Old, [C|Res]) :-
pick_rem(Dom, C, Dom1),
not_attack(Old, C, 1),
gen(Dom1, [C|Old], Res).
Here the first parameter is the domain that is "shrinking" each recursive call with one element, the second element is a list that is building up with the columns of the queens we put on the board. Finally the last parameter will "construct" the positions of the board.
So now we only need to wrap this predicate with some logic in a more convenient one:
to_pos(R, C, pos(R, C)).
n_queens(N, Sol) :-
range(1, N, Dom),
gen(Dom, [], Res),
maplist(to_pos, Dom, Res, Sol).
This then generates the N-queens solutions for N=4 and N=5 quite efficiently:
?- n_queens(4, S).
S = [pos(1, 2), pos(2, 4), pos(3, 1), pos(4, 3)] ;
S = [pos(1, 3), pos(2, 1), pos(3, 4), pos(4, 2)] ;
false.
?- n_queens(5, S).
S = [pos(1, 1), pos(2, 3), pos(3, 5), pos(4, 2), pos(5, 4)] ;
S = [pos(1, 1), pos(2, 4), pos(3, 2), pos(4, 5), pos(5, 3)] ;
S = [pos(1, 2), pos(2, 4), pos(3, 1), pos(4, 3), pos(5, 5)] ;
S = [pos(1, 2), pos(2, 5), pos(3, 3), pos(4, 1), pos(5, 4)] ;
S = [pos(1, 3), pos(2, 1), pos(3, 4), pos(4, 2), pos(5, 5)] ;
S = [pos(1, 3), pos(2, 5), pos(3, 2), pos(4, 4), pos(5, 1)] ;
S = [pos(1, 4), pos(2, 1), pos(3, 3), pos(4, 5), pos(5, 2)] ;
S = [pos(1, 4), pos(2, 2), pos(3, 5), pos(4, 3), pos(5, 1)] ;
S = [pos(1, 5), pos(2, 2), pos(3, 4), pos(4, 1), pos(5, 3)] ;
S = [pos(1, 5), pos(2, 3), pos(3, 1), pos(4, 4), pos(5, 2)] ;
false.
On my machine, it works quite effective up to N=19. The above is of course not perfect. One can think about some heuristics, etc. to pick better positions, or see in advance that certain patterns will fail. Right now we only stop searching a branch if there is no way to place the queen on the board. But sometimes a combination of some queens can never yield good results later, and such patterns can be added to avoid exhaustively searching the branch.