How would you program this?

[Bill Mill]

On Wed, 02 Mar 2005 10:23:33 -0800, engsol <engsolnorm at peak.org> 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. 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.
> 

Are you sure about that? You can eliminate a whole lot of options just
based on the row (or column, if you're so inclined) totals. Here's
what I came up with in 10 minutes:

#--------------------linalg_brute.py------------------------------
ns = range(1,10)
def mkrow(limit):
    return [(a,b,c) for a in ns for b in ns for c in ns if a + b + c == limit]
row1 = mkrow(19)
row2 = mkrow(18)
row3 = mkrow(23)
row4 = mkrow(18)
for b,c,d in row1:
    for e,f,h in row2:
        for i,j,k in row3:
            for m,o,p in row4:
                if 3 + e + i + m == 24 and 7 + b + f + j == 18 \
                and 8 + c + k + o == 31 and 8 + d + h + p == 31 \
                and 3 + f + k + p == 24 and m + j + 8 + d == 24:
                    print 3,b,c,d
                    print e,f,8,h
                    print i,j,k,8
                    print m,7,o,p
                    print '-------------'
#--------------end linalg_brute.py-----------------------------

Of course, it could use a whole bunch of generalization, but that
wasn't the point. It runs quite nicely:

02:42 PM /d/code/Python$ time python linalg.py
3 3 8 8
9 3 8 6
9 5 9 8
3 7 6 9
-------------
3 3 9 7
8 3 8 7
9 5 9 8
4 7 5 9
-------------

real    0m1.255s
user    0m1.221s
sys     0m0.030s

Both solutions look correct to me; how about you? With clever enough
heuristics, problems that you can expect people to solve will almost
always fall to brute force algorithms, I feel.

Peace
Bill Mill
bill.mill at gmail.com