How would you program this?

[engsol]

On Thu, 3 Mar 2005 14:57:13 -0000, "Duncan Smith" <buzzard at urubu.freeserve.co.uk> wrote:

>
>"engsol" <engsolnorm at peak.org> wrote in message
>news:savb21dksa0hr21a8vvb4im0bpgk82huca at 4ax.com...
>> There is a number puzzle which appears in the daily paper.
>> Because I'm between Python projects, I thought it might be
>> fun to write a program to solve it....20 minute job, max.
>>
>> On closer inspection, it became apparent that it's not a
>> simple thing to program. How would you approach it?
>>
>> The puzzle: a 4 x 4 grid. The rows are summed (and given), the
>> cols are summed (and given), and the two diagonals are summed,
>> and given. In addition, 4 clues are given, but none of the 4 are in
>> the same row or col.
>>
>> Example from today's paper:...solution time is 8 minutes, 1 second,
>> so they say.
>>
>> The set of allowable numbers  is 1 thru 9
>>
>> Rows:
>> 3 + B + C + D = 22
>> E + F + 8 + H = 26
>> I + J + K + 8 = 31
>> M + 7 + O + P = 25
>>
>> Col sums:
>> 24, 18, 31, 31
>>
>> Diag sums:
>> 3 + F + K + P = 24
>> M + J + 8 + D = 24
>>
>>
>>
>> The first impulse is to just brute force it with nested for loops,
>> but the calculator shows the possible combinations are
>> 9^12 = 5,159,780,352, which would take much too long.
>>
>> Another approach would be to inspect each square and determine
>> what the range of reasonable numbers would be. For example,
>>
>> if A + 9 + C + D = 14, then A, C, D can only have a value of 1 or 2 or 3,
>> which would greatly reduce the for loop range of A, C and D.
>> While useful, it's still a manual task.
>>
>> I can't help but think there's a better way. If you have a real Python
>> project, this isn't worth your time, but if a student, it might be a good
>> exercise to think how you'd do it.
>> Norm B
>
>This sort of thing actually is a real Python project for me.  Unfortunately
>you don't generally (in practice) end up with constraints on diagonals in
>contingency tables, so my code can't solve this particular problem.  You
>might be interested in checking out the shuttle algorithm (Fienberg and
>Dobra), and seeing if you can tweak it to handle more general constraints.
>
>Duncan
>

The diagonal constraint is interesting....it seems to affect the number of
solutions. One surprise, (not being a math major), was that when I let the
brute force run (forever, it seemed), but without the diagonal qualification(s),
there was maybe 100 solutions. The reson it was a surprise it that years
ago a programmer used the row-sum, col-sum method to detect and correct
data errors. He swore it was robust, and 100% reliable. Seems that that
isn't the case.
Norm B