On Wed, 02 Mar 2005 10:23:33 -0800, engsol <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
