Kaheksa lippu

Kuidas paigutada malelauale kaheksa lippu nii, et nad ei tulistaks (lipud tulistavad mööda ridu, veerge ja diagonaale) üksteist ?
Ülesande muudab tunduvalt lihtsamaks probleemile sobiva andmestruktuuri leidmine. Tavaliselt tähistatakse malelaua ruute kahekohalise jadaga: a1, g5 jne - esimene on veeru, teine rea tähis. Prologi jaoks peaks need tähised olema aatomid ja kui nendega hakata manipuleerima (otsima, millal üks lipp tulistab teist), tuleks need aatomeid jagada osadeks (täht, number), mõisted "sama rida", "sama veerg" oleks lihtsad (sama esimene või teine tähis), kuid mõiste "samal diagonaalil" kirjeldus tuleks üsna segane.
"Samal diagonaalil" mõiste on üsna lihtne, kui nii read kui ka veerud tähistada numbritega 1,2,...,8 - sel juhul lipud (i,j) ja (i1,j1) asuvad samal diagonaalil, kui kas i+j = i1+j1 (langev diagonaal) või i - j = i1 - j1 (tõusev diagonaal). Lipud peavad asuma kõik erinevatel ridadel (muidu mõni lipp tulistaks teist), seega igal real peab asuma üks lipp ka lipud võib loetleda (lahenduses) ridade järjekorras, seega oline on vaid teine, veeruindeks. Lipud peavad asuma kõik erinevates veergudes (taas muidu mõni tulistaks teist), seega lahenduse määrab mingi erinevate veeruindekstite nimistu, s.t. nimistu, mis saadakse nimistust [1,2,3,4,5,6,7,8] mingi permutatsiooniga. Kõike seda arvesse võttes on ülesannet lihtne lahendada: tuleb leida mingi permutatsioon, arvutada selle permutatsiooni ja nimistu [1,2,3,4,5,6,7,8] (reaindeksid!) vastavate elementide summad ja vahed ja kontrollida, et nii summade kui ka vahede nimistud koosneks erinevatest elementidest:

lahend(P) :-
perm([1,2,3,4,5,6,7,8],P),
kombineeri([1,2,3,4,5,6,7,8],P,S,D),
erinevad(S),
erinevad(D).

kombineeri([X1|X],[Y1|Y],[S1|S],[D1|D]) :-
S1 is X1 +Y1,
D1 is X1 - Y1,
kombineeri(X,Y,S,D).

kombineeri([],[],[],[]).

erinevad([X|Y]) :-
not(member(X,Y)), erinevad(Y).

erinevad([X]).

perm([X|Y],Z) :-
perm(Y,W), lisa(X,W,Z).

perm([],[]).

lisa(X,R,[X|R]).

lisa(X,[F|S],[F|R]) :-
lisa(X,S,R).

Ülesandeid:

1. Kuidas muuta programmi, nii et ridade-veergude arv ei oleks fikseeritud, vaid oleks predikaadile lahenda antav parameeter?

2. Tee programm, mis leiab maksimaalse malelauale paigutatud üksteist mittetulistavate ratsude arvu; ratsu ruudul (I,J) tulistab ruutu (I1, J1), kui kas abs(I1-I)=1, abs(J1-J)=2 või abs(I1-I)=2, abs(J1-J)=1 ).

3. Eelmine ülesanne, kuid laua suurus on n x n ( parameeter n sisestatakse).

Küsimused, probleemid: