How would you program this?

[engsol]

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