A CP Model for the Weight Problem of Bachet de Meziriac

Fellow OR blogger Erwin Kalvelagen just posted a MINLP model for a puzzle apparently posed by French mathematician Claude Gaspard Bachet de Méziriac. You can read the puzzle statement on Erwin's blog; a brief synopsis is that you are looking to find four integer weights that sum to 40, such that any object with integer weight from 1 to 40 can be weighed using them. I assume (and Erwin apparently agrees) that means weight on a balance scale, where weights can be placed either in the same pan as the object being weighed or in the opposite pan.

Just for amusement, here's a MiniZinc constraint programming model for the problem. It yields (unsurprisingly) the same unique solution that Erwin's MINLP model produces.

% Bachet de Meziriac problem

include "globals.mzn";

% sizes of the pieces
array[1..4] of var 1..40: x;

% pieces used in subtotals
array[1..40, 1..4] of var -1..1: y;

% order constraints
constraint increasing(x);

% overall sum
constraint sum(x) = 40;

% partial sums
constraint forall (i in 1..40) (sum([ x[j]*y[i,j] | j in 1..4 ]) = i);

% search
solve::int_search(x, largest, indomain_max, complete) satisfy;