% Изкуствен интелект, Факултет по математика и информатика, СУ "св. Кл. Охридски"
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% N-queens problem
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variant 1
queens1(S) :-
pattern(S),
solve1(S).
notbeat1(_,[]).
notbeat1(X/Y,[X1/Y1|Rest]) :-
Y =\= Y1, Y1-Y =\= X-X1,
Y1-Y =\= X1-X,
notbeat1(X/Y,Rest).
solve1([]).
solve1([X/Y|Rest]) :-
solve1(Rest),
member(Y,[1,2,3,4,5,6,7,8]),
notbeat1(X/Y,Rest).
pattern([1/_, 2/_, 3/_, 4/_, 5/_, 6/_, 7/_, 8/_]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variant 2
queens2(S) :-
perm([1,2,3,4,5,6,7,8],S),
safe(S).
safe([]).
safe([Q|Rest]) :-
safe(Rest),
notbeat2(Q,Rest,1).
notbeat2(_,[],_).
notbeat2(Y,[Y1|ListY],DistX) :-
Y1-Y =\= DistX,
Y-Y1 =\= DistX,
Dist1 is DistX+1,
notbeat2(Y,ListY,Dist1).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variant 3
% Obobshtenie na reshenieto za N na broj carici i duska NxN.
% sol(N,S), kudeto S e reshenieto, a N e razmera na duskata.
queens3(N,S) :-
generate(1,N,Dxy),
Nu1 is 1-N, Nu2 is N-1,
generate(Nu1,Nu2,Du),
Nv2 is N+N, generate(2,Nv2,Dv),
solve3(S,Dxy,Dxy,Du,Dv).
solve3([],[],_,_,_).
solve3([X/Y|ListY],[X|Dx1],Dy,Du,Dv) :-
del(Y,Dy,Dy1),
U is X-Y, del(U,Du,Du1),
V is X+Y, del(V,Dv,Dv1),
solve3(ListY,Dx1,Dy1,Du1,Dv1).
solution(ListY) :-
solve3(ListY,[1,2,3,4,5,6,7,8],
[1,2,3,4,5,6,7,8],
[-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7],
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]).
% Generator na Dx,Dy,Du,Dv
% generate(N1,N2,List), kudeto List=[N1,N1+1,N1+2,...,N2-2,N2-1,N2]
generate(N,N,[N]).
generate(N1,N2,[N1|List]) :-
N1 < N2, M is N1+1,
generate(M,N2,List).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variant 4
queens4(N,Board):-
makelist(N,L),
Diagonal is N*2-1,
makelist(Diagonal,LL),
placeN(N,board([],L,L,LL,LL),board(Board,_,_,_,_)).
placeN(_,board(D,[],[],D1,D2),board(D,[],[],D1,D2)):-!.
placeN(N,Board1,Result):-
place_a_queen(N,Board1,Board2),
placeN(N,Board2,Result).
place_a_queen(N,board(Queens,Rows,Columns,Diag1,Diag2),
board([q(R,C)|Queens],NewR,NewC,NewD1,NewD2)):-
del(R,Rows,NewR),
del(C,Columns,NewC),
D1 is N+C-R,
del(D1,Diag1,NewD1),
D2 is R+C-1,
del(D2,Diag2,NewD2).
makelist(1,[1]).
makelist(N,[N|Rest]):-
N>0,N1 is N-1,makelist(N1,Rest).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
member(X,[X|_]).
member(X,[_|L]):-member(X,L).
del(A,[A|L],L).
del(A,[B|L],[B|L1]):-del(A,L,L1).
perm([],[]).
perm([X|L],P):-perm(L,L1),del(X,P,L1).