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]

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".

 

[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.

 

[Carl Banks]

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.

 

[Paul Rubin]

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]

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]

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.

 

[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]

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

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


--

 

[Duncan Smith]

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]

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

Yup, I need to grow two more fingers, I guess.

 

[engsol]

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]

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]

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]

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]

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