% Изкуствен интелект, Факултет по математика и информатика, СУ "св. Кл. Охридски"

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%   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).