|Pathologically Eclectic Rubbish Lister|
Code for Constraint Satisfaction Problemsby Xilman (Friar)
|on Jan 16, 2010 at 14:00 UTC||Need Help??|
Xilman has asked for the wisdom of the Perl Monks concerning the following question:
I have a fairly typical constraint satisfaction problem (CSP) and I expected to be able to find a Perl module to help me solve it. No such luck --- either it doesn't exist or I haven't yet found the correct set of search terms.
Here is the problem:
For concreteness, let B=12, W=5 and S=20. This is an acceptable set:
because it has 21 values and 21 >= S.
http://www.win.tue.nl/~aeb/codes/binary-1.html implies that the largest possible acceptable set has 32 members.
A simple-minded approach of choosing random integers in the range 0 ... 0xfff and testing for consistency with previously chosen integers has found sets with 24 members.
Question: can anyone point me to a module / script which can find significantly larger acceptable sets in a reasonable amount of computation. Brute force searching of a (2<<12)<<32 sized space is not reasonable!