# Vaje 12: Programiranje z omejitvami
## Uvod
Da lahko programiramo z omejitvami, moramo v prolog naložiti ustrezno knjižnico. Na začetek našega programa zapišemo direktivo
:- use_module(library(clpfd)).
za delo s [končnimi domenami](http://www.swi-prolog.org/pldoc/man?section=clpfd) (celimi števili) oziroma
:- use_module(library(clpr)).
za delo z [realnimi števili](http://www.swi-prolog.org/pldoc/man?section=clpqr).
Na vajah bomo uporabljali omejitve na celih številih. Knjižnica CLP(FD) podpira aritmetične operacije in operatorje za primerjavo:
+ - * ^ min max mod rem abs // div
#= #\= #>= #=< #> #<
Domeno za posamezno spremenljivko določimo tako:
A in 0..42
B in inf..sup
ali za seznam spremenljivk hkrati:
[A,B,C] ins 1..10
Omejitev `all_distinct([A,B,C])` zagotovi, da imajo spremenljivke `A`, `B` in `C` različne vrednosti. S predikatom `label([A,B,C])` pa naročimo prologu, da s preiskovanjem našteje konkretne vrednosti spremenljivk, ki ustrezajo vsem podanim omejitvam. Preden uporabimo `label`, morajo biti domene vseh spremenljivk omejene.
:- use_module(library(clpfd)).
A in 0..42.
A #> 2, A #=< 4, label([A]).
### Naloga "klekljarice"
Na rednem tedenskem srečanju se je zbralo `X` klekljaric. Nekatere so s sabo pripeljale tudi svoje mačke; teh je bilo skupaj `Y`. Vemo, da je na srečanju bilo 22 glav in 72 nog. Napiši predikat `meeting(X, Y)`, ki postavi ustrezne omejitve in vrne število klekljaric in mačk, ki so bile na srečanju.
% implementiraj predikat meeting/2
meeting(X, Y).
## Problem `n` dam
Napisali bomo program, ki na šahovsko ploščo velikosti `n×n` razporedi `n` dam tako, da se med sabo ne napadajo (torej noben par dam ni na isti horizontali, vertikali ali diagonali). Koordinate posamezne figure bomo zapisali v obliki `X/Y`.
### `safe_pair(X1/Y1, X2/Y2)`
Napišite predikat `safe_pair(X1/Y1, X2/Y2)`, ki z ustreznimi omejitvami zagotovi, da se dami na poljih `X1/Y1` in `X2/Y2` med sabo ne napadata. Primer:
?- safe_pair(1/1, 2/2).
false.
?- safe_pair(4/2, 5/3).
false.
?- safe_pair(3/3, 4/2).
false.
?- safe_pair(1/1, 2/3).
true.
% implementiraj predikat safe_pair/2
safe_pair(X1/Y1, X2/Y2) :-
X1 #\= X2,
Y1 #\= Y2,
abs(X2-X1) #\= abs(Y2-Y1).
safe_pair(1/1, 2/2).
safe_pair(4/2, 5/3).
safe_pair(3/3, 4/2).
safe_pair(1/1, 2/3).
### `safe_list/2`
Napišite predikat `safe_list(X/Y, L)`, ki sprejme koordinate ene dame in seznam koordinat preostalih dam ter preveri, da dama na koordinatah `X/Y` ne napada nobene v seznamu. Primer:
?- safe_list(1/1, [3/4, 3/8, 2/3, 3/5]).
true.
% implementiraj predikat safe_list/2
safe_list(_, []).
safe_list(Q, [H|T]) :-
safe_pair(Q, H),
safe_list(Q, T).
safe_list(1/1, [3/4, 3/8, 2/3, 3/5]).
### `safe_list/1`
Napišite predikat `safe_list(L)`, ki sprejme seznam koordinat in preveri, da se med sabo ne napada noben par dam v seznamu. Primer:
?- safe_list([3/3, 2/5, 1/7, 8/6, 5/4, 7/8]).
true.
% implementiraj predikat safe_list/1
safe_list([]).
safe_list([H|T]) :-
safe_list(H, T),
safe_list(T).
safe_list([3/3, 2/5, 1/7, 8/6, 5/4, 7/8]).
### `place_queens/3`
Napišite predikat `place_queens(N, I, L)`, ki na šahovnico velikosti `N×N` razporedi `N` dam tako, da je vsaka v svojem stolpcu (ima svojo koordinato `X`). Predikat naj vrne koordinate v seznamu `L`. `I` je pomožen parameter, ki hrani trenutno vrednost koordinate `X`. Primer:
?- place_queens(2, 0, L), term_variables(L, Vars), label(Vars).
L = [1/1, 2/1],
X = [1, 1] ;
L = [1/1, 2/2],
X = [1, 2] ;
L = [1/2, 2/1],
X = [2, 1] ;
L = [1/2, 2/2],
X = [2, 2] ;
false.
Predikat `term_variables(L, Vars)` poišče vse spremenljivke v izrazu (seznamu) `L` in jih shrani v seznam `Vars`, na katerem lahko potem pokličemo `label/1`. Predikat `place_queens/2` poskusite napisati tako, da se ustavi, ko vrne vse rešitve.
place_queens(N, I, []) :-
I #>= N.
place_queens(N, I, [I1/Y|T]) :-
I #< N,
Y in 1..N,
I1 #= I + 1,
place_queens(N, I1, T).
place_queens(2, 0, L), term_variables(L, Vars), label(Vars).
### `queens/2`
Napišite predikat `queens(N, L)`, ki na šahovnico velikosti `N×N` razporedi `N` dam tako, da se med sabo ne napadajo. Njihove koordinate naj vrne v seznamu `L`. Kakšen je najmanjši `N`, za katerega obstaja vsaj ena rešitev?
queens(N, L) :-
place_queens(N, 0, L),
safe_list(L),
term_variables(L, Vars),
label(Vars).
queens(4, L).
Lepši izpis rešitve:
:- use_rendering(chess).
queens2(N, L2) :-
queens(N, L),
maplist(arg(2), L, L2).
queens2(4, L).