# Re: How would you program this?

From: Russell Blau (russblau_at_hotmail.com)
Date: 03/02/05

```To: python-list@python.org
Date: Wed, 2 Mar 2005 13:44:07 -0500

```

"engsol" <engsolnorm@peak.org> wrote in message
news:savb21dksa0hr21a8vvb4im0bpgk82huca@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.
```

## Relevant Pages

• Re: Dynamic Hill cipher
... of systems of linear equations in the special case of the determinant ... being zero. ... have a unique solution but instead a large number of eligible solutions. ... and ciphertext you have at hand, ...
(sci.crypt)
• Re: How would you program this?
... Given a proper set of linear equations, ... An introductory linear ... algebra book can provide everything you need to know about this topic. ...
(comp.lang.python)
• Re: Solving a non-square matrix
... narenonline2k@yahoo.ca dixit: ... >I have the following linear equations. ... As Jeremy Watts said you can use gaussian elimination to solve this. ... With 15 equations and 3 unknowns, if there is a unique solution, then ...
(sci.math.num-analysis)
• ? finite-norm LS soln
... linear equations that have more unknowns than equations to ensure a ... unique solution. ... What if we impose a finite-norm condition, ...
(sci.math.num-analysis)