Just for fun: Countdown numbers game solver

[dg.google.groups at thesamovar.net]

Hi all,

It's great how many different sorts of solutions (or almost solutions)
this puzzle has generated. Speedwise, for reference my solution posted
above takes about 40 seconds on my 1.8GHz laptop, and the less elegant
version (on my webpage linked to in the original post) takes about 15
seconds. It seems to me like surely this problem can be more
efficiently solved than that?

My version isn't very Pythonic (it could almost be written in C++ the
way I've done it) so I liked the idea of the first solution, but I
don't think it can be fixed. I adapted it so that it doesn't use the
same number more than once, but it still has some problems. Firstly,
it only finds solution ((a op b) op c) op d etc. and won't find (for
example (1+2)*(3+4). Secondly, it stores a dictionary value->how to
get to value which is fine if you can re-use numbers because one way
to get to a given value is as good as another, but sometimes you can
get to the same number in two different ways using different numbers,
so it misses solutions.

Paul: 758 = 8+(5*((2+4)*25))

Arnaud: I haven't had time to play with your solution yet - how quick
does it run?

My fantasy is that there is a solution that isn't TOO slow where you
can just look at the code and go 'Oh yes, of course that works!' and
understand it immediately. Maybe that's too much to ask even of
Python! ;-)