The stable marriage problem.

Awaiting the next Drools puzzle I decided to write a solver for the stable marriage problem:

Given a set of N men and N women, marry them off in pairs after each man has ranked the women in order of preference from 1 to N, {w1, ..., wN} and each woman has done likewise, {m1, ..., mN}. If the resulting set of marriages contains no pairs of the form {mA,wB}, {mC,wD} such that mA prefers wD to wB and wD prefers mA to mC, the marriage is said to be stable.

It's an old problem and you can read lots more about it here [PDF], here and here, and there's a solver Applet here. I haven't googled for source code and solutions to the problem but there are some descriptions of algorithms and ways to go about it (using a procedural language) in the links above.

I aimed at a small rule set so it might not be super efficient but I don't think it's particularly bad either. On my machine the limit seems to be at around 15, 16 men and women. If you try it with more than that it takes a long, *long* time to finish. I should probably also mention that my solver disagrees sometimes with the solver applet I linked to above. I do believe that the solver applet is wrong though but if you can spot mistakes in my code, please let me know.

Enjoy!

CLIPS> (batch "C:/Program/CLIPS/drools-puzzle/marriage.bat")
TRUE
CLIPS> (clear)
CLIPS> (load "marriage.clp")
%%%***
TRUE
CLIPS> (load "marriage-data-16.clp")
$
TRUE
CLIPS> (reset)
CLIPS> (run)
man-3 (#10) is married to woman-1 (#4)
man-11 (#4) is married to woman-8 (#9)
man-16 (#3) is married to woman-14 (#1)
man-8 (#2) is married to woman-4 (#2)
man-14 (#6) is married to woman-3 (#3)
man-5 (#1) is married to woman-2 (#3)
man-1 (#11) is married to woman-11 (#9)
man-4 (#1) is married to woman-6 (#2)
man-15 (#1) is married to woman-15 (#2)
man-13 (#2) is married to woman-16 (#2)
man-12 (#5) is married to woman-10 (#1)
man-7 (#5) is married to woman-9 (#1)
man-9 (#8) is married to woman-5 (#8)
man-10 (#1) is married to woman-7 (#5)
man-6 (#5) is married to woman-12 (#1)
man-2 (#2) is married to woman-13 (#1)
CLIPS>