 /*
  *
  * stable_marriage.pl :	Source prolog code solving "Stable Marriage Problem"
  * Implemented by : 		Psallidas Fotis
  * std code :			std06170
  * Project Reference:		Logic Programming Project 7.0
  *
  */

:- lib(fd).
%Comment out next line and give the proper input dataset for stable_marriage problem 
%:- compile(stable10).


/* 
 *	variables(SM,SW,N):
 *		Declaring Variables for stable marriage problem.
 *		For every man and every woman there is a corresponding variable.
 *		SM variables are corresponding to men.
 *		SW variables are corresponding to women. 
 */
variables(SM,SW,N):-
	length(SM,N),
	length(SW,N).

/*
 *	domain(SM,SW,N):
 *		SM variables have domain women
 *		SW variables have domain men.
 *		This is done to declare a marriage.
 *		One one hand a certain man has a corresponded variable 
 *		which is about to be his wife,so her domain are all the possible women.
 *		On the other hand a certain woman has a corresponded variable
 *		which is about to be her husband,so his domain are all the possible men.	 
 */
domain(SM,SW,MEN,WOMEN):-
	SM :: WOMEN,
	SW :: MEN.

/* 
 *	constraint(SM,SW):
 *		The possible wifes' set and the possible husbands' set
 *		must not contain a certain woman or man twice. 
 *		This is because we want to marry N men with N women,and all must
 *		get married.
 */
constraint(SM,SW):-
	alldifferent(SM),
	alldifferent(SW).

/*
 *	Now we want to declare the basic constraint which is.
 *	If we have a marriage M-W then this marriage is stable if
 *	M likes another woman(say W1) than W then W1 must like her husband A1 more than M and
 *	if W likes another man (say A2) than M then A2 must like her wife G2 more than W.
 *	To express something like that based on the csp declaration we have done till now 
 *	we take every possible combination of A-W (constants A-W) and say that
 *	if M likes her possible wife (which is his corresponded variable in SM variables) less than W ,
 *	then W must like her possible husband (which is her corresponded variable in SW variables)  more than M and
 *	if W likes her possible husband more than M then M must like his possible wife more than W.
 *	Schema virtualize 
 *			    N3
 *			 ------->
 *			M  	 W
 *			 <-------
 *			|   N4	 |
 *		     N1 |	 | N2
 *			|	 |
 *		       \ /      \ /
 *			`        `
 *			DM       DW
 *	Where:
 * 		N1 is how much man M likes his possible wife DM.
 *		N2 is how much woman W likes his possible husband DW.
 *		N3 is how much man M likes woman W.
 *		N4 is how much woman W like man M.
 *		So the constraints we can declare now are:
 *		N1 > N3 => N2 < N4 and N2 > N4 => N1 < N3.
 *	This gets done for every possible combination of M-W.
 *	
 *	Till now everything seems good but there is also something
 * 	we have to declare.If M-W is a marriage then also W-M is a marriage.
 *	This can be expressed by declaring than 
 *		M == DW <=> W == DM [look schema]
 *	This is also gets done for every possible combination of W-M.
 */
create_men([],[],_,_).
create_men([MAN | MEN],[MAN_DOMAIN_H | MEN_DOMAIN_T],WOMEN,WOMEN_DOMAIN):-
	create_women(MAN,MAN_DOMAIN_H,WOMEN,WOMEN_DOMAIN),
	create_men(MEN,MEN_DOMAIN_T,WOMEN,WOMEN_DOMAIN).

create_women(_,_,[],[]).
create_women(MAN,MAN_DOMAIN_H,[WOMAN | WOMEN],[WOMAN_DOMAIN_H | WOMAN_DOMAIN_T]):-
	prefers(WOMAN,WOMAN_prefers),
	prefers(MAN,MAN_prefers),
	/* N1: how much MAN likes possible wife */
	element(N1,MAN_prefers,MAN_DOMAIN_H),
	/* N2: how much WOMAN likes POSSIBLE HUSBAND */
	element(N2,WOMAN_prefers,WOMAN_DOMAIN_H),
	/* N3: how much MAN prefers WOMAN */
	element(N3,MAN_prefers,WOMAN),
	/* N4: how much WOMAN prefers MAN */
	element(N4,WOMAN_prefers,MAN),
	/* constraints */
	N1 #> N3 #=> N2 #< N4,
	N2 #> N4 #=> N1 #< N3,
	/* If A-G is a marriage then G-A is also a marriage */
	MAN #= WOMAN_DOMAIN_H #<=> WOMAN #= MAN_DOMAIN_H,
	create_women(MAN,MAN_DOMAIN_H,WOMEN,WOMAN_DOMAIN_T). 

/*
 *	generate(SW): 
 *		solving problem by giving variables proper values. 
 */
generate([]).
generate([WIFE | REST_WIFES]):-
	indomain(WIFE),
	generate(REST_WIFES).

/*
 *	marry(M,W):
 *		Transform the solution set to proper format.
 */
marry([],[],[]).
marry([MAN | MEN],[WIFE | WIFES],[MAN-WIFE | T]):-
	marry(MEN,WIFES,T).

stable(S):-
	/* take women */
	women(WOMEN),
	/* take men */
	men(MEN),
	/* find men's */
	length(MEN,N),
	/* declare variables */
	variables(SM,SW,N),
	/* declare variables' domain */ 
	domain(SM,SW,MEN,WOMEN),
	/* declare constraints' on variables */
	constraint(SM,SW),
	create_men(MEN,SM,WOMEN,SW),
	/* solve problem */
	generate(SW),
	/* transform solution to proper format */ 
	marry(MEN,SM,S).
