c++ countdown number game solver

[shayan1234]

Hello, I have been programming simple things for some time now and now i want to try something abit more complex
I was thinking of creating a countdown number game solver,

Those who are not familiar with this check this link
http://www.youtube.com/watch?v=pfa3MHLLSWI

the rules are that you have 6 numbers, 1 target number and
4 operations (+ , - , x , / ):
you basicaly have to generate a solution from the 6 numbers to get the target number.

I have given this a deep explore and only possible solution i could think of is
bruteforce which unfortunatly i am not very good with atm.

I just wanted to ask you professionals out there, what other ways are there to solve a problem like this, (any algorithms which match this problem?)
if so which would be easiest to code and understand at the same time.

Thanks in advance for you help.

[hamsterman]

Here's an older thread that has a bit of a discussion on this and a couple of implementations: http://www.cplusplus.com/forum/lounge/53835/
It is an ugly problem, but then, brute-forcing is a useful skill (I'm saying that but I'm not sure that a cleaner solution does not exist).

[shayan1234]

@hamsterman (4037)
Thanks
I will have a look at the post now

[kev82]

Can you explain what you mean by brute force - what is the algorithm you've thought of.

I have just implemented a brute force solution, but may be different to yours.

1) Generate all binary trees with between 1 and 6 leaf nodes.
1a) For quick runtime, it is vital to remove any duplicate trees.
2) For each tree generate the entire set of expressions (each binary node can be +, -, *, /, each leaf node can be 1,2,3,4,5,6 but no two leaves can have the same number)
3) Evaluate each expression generated in 2, I did it with a simple rpn calculator, but depends how you implemented (1) - be extra careful with division.
4) Print the expressions that match the target.

It runs in under a minute evaluating all possible combinations.