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

[oyster]

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
2. is there any free/open lib for this?
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
4. I don't know how to deal with case 3 and case 4


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

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

3: calculate the minimum of
sin((z*x-0.5)^2 + x*2*y^2-z/10)*exp(-((x-0.5-exp(-y+z))^2 + y^2-z/5+3))
where x in [-1,7], y in [-2,2]

4: calculate the root [x,y,z], let
(x-0.3)^y^z+x/y/z-x*y*sin(z)+(x+y-z)^cos(x-1) = 1
(y-0.2)^z^x+y/z/x-y*z*sin(x)+(y+z-x)^cos(y-2) = 2
(z-0.1)^x^y+z/x/y-z*x*sin(y)+(z+x-y)^cos(z-3) = 3


I have written the case 1 in python, it needs 90 seconds on my pc, and
the same approach in www.freebasic.net takes less than 1 seconds
[code for python]
import sets
import time
try:
import psyco
psyco.full()
except:
pass

d0, d1=1, 2

st=time.time()
result=[]
for a0 in range(1,10):
for a1 in sets.Set(range(1,10))-sets.Set([a0]):
for a2 in sets.Set(range(1,10))-sets.Set([a0,a1]):
a1a2=a1*10+a2
if 2*a0< a1a2:
for b0 in sets.Set(range(1,10))-sets.Set([a0,a1,a2]):
for b1 in sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0]):
for b2 in sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1]):
b1b2=b1*10+b2
if 2*a0*b1b2 + 2*b0*a1a2 < a1a2*b1b2:
for c0 in sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1, b2]):
for c1 in
sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1, b2, c0]):
for c2 in
sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1, b2, c0, c1]):
c1c2=c1*10+c2
if d1*a0*b1b2*c1c2 + d1*b0*a1a2*c1c2 +
d1*c0*a1a2*b1b2 == d0*a1a2*b1b2*c1c2:
aresult=[[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]]
aresult.sort()
if aresult not in result:
result.append(aresult)
et=time.time()
print 'time elapsed: %s s' % (et-st)
for [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] in result:
print ' %0d %0d %0d %0d' % (a0, b0, c0, d0)
print '--- + --- + --- = ---'
print ' %0d%0d %0d%0d %0d%0d %0d' %(a1, a2, b1, b2, c1,c2, d1)
print
[/code]

 

[John Machin]

oyster wrote:
[snip]

I have written the case 1 in python, it needs 90 seconds on my pc, and
the same approach in www.freebasic.net takes less than 1 seconds
[code for python]
import sets
import time
try:
import psyco
psyco.full()
except:
pass

d0, d1=1, 2

st=time.time()
result=[]
for a0 in range(1,10):
for a1 in sets.Set(range(1,10))-sets.Set([a0]):
for a2 in sets.Set(range(1,10))-sets.Set([a0,a1]):
a1a2=a1*10+a2
if 2*a0< a1a2:
for b0 in sets.Set(range(1,10))-sets.Set([a0,a1,a2]):
for b1 in sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0]):
for b2 in sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1]):
b1b2=b1*10+b2
if 2*a0*b1b2 + 2*b0*a1a2 < a1a2*b1b2:
for c0 in sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1, b2]):
for c1 in
sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1, b2, c0]):
for c2 in
sets.Set(range(1,10))-sets.Set([a0,a1,a2,b0, b1, b2, c0, c1]):

Has it not occurred to you to "calculate" sets.Set(range(1,10)) *ONCE*,
store it, and reuse it?

For the remaining uses of sets.Set, do
set = sets.Set
once up the front, and remember to remove it when (as you should!) you
upgrade off Python 2.3.

HTH,
John

 

[Paul McGuire]

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
2. is there any free/open lib for this?
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
4. I don't know how to deal with case 3 and case 4


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

Since you are working with permutations of [1..9], here is a general
framework for problems using those permutations - put your problem
definition in the function func, which is successively passed each of the
362880 permutations of the numbers 1-9. On my system, your original code
ran in about 11 seconds, and after factoring out invariants, got down to
about 1.8 seconds. This little framework takes about 4.5 seconds, but with
psyco, cuts down to about 1.3 seconds.

-- Paul


import time
try:
import psyco
psyco.full()
except:
pass

def prod(lst):
return reduce(lambda a,b:a*b,lst,1)

def perms(setSize, sampleSize):
return prod(xrange(setSize-sampleSize+1,setSize+1))

def permutation(k, s):
fact = 1
s = s[:]
for j in xrange( 2, len(s)+1):
fact = fact * (j-1)
idx1 = j - ((k / fact) % j)-1
idx2 = j-1
s[idx1],s[idx2] = s[idx2],s[idx1]
return s

def permutations(s,sampleSize=None):
if sampleSize is None:
sampleSize = len(s)
k = perms(len(s),sampleSize)
for i in xrange(k):
yield permutation(i,s)

d0,d1 = 1,2
def func(p):
a0,a1,a2,b0,b1,b2,c0,c1,c2 = p

# do application evaluation here
b1b2 = 10*b1+b2
a1a2 = 10*a1+a2
c1c2 = 10*c1+c2
if d1*a0*b1b2*c1c2 + d1*b0*a1a2*c1c2 + d1*c0*a1a2*b1b2 ==
d0*a1a2*b1b2*c1c2:
return sorted( [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] )
else:
return None

st = time.time()
result = []
for p in permutations(range(1,10)):
aresult = func(p)
if aresult is not None and aresult not in result:
result.append(aresult)

et=time.time()
print 'time elapsed: %.4f s' % (et-st)
for [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] in result:
print ' %0d %0d %0d %0d' % (a0, b0, c0, d0)
print '--- + --- + --- = ---'
print ' %0d%0d %0d%0d %0d%0d %0d' %(a1, a2, b1, b2, c1,c2, d1)
print

 

[Marc 'BlackJack' Rintsch]

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
2. is there any free/open lib for this?
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
4. I don't know how to deal with case 3 and case 4


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

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

The first two can be solved by a finite domain constraint solver. Logilab
has a pure-python package:

http://www.logilab.org/view?rql=Any X WHERE X eid 852

Ciao,
Marc 'BlackJack' Rintsch

 

[bearophileHUGS]

Paul McGuire:

This little framework takes about 4.5 seconds, but with
psyco, cuts down to about 1.3 seconds.

st = time.time()
result = []
for p in permutations(range(1,10)):
aresult = func(p)
if aresult is not None and aresult not in result:
result.append(aresult)

et=time.time()
print 'time elapsed: %.4f s' % (et-st)
for [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] in result:
print ' %0d %0d %0d %0d' % (a0, b0, c0, d0)
print '--- + --- + --- = ---'
print ' %0d%0d %0d%0d %0d%0d %0d' %(a1, a2, b1, b2, c1,c2, d1)
print

If you want to more speed, put long loops always inside functions, not
inside the main body:

def main():
st = clock()
result = []
for p in permutations(range(1, 10)):
aresult = func(p)
if aresult is not None and aresult not in result:
result.append(aresult)

et = clock()
print 'time elapsed: %.4f s' % (et-st)
for [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] in result:
print ' %0d %0d %0d %0d' % (a0, b0, c0, d0)
print '--- + --- + --- = ---'
print ' %0d%0d %0d%0d %0d%0d %0d' %(a1, a2, b1, b2,
c1,c2, d1)
print

main()

If you have a bit of time you can test the speed of this code on your
computer.

Bye,
bearophile

 

[bearophileHUGS]

Using Psyco this version is much faster, you can test it on your PC
compared to the other one (the whole running time, Psyco compilation
too):
Psyco is unable to speed up generator functions, so you have to return
true lists.
Giving the func to the permutation function, you can avoid lot of list
copying and unpacking.


try:
import psyco
psyco.full()
except ImportError:
pass

d0, d1 = 1, 2


def func(p):
a0,a1,a2,b0,b1,b2,c0,c1,c2 = p
# do application evaluation here
b1b2 = 10*b1+b2
a1a2 = 10*a1+a2
c1c2 = 10*c1+c2
if d1*a0*b1b2*c1c2 + d1*b0*a1a2*c1c2 + d1*c0*a1a2*b1b2 \
== d0*a1a2*b1b2*c1c2:
return sorted( [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] )
else:
return None


def accepted_permutations(alist, func):
# func must return None for the unacceptable results
# Algoritm from Phillip Paul Fuchs, modified
result = []
items = alist[:]
n = len(alist)
p = range(n+1)
i = 1
r = func(alist)
if r is not None: result.append(r)
while i < n:
p -= 1
if i & 1:
j = p
else:
j = 0
alist[j], alist = alist, alist[j]
r = func(alist)
if r is not None: result.append(r)
i = 1
while p == 0:
p = i
i += 1
return result


def main():
result = []
for aresult in accepted_permutations(range(1, 10), func):
if aresult not in result:
result.append(aresult)
[[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] = aresult
print ' %0d %0d %0d %0d' % (a0, b0, c0, d0)
print '--- + --- + --- = ---'
print ' %0d%0d %0d%0d %0d%0d
%0d'%(a1,a2,b1,b2,c1,c2,d1)
print

main()

Bye,
bearophile

 

[Paul McGuire]

Using Psyco this version is much faster, you can test it on your PC
compared to the other one (the whole running time, Psyco compilation
too):
Psyco is unable to speed up generator functions, so you have to return
true lists.
Giving the func to the permutation function, you can avoid lot of list
copying and unpacking.


try:
import psyco
psyco.full()
except ImportError:
pass

d0, d1 = 1, 2


def func(p):
a0,a1,a2,b0,b1,b2,c0,c1,c2 = p
# do application evaluation here
b1b2 = 10*b1+b2
a1a2 = 10*a1+a2
c1c2 = 10*c1+c2
if d1*a0*b1b2*c1c2 + d1*b0*a1a2*c1c2 + d1*c0*a1a2*b1b2 \
== d0*a1a2*b1b2*c1c2:
return sorted( [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] )
else:
return None


def accepted_permutations(alist, func):
# func must return None for the unacceptable results
# Algoritm from Phillip Paul Fuchs, modified
result = []
items = alist[:]
n = len(alist)
p = range(n+1)
i = 1
r = func(alist)
if r is not None: result.append(r)
while i < n:
p -= 1
if i & 1:
j = p
else:
j = 0
alist[j], alist = alist, alist[j]
r = func(alist)
if r is not None: result.append(r)
i = 1
while p == 0:
p = i
i += 1
return result


def main():
result = []
for aresult in accepted_permutations(range(1, 10), func):
if aresult not in result:
result.append(aresult)
[[a0, a1, a2], [b0, b1, b2], [c0, c1, c2]] = aresult
print ' %0d %0d %0d %0d' % (a0, b0, c0, d0)
print '--- + --- + --- = ---'
print ' %0d%0d %0d%0d %0d%0d
%0d'%(a1,a2,b1,b2,c1,c2,d1)
print

main()

Bye,
bearophile

Nice and neat. I guess what appeals to me is that this is essentially a
brute force approach. Instead of a goal-seeking constraint solver, this
just brute force tries every possible permutation. Of course, this breaks
down quickly when the size of the input list grows large, but the OP was
trying to work with permutations of the digits 1-9 using an unwieldy nesting
of for loops and set manipulations. Using permutations is no more or less
smart of an algorithm than in the original post, it just cleans up the for
loops and the set arithmetic.

For example, for all the complexity in writing Sudoku solvers, there are
fewer than 3.3 million possible permutations of 9 rows of the digits 1-9,
and far fewer permutations that match the additional column and box
constraints. Why not just compute the set of valid solutions, and compare
an input mask with these?

-- Paul

 

[bearophileHUGS]

For people that will read the posts in the future, there is a little
bug (it doesn't change the output of this program):

items = alist[:]

Has to be:

alist = alist[:]

Sorry,
bye,
bearophile

 

[Gabriel Genellina]

For example, for all the complexity in writing Sudoku solvers, there are
fewer than 3.3 million possible permutations of 9 rows of the digits 1-9,
and far fewer permutations that match the additional column and box
constraints. Why not just compute the set of valid solutions, and compare
an input mask with these?

Are you sure? There are 9!=362880 rows of digits 1-9; taking 9 of
these at random gives about 10**50 possibilities. Of course just a
few match the additional constraints. Maybe you can trivially reduce
them (just looking for no dupes on the first column) but anyway its a
laaaaarge number... (Or I'm wrong computing the possibilities...)


--
Gabriel Genellina
Softlab SRL






__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

 

[Chris Mellon]

Are you sure? There are 9!=362880 rows of digits 1-9; taking 9 of
these at random gives about 10**50 possibilities. Of course just a
few match the additional constraints. Maybe you can trivially reduce
them (just looking for no dupes on the first column) but anyway its a
laaaaarge number... (Or I'm wrong computing the possibilities...)

According to Wikipedia, there are 6,670,903,752,021,072,936,960
possible classical Sudoku layouts. Ref.
http://www.research.att.com/~njas/sequences/A107739

 

[John Krukoff]

Are you sure? There are 9!=362880 rows of digits 1-9; taking 9 of
these at random gives about 10**50 possibilities. Of course just a
few match the additional constraints. Maybe you can trivially reduce
them (just looking for no dupes on the first column) but anyway its a
laaaaarge number... (Or I'm wrong computing the possibilities...)

Fortunately, somebody has already written a paper on the subject:
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf

It looks like the number is actually rather large, and I'd expect even
with a specialized data structure for compression (probably some kind of
tree with bitwise digit packing?) would not fit in memory on any box I
own.

I would wonder if loading that much data isn't slower than solving the
puzzle.

 

[Paul McGuire]

Are you sure? There are 9!=362880 rows of digits 1-9; taking 9 of these at
random gives about 10**50 possibilities. Of course just a few match the
additional constraints. Maybe you can trivially reduce them (just looking
for no dupes on the first column) but anyway its a laaaaarge number... (Or
I'm wrong computing the possibilities...)

Der, I was thinking 9 times 362880, not 326880 P 9. Thanks for
straightening me out!

10**50 was a good ballpark guess. My permutation calculator says that
362880 items taken 9 at a time yields
109099864394915605737486658299863377337267988480000 permutations (~10**50).
I assume the smaller Wikipedia number (6.7*10**21) factors in the additional
column and box constraints. So I guess we can rule out brute force as a
viable strategy after all.

-- Paul

 

[mark.dufour]

Using Psyco this version is much faster, you can test it on your PC
compared to the other one (the whole running time, Psyco compilation
too):

FWIW, the CVS version of Shed Skin optimizes this exact program a bit
further than Psyco:

Psyco: 0.66 s


Shed Skin: 0.30 s


Thanks,
Mark Dufour.
-- Shed Skin author, http://mark.dufour.googlepages.com