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

[Paul McGuire]

<bearophileHUGS at lycos.com> wrote in message 
news:1166974469.681026.101070 at 42g2000cwt.googlegroups.com...
> 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[i] -= 1
>        if i & 1:
>            j = p[i]
>        else:
>            j = 0
>        alist[j], alist[i] = alist[i], alist[j]
>        r = func(alist)
>        if r is not None: result.append(r)
>        i = 1
>        while p[i] == 0:
>            p[i] = 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