On 12/24/06, oyster <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
