COSC5313                     PROGRAM-5                   
                          PARTNER MATCHING 
                           (Backtracking)           		Due: 5/1/2013                 

The program is to employ a backtracking design which involves making a series of decisions/choices and
making a forward move after each such decision and then eventually returning to each previous point 
where a decision was previously made to cancel (and nullify) the decision/choice in making 
a different decision/choice to move forward all over again in a different direction in 
either finding all solutions or finding just one solution, whichever is the case. 
  
PROBELM:
 
  We have a set of 8 men and 8 women. 
  And, we have two input matrices of their respective preferences.
  We want to find out all possible matchings of these people (eight men and as many women)
  subject to just one constraint.
  The only one constraint is that:
  if man-A and women-B are to be matched (as a potential married couple), then it is necessary that 
  (a) there is no married woman-W such that this woman-W prefers this man-A to
  her own husband and man-A also prefers this woman-W to his proposed wife woman-B and 
  (b) there is no married man-M such that this man-M prefers this woman-B to his own wife and 
  woman-B also prefers this man-M to her  proposed husband man-A.
   
INPUTS:  

  Men's Preference Matrix (wmr[m,r] represents a woman who is the preference #r of man #m) 
  
    7 2 6 5 1 3 8 4
    4 3 2 6 8 1 7 5
    3 2 4 1 8 5 7 6
    3 8 4 2 5 6 7 1
    8 3 4 5 6 1 7 2
    8 7 5 2 4 3 1 6
    2 4 6 3 1 7 5 8
    6 1 4 2 7 5 3 8
   
  Women's Preference Matrix (mwr[w,r] represents a man who is the preference #r of woman #w)

    4 6 2 5 8 1 3 7
    8 5 3 1 6 7 4 2
    6 8 1 2 3 4 7 5
    3 2 4 7 6 8 5 1
    6 3 1 4 5 7 2 8
    2 1 3 8 7 4 6 5
    3 5 7 2 4 1 8 6
    7 2 8 4 5 6 3 1

OUTPUT REQUIREMENTS: 

  1. Print the two input preference matrices under a suitable heading each. 
  2. Print all matching solutions (9 of them) in the non-increasing order of man's total
     preferences.
  3. Print the Male Optimal Solution.  
      7  4  3  8  1  5  2  6
  4. Print the Female Optimal Solution.