1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
| %-------------------------------------------%
% all(N, K, L) / debug(N,K,L) %
% N : taille des matrices %
% K : nombre de 1 sur chaque ligne/colonne%
% Succès : L est le nombre de solutions %
% (debug les affiche) %
all(N,K,L) :-
findall(N,find(N,K),Sols), length(Sols,L).
debug(N,K,L) :-
findall(N,findpp(N,K),Sols), length(Sols,L).
find(N,K) :-
% une matrice N * N
emptymat(N,N,L),
binmatrix(L,N,K).
findpp(N,K) :-
% une matrice N * N
emptymat(N,N,L),
binmatrix(L,N,K),
pretty_print(L), nl.
%-------------------------------------------%
% binmatrix(L, N, K) %
% N : un entier %
% K : un entier %
% Succès : L est une matrice de taille N %
% avec K 1 par ligne et par colonne%
binmatrix(L,N,K) :-
% Récupérer toutes les variables de L
flatten(L,AllVars),
transpose(L,LT),
% Toutes ces variables sont booléennes
fd_domain(AllVars,0,1),
% Sur chaque ligne, les contraintes
row_constraints(L,K),
% et sur chaque colonne aussi
row_constraints(LT,K),
% Toutes les contraintes sont
% ajoutées, reste à essayer
fd_labelingff(AllVars).
% Crée une matrice NxN quelconque
emptymat(N,0,[]).
emptymat(N,K,[R|L]) :-
M is (K-1), M >= 0,
emptyrow(N,R),
emptymat(N,M,L).
emptyrow(0,[]).
emptyrow(K,[_|R]) :-
M is (K-1), M >= 0,
emptyrow(M,R).
% Ajoute les contraintes sur les lignes
row_constraints([],_).
row_constraints([R|L],K) :-
fd_exactly(K,R,1),
row_constraints(L,K).
%-------------------------------------------%
% transpose(L, LT) %
% L : une liste de listes %
% Succès : LT est la transposée de L %
transpose([Row], LT) :- !,
list2columns(Row, LT).
transpose([Row|Rows], LT) :- !,
transpose(Rows, LT0),
put_columns(Row, LT0, LT).
list2columns([], []).
list2columns([X|Xs], [[X]|Zs]) :-
list2columns(Xs, Zs).
put_columns([], Cs, Cs).
put_columns([X|Xs], [C|Cs0], [[X|C]|Cs]) :-
put_columns(Xs, Cs0, Cs).
%-------------------------------------------%
% flatten(L, FL) %
% L : une liste de listes %
% Succès : FL est la version aplatie de L %
flatten([], []).
flatten([H | T], FL) :-
flatten(T, TFL),
append(H, TFL, FL).
%-------------------------------------------%
% pretty_print(L) %
% L : une liste de listes %
% Affiche joliment le résultat L %
pretty_print([]).
pretty_print([Row | L]) :-
write(Row),
nl,
pretty_print(L). |
Partager