ILP Part 72 — Self-descriptive numbers

This is the seventieth second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we’re going to solve self-descriptive numbers described in Delta article. Self-descriptive number is a number which “describes” itself: first digit denotes how many zeroes there are in decimal representation of the number. Second digit denotes how many ones and so on. We consider here decimal system only but the solution can be easily generalized to other systems as well.

Authors mention that optimized algorithm finds 10-digit number in couple seconds using Python. Let’s see if we can do better in ILP. Let’s use CplexMilpSolver as usual. The code:

First, we create solver in lines 1-9.

In line 11 we define ten non-negative integer variables. Next, in line 13 we set their upper bound. Here we use the fact that k-digit self-descriptive number must have digits which are less than k. Finally, in line 17 we specify that first digit must be non-zero.

Next we calculate counts. We define counters in line 19. Then in lines 21-25 we simply iterate over digits and compare them with constants.

Finally, in lines 27-29 we add constraints to make the number self-descriptive. We take each counter and make it equal to the respective digit.


So it looks like the solution was found in almost no time. Pretty good.