On Thu, 3 Mar 2005 14:57:13 -0000, "Duncan Smith" <[EMAIL PROTECTED]> wrote:
> >"engsol" <[EMAIL PROTECTED]> wrote in message >news:[EMAIL PROTECTED] >> 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 > >This sort of thing actually is a real Python project for me. Unfortunately >you don't generally (in practice) end up with constraints on diagonals in >contingency tables, so my code can't solve this particular problem. You >might be interested in checking out the shuttle algorithm (Fienberg and >Dobra), and seeing if you can tweak it to handle more general constraints. > >Duncan > The diagonal constraint is interesting....it seems to affect the number of solutions. One surprise, (not being a math major), was that when I let the brute force run (forever, it seemed), but without the diagonal qualification(s), there was maybe 100 solutions. The reson it was a surprise it that years ago a programmer used the row-sum, col-sum method to detect and correct data errors. He swore it was robust, and 100% reliable. Seems that that isn't the case. Norm B -- http://mail.python.org/mailman/listinfo/python-list
