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 -- http://mail.python.org/mailman/listinfo/python-list
