How would you program this?

[Carl Banks]

engsol wrote:
> 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.

No kidding--it's a constrained integer programming problem.  Those can
be pretty nasty.  This one is pretty simple, being linear with only 12
unknowns.  However, they get very difficult very fast.  There are whole
optimization textbooks written on this kind of problem.


> 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.

Not necessary.

It looks like there are 12 unknowns and 10 equations, and all equations
are linear.  Any two variables completely determine the values of all
the others: we just need to solve the linear equations to get them.
Once you've found all the others, check to see if they all satisfy the
constaint (i.e., they're all integers from 1 to 9).

In Python, this is easy with Numeric/numarray; pure Python I wouldn't
want to try (that's what Numeric is for), but it's possible.

So we've reduced the problem to brute forcing 2 variables, which is
only 81 combinations; definitely doable.


-- 
CARL BANKS