This weekend I tried to play with the latest DMCommunity Challenge that asks: “Suppose you need to pay 1 Euro. In how many different ways you can do it via 1c, 2c, 5c, 10c, 20c, 50c and 1 Euro coins?” It sounds as a very simple problem for any constraint solver.

No wonder, there are already two constraint-based solutions:

• Pyomo – produced by Alireza Soroudi
• CPLEX – produced by Alex Fleischer

So, first I quickly added a similar solution but implemented using JSR-331, Java Constraint Programming API. They all produced 4563 different combinations. I decided to compare them with a basic Java solution:

It found all 4563 solutions within 38 milliseconds. Note that I limited the upper bounds inside the nested loops. If I would not do it, the program will work forever. A nice thing about constraint solvers that you don’t have to worry about such “small” details.

Then I asked ChatGPT to produce its own Java solution. Here is our dialog:

In response, ChatGPT produced a working Java code even with a recursion instead of nested loops.

All these solutions are efficient, produce correct results, and quite compact. However, they all require a programmer. My questions was: “How can a business person represent and solve this problem?“

I decided to do it using OpenRules RuleSolver and built a relatively simple decision model in Excel. RuleSolver usually requires two tables “Define” and “Solve”:

The table “Define” defines our problem using the following tables:

Here “Scalar Product” is defined as “Coin Variables X Coin Values”, and the only constraint in “DefineConstraints” sets the Scalar Product to be equal to Total Value (100).

The table “Solve” uses the standard RuleSolver method “SolverFindAllSolutions” and “SolverLogSolutions”. Printing of all solutions takes the most time and here are the last 3 solutions: