## Linear programming #1 – Project Euler 185

I was recently faced with a very nice challenge from Project Euler – Problem 185. The idea is to find a number with a fixed number of digits by making guesses. Each time you are told how many digits you got right. By got right, I mean guessing the right digit on the right position. If you find a digit which is in the number, but on a different position, you don’t know…

There is a test case with 5 digits:

90342 ;2 correct

70794 ;0 correct

39458 ;2 correct

34109 ;1 correct

51545 ;2 correct

12531 ;1 correct

with unique solution 39542 and the difficult case with 16 digits

5616185650518293 ;2 correct

3847439647293047 ;1 correct

5855462940810587 ;3 correct

9742855507068353 ;3 correct

4296849643607543 ;3 correct

3174248439465858 ;1 correct

4513559094146117 ;2 correct

7890971548908067 ;3 correct

8157356344118483 ;1 correct

2615250744386899 ;2 correct

8690095851526254 ;3 correct

6375711915077050 ;1 correct

6913859173121360 ;1 correct

6442889055042768 ;2 correct

2321386104303845 ;0 correct

2326509471271448 ;2 correct

5251583379644322 ;2 correct

1748270476758276 ;3 correct

4895722652190306 ;1 correct

3041631117224635 ;3 correct

1841236454324589 ;3 correct

2659862637316867 ;2 correct

While the small case could be tackled using a pure brute force approach (only ) cases to check, the second case becomes intractable. Looping through all cases would take ages. One could try genetic algorithms or other algorithms based on randomness. Recursive approaches are also possible.

There is however a way to express this problem which makes it solvable right away using a linear programming solver: that is an algorithm which finds valid solutions given some constraints. How do we find these constraints? There are essentially two types of constraints in our case:

- each of the positions of the result contains one digit from 0 to 9
- in each of the guesses given above we have a fixed number of correct digits

We can model this in the following way: we define a matrix of size (number of digits from 0 to 9) times (number of digits of the result). At position (i,j) in this matrix we have 1 if the position j of the result contains the digit i-1 and zero otherwise. For example, the matrix corresponding to the result in the case of the 5 digit guess sequence 39542 is

Now, we can see clearer how can we impose the desired constraints. The fact that we have only one digit per position in the result is equivalent to the fact that on each column of the above matrix we have only one position equal to 1, or that the sum on the columns of the matrix is 1. This gives us as many constraints as digits in the solution. For example, the condition that in column 2 the sum is 1 can be written as

Now the conditions given by the current guesses are a bit different, but the idea is the same. For example the condition (90342 ;2 correct) can be translated to the following: in the set there are exactly 2 ones and three zeros. Therefore

Of course, this conditions can be found in an automatic way starting from the given guesses. This can be implemented in Matlab or Octave using linprog. If you have Yalmip installed then the setup is more straightforward, as illustrated in previous posts where I showed how to solve a Sudoku puzzle with Matlab or Two more mind games solved using Matlab.

Nice post Beni. A couple questions:

1. What is the big-o complexity of solving a the series of equations?

2. Can you provide any intuition behind why the brute force search space is so much larger? I can see that we’re “throwing out” the negative information with the brute force approach, as it were, but you wouldn’t guess it would be worth that much. I understand the matrix approach technically, but I can’t quite wrap my head around *why* the seemingly small amount of information we’re given turns out to narrow things down so much.

Hello and thank you for your comment.

1. You ask what is the complexity for solving a series of equations, but what is done here is more: for the big case we have 22×16 unknowns (if I counted right) and only 22+16 equations. Normally this would give infinitely many solutions. The fact that we search solutions with values only equal to 0 or 1 greatly limits the set of solutions, which finally makes the solution unique. Unfortunately, I do not know what is the complexity of the algorithm. I will take a look at the references mentioned in the Matlab documentation.

2. For the brute force approach, note that you have 16 positions with variable digits. For each position you have 10 possible variants. This gives you 10 ^ 16 possibilities. To imagine the magnitude of the calculation, run an empty for loop and time it. On regular computer you should be able to do a 10^8 loop in under a minute. Now, if 10^8 takes only one second, let’s say, then multiply this with 10^8 to get 10^8 seconds to reach 10^16. Now divide 10^8 seconds by 3600 to get the time in hours and by 24 to get the time in days. You’ll get 1157 days, which is a few years already.

Hope this helps.