How would you program this?

[engsol]

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

[Russell Blau]

"engsol" <en********@peak.org> wrote in message
news:sa********************************@4ax.com...

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.

What you have is a set of 10 linear equations in 11 variables. Normally
that isn't
enough to generate a unique solution, but the additional constraint that all
variables must have values in the range 1..9 probably will get you to a
unique solution. I suggest you Google for techniques for solving
"simultaneous linear equations".
--
I don't actually read my hotmail account, but you can replace hotmail with
excite if you really want to reach me.

[James Stroud]

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

This is a system of 12 variables and 10 equations. Looks like there will be
more than one solution (if I remember my 8th grade algebra--its beginning to
get very foggy). Given a proper set of linear equations, I think numarray and
scientific python have very convenient tools for this. An introductory linear
algebra book can provide everything you need to know about this topic.

--
James Stroud, Ph.D.
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

[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

[Paul Rubin]

"Carl Banks" <in**********@aerojockey.com> writes:

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.

Why is it an integer programming problem rather than just a set of
simultaneous equations? It looks offhand like 12 equations in 12
unknowns that can be solved with linear algebra, but I haven't tried
solving it.

[Bill Mill]

On Wed, 02 Mar 2005 10:23:33 -0800, engsol <en********@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

[Roel Schroeven]

Paul Rubin wrote:

"Carl Banks" <in**********@aerojockey.com> writes:

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.

Why is it an integer programming problem rather than just a set of
simultaneous equations? It looks offhand like 12 equations in 12
unknowns that can be solved with linear algebra, but I haven't tried
solving it.

It's because solutions involving non-integer numbers are invalid in this
context. And there are 12 unknowns but only 10 equations.

--
"Codito ergo sum"
Roel Schroeven

[Bill Mill]

<snip>

This should have said "time python linalg_brute.py" . I changed the
name, but didn't rerun the test. linalg.py is the same as
linalg_brute.py.

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

Peace
Bill Mill
bill.mill at gmail.com

[Dennis Lee Bieber]

On Wed, 2 Mar 2005 13:44:07 -0500, "Russell Blau" <ru******@hotmail.com>
declaimed the following in comp.lang.python:

What you have is a set of 10 linear equations in 11 variables. Normally
Worse -- there are 12 unknowns in the 10 equations...
-- ================================================== ============ <
wl*****@ix.netcom.com | Wulfraed Dennis Lee Bieber KD6MOG <
wu******@dm.net | Bestiaria Support Staff <
================================================== ============ <
Home Page: <http://www.dm.net/~wulfraed/> <
Overflow Page: <http://wlfraed.home.netcom.com/> <

[Duncan Smith]

"engsol" <en********@peak.org> wrote in message
news:sa********************************@4ax.com...

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

[Russell Blau]

"Dennis Lee Bieber" <wl*****@ix.netcom.com> wrote in message
news:qk********************************@4ax.com...

On Wed, 2 Mar 2005 13:44:07 -0500, "Russell Blau" <ru******@hotmail.com>
declaimed the following in comp.lang.python:

What you have is a set of 10 linear equations in 11 variables. Normally

Worse -- there are 12 unknowns in the 10 equations...

Yup, I need to grow two more fingers, I guess.
--
I don't actually read my hotmail account, but you can replace hotmail with
excite if you really want to reach me.

[engsol]

On Thu, 3 Mar 2005 14:57:13 -0000, "Duncan Smith" <bu*****@urubu.freeserve.co.uk> wrote:

"engsol" <en********@peak.org> wrote in message
news:sa********************************@4ax.com.. .

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

[pwalessi1]

very nice.

[Bill Mill]

On Thu, 03 Mar 2005 10:52:23 -0800, engsol <en********@peak.org> wrote:

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.

I think that it probably is a decent gut-check for data errors, for
the simple reason that changing one number requires, at a minimum,
three other changes in order to maintain both the row and column sums.
If you have at least a decent data fidelity rate, that is unlikely to
happen, and even if it does, very very unlikely to happen in such a
way that the row and column sums are maintained; especially as the
number of rows and columns grows.

Better to just do a crc or a hash of the data though.

Peace
Bill Mill
bill.mill at gmail.com

[engsol]

On Thu, 3 Mar 2005 15:32:36 -0500, Bill Mill <bi*******@gmail.com> wrote:

On Thu, 03 Mar 2005 10:52:23 -0800, engsol <en********@peak.org> wrote:

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.

I think that it probably is a decent gut-check for data errors, for
the simple reason that changing one number requires, at a minimum,
three other changes in order to maintain both the row and column sums.
If you have at least a decent data fidelity rate, that is unlikely to
happen, and even if it does, very very unlikely to happen in such a
way that the row and column sums are maintained; especially as the
number of rows and columns grows.

Better to just do a crc or a hash of the data though.

Peace
Bill Mill
bill.mill at gmail.com

You make a good point Bill, and are entirely correct.
I never liked that programmer, and was too hasty in
condeming his work...shame on me....I was unfair.

BTW, I ran the code you suggested, (I like your approach), after
correcting the A cell value (should have 5 vice 3 as I posted). There seems
to be 16 solutions, one of which agrees with the puzzle author.

I don't fully understand this line of your code:
return [(a,b,c) for a in ns for b in ns for c in ns if a + b + c == limit]
If the "if" part is true, does it 'trigger' the return?
Norm B

[Steven Bethard]

engsol wrote:

I don't fully understand this line of your code:
return [(a,b,c) for a in ns for b in ns for c in ns if a + b + c == limit]
If the "if" part is true, does it 'trigger' the return?

This code is basically equivalent to:

lc = []
for a in ns:
for b in ns:
for c in ns:
if a + b + c == limit:
lc.append((a, b, c))
return lc

Does that help?

STeVe

[engsol]

On Thu, 03 Mar 2005 19:32:19 -0700, Steven Bethard <st************@gmail.com> wrote:

engsol wrote:

I don't fully understand this line of your code:
return [(a,b,c) for a in ns for b in ns for c in ns if a + b + c == limit]
If the "if" part is true, does it 'trigger' the return?

This code is basically equivalent to:

lc = []
for a in ns:
for b in ns:
for c in ns:
if a + b + c == limit:
lc.append((a, b, c))
return lc

Does that help?

STeVe

Now it's clear....thank you.
Norm B