Combinatorial problem?

oq4v3ht0u76kf2

Apologies for the cross post in both Maths and Programming, but it really is a cross-disciplinary problem.

A friend of mine has given me this problem and it really is wrecking my head. I have a list of 22 distinct 16 digit numbers. They hold within them the clues to one true solution to the code, i.e. the single correct thirteen digit number. My clues are as follows. The number of correct digits for a given code indicates how many digits within that example are correct.

x0: 0 correct digits
x1 - x6: 1 correct digit
x7 - x13: 2 correct digits
x15 - x21: 3 correct digits

For example, a line may be:
3248975391044454 with 2 correct digits

So, let's just assume it's the first two which are correct, the correct code will be:
32ABCDEFGHIJKLMN where A - N are other digits.

I'm absolutely lost trying to find a decent algorithm which will let me solve this question. He assures me that the correcgt algorithm will find a solution in less than twenty minutes on any modern computer. I've been using Python to try and solve the problem.

I cannot devise an algorithm which will allow me to eliminate numbers from each position. I had something I thought would work which basically ran like this:

Guess first X digits from row 1 where X is the number we have been told are correct in row 1
Guess first Y digits from row 2 where Y is the number we have been told are correct in row 2

And so on, until EITHER:

1. Guess is complete and we have our solution
2. Guess cannot go any further (for example, gets to row [i]M[/i] and there are no possible correct values left, where 0 < [i]M[/i] < 20)

My problem lies in the fact that more often than not, we'll get to scenario two as the guess will break unless we are very lucky during our first run... however, when the guess does break, what exactly does this tell me? Was the first number I placed in the guess incorrect? Is the very last number I've guessed? Can I say anything EXCEPT that the EXACT sequence of numbers I have guessed is incorrect? - This seems very brute forcish for something supposedly elegant.

Does anyone have any tips or references I could take a look at? If there's not much interest but anyone really does want to try and tackle this with me, I'm always availabile at rob@robburke.ie but let's try and get a good thread going first!

Martyr

if i'm guessing right, you want to create all possible combinations using numbers 0 - 9 for 13 digits in length?

1 way you could do this is using pointers or arrays..if using arrays, increment each element from 0 - 9

each element would represent a digit in the string "0123456789"
this might take more than 20 minutes though.

how do you know if you've got correct combination?

FSL

I think you need to be a little more explicit. Does correct means correct digit in correct position or just correct digit. Should the answer be a sixteen digit number not a thirteen one. This seems like an advanced variation on the old Mastermind Game. Ten colours, code sixteen long solve it on the 23 move.

oq4v3ht0u76kf2

Sorry, yeah, it's a lot like Mastermind except with 16 pegs and 10 colours. I have an algorithm which will generate my list of numbers in a 0,15 array however this is an inelegant and brutish approach - not to mention it would take months, if not years, to check every single combination - there are 10^16 possibilities. Even once I remove numbers I know cannot happen in each column I still only reduce it to 263,303,591,362,560 - over 263 billion combinations.

Unlike Mastermind, this game only tells us how many digits in a Guess are exactly right. We recieve no feedback as to other correct digits in the wrong place.

And yes, the answer should be a 16 digit one - a typo on my part.

@FSL:
Did you get the solve it on the 23rd move from something in my post or an idea of yours?

@AverageJoe:
The only way we'll know is if it matches exactly 3 digits in 8 of my incorrect rows, 2 digits in 7, 1 digit in 6 and 0 digits in 1.

FSL

If it is solvable from the 22 rows of input then those were the first 22 attempts and by implication the result is the 23rd. Are we to assume that the first row has no correct digits the next six have 1 the next 7 have 2 and the last 8 have 3.

oq4v3ht0u76kf2

Yes FSL, that's it exactly. Now, where to go from there?