How would you program this?

[Duncan Smith]

"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