some OT: how to solve this kind of problem in our program?

[BJörn Lindqvist]

On 12/24/06, oyster <lepto.python at gmail.com> wrote:
> 1. first of all, what is the English jargon (Optimize? But I think
> this is not a very good keyword :( )for this problem? So I can use it
> to search on the internet

The first problem is a magic square. The general term for all your
problems are constraint satisfaction problems.

> 2. is there any free/open lib for this?

Yes, this for example: http://labix.org/python-constraint

> 3. I know for some questions(case 1, case 2, and sudoku), we can use
> bundles of "FOR...NEXT" loop to program. however I think it is clumsy
> and inconvenient, especially when there is many vars

Yes. I think it is also very much unoptimal. For solving problems such
as magic squares and sudoku puzzles you want a recursive backtracking
constraint solver.

> case:
> 1. choose x0~x9 from 1~9, and must use all of 1~9, let
> x0/(10*x1+x2)+x3/(10*x4+x5)+x6/(10*x7+x8)=1/2

Using the linked to constraint solver, you could write something like this:

p = Problem()
# Ten variables named 0..9 all with values in the domain 0..9
p.addVariables(range(10), range(10))
p.addConstraint(AllDifferentConstraint(), range(10))

def eqConstraint(*x):
    t = x[0]/(10*x[1] + x[2]) + x[3]/(10 * x[4] + x[5]) + x[5](10 * x[7] + x[8])
    # Convert to int to get rid of rounding errors
    t = int(t * 2)
    return t == 1
p.addConstraint(eqConstraint, range(10))
p.getSolutions()

> 2. choose x0~x15 from 1~16, and must use all of 1~16, let
> +-----+-----+-----+-----+
> |  x0 |  x1 |  x2 |  x3 |
> +-----+-----+-----+-----+
> |  x4 |  x5 |  x6 |  x7 |
> +-----+-----+-----+-----+
> |  x8 |  x9 | x10 | x11 |
> +-----+-----+-----+-----+
> | x12 | x13 | x14 | x15 |
> +-----+-----+-----+-----+
>
> sum of every column =sum of of every row
> = x0+x5+x10+x11 =x3+x6+x9+x12

Similar to above, just enter all the constraints and let the library
do the hard work:

def lineConstraint(*l):
    s1 = sum(l[:4])
    s2 = sum(l[4:])
    return s1 == s2

# For magic squares, recursive backtracking solves are the best
p = Problem(RecursiveBacktrackingSolver())
p.addConstraint(AllDifferentConstraint())
p.addConstraint(lineConstraint, [0, 5, 10, 11, 3, 6, 9, 12])
... add more constraints...
p.getSolution()

HTH

-- 
mvh Björn