3

I just post a mathematic question at math.stackexchange, but I'll ask people here for a programmatically recursive algorithm.

The problem: fill in the blank number from 1 to 9 (once and only once each blank) to finish the equation.

problem

Additional conditions: 

1. Mathematic priority DOES matter. 
2. All numbers (include evaluation result) should be integers.
Which mean the divide should be divisible (E.g. 9 mod 3 = 0 is OK, 8 mod 3 != 0 is not OK).
3. For those who don't know (as one in the original question), the operations in the diagram are: 
+ = plus; : = divide; X = multiple; - = minus.

There should be more than 1 answer. I'd like to have a recursive algorithm to find out all the solutions.

Original question

PS: I'd like to learn about the recursive algorithm, performance improval. I was trying to solve the problem using brute force. My PC freeze for quite a while.

Community
  • 1
  • 1
Eddie
  • 1,903
  • 2
  • 21
  • 46
  • 4
    what do you have so far, what exactly are you asking? I hope it's not "will you code this for me?" – ryanpattison May 18 '15 at 18:35
  • I only have a brute force solution. I'm looking for a speedy, easy to read and develop algorithms. I have thought about using recursion, but no idea where to start, where to finish, where to branch the loop. – Eddie May 18 '15 at 18:37
  • 4
    _"I was trying to solve the problem using brute force. My PC freeze for quite a while."_ Strange, there are only 9! = 362,800 different possibilities, so brute forcing should be pretty quick. – Kevin May 18 '15 at 18:38
  • Maybe I was using too many loops, variables, branch conditions? – Eddie May 18 '15 at 18:39
  • @Eddie too many loops sounds likely, post your brute force solution. – ryanpattison May 18 '15 at 18:50
  • I don't think it's worth posting a full answer, but if you've got many levels (e.g. 9) of nested loops, it *is* worth considering using a recursive solution - see e.g. http://stackoverflow.com/questions/15866798/efficiently-creating-a-nested-for-loop-x-layers-deep . In your case, you'd have to keep track of where you were up to in each layer of the loop, so that you can evaluate the sum when you hit `max_depth` (the recursion termination condition) – J Richard Snape May 19 '15 at 13:03

2 Answers2

2

You have to find the right permuations

9! = 362880

This is not a big number and you can do your calculations the following way:

isValid(elements)
    //return true if and only if the permutation of elements yields the expected result
end isValid

isValid is the validator, which checks whether a given permutation is correct.

calculate(elements, depth)
    //End sign
    if (depth >= 9) then
        //if valid, then store
        if (isValid(elements)) then
            store(elements)
        end if
        return
    end if
    //iterate elements
    for element = 1 to 9
        //exclude elements already in the set
        if (not contains(elements, element)) then
            calculate(union(elements, element), depth + 1)
        end if
    end for
end calculate

Call calculate as follows:

calculate(emptySet, 1)
Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
  • where are you getting four slots? I see nine. – ryanpattison May 18 '15 at 18:47
  • Me too, I see 9 also. But the algorithm looks good. I'll try it tomorrow. – Eddie May 18 '15 at 18:50
  • depth make sure it is four slots. When depth >= 4, the algorithm will stop due to return. depth is increased in each iteration and its initial value is 1. So it is first slot, second slot, third slot, fourth slot, store if needed and stop. This is the idea in plain words. – Lajos Arpad May 18 '15 at 18:52
  • Yes, I understand that much. Just it's not fit 9 slots as in the original question, but that's the algorithm for you. Thank you anyway. – Eddie May 18 '15 at 18:55
  • If I am not mistaken, you have to try 9 numbers on 4 places, right? – Lajos Arpad May 18 '15 at 18:56
  • I believe it's 9 numbers on 9 places. There are 9 blanks in the figure, right? Kevin is right, there are 9! = 362,800 posibilitities. – Eddie May 18 '15 at 19:02
  • That's not too serious. The important thing is you've provided a solution, an algorithm. That's what I need. Thank you. I hope one day I'd be as pro as you :( – Eddie May 18 '15 at 19:04
  • You were right, my friend. My answer's initial version was mistaken, therefore I have edited it. I believe you will understand the answer, you seem to be a bright fellow – Lajos Arpad May 18 '15 at 19:05
  • Not as bright as you. I'll test the algorithm and mark your answer soon. But I think it's correct already. – Eddie May 18 '15 at 19:07
0

Here's a solution using PARI/GP:

div(a,b)=if(b&&a%b==0,a/b,error())
f(v)=
{
  iferr(
    v[1]+div(13*v[2],v[3])+v[4]+12*v[5]-v[6]-11+div(v[7]*v[8],v[9])-10==66
  , E, 0)
}
for(i=0,9!-1,if(f(t=numtoperm(9,i)),print(t)))

The function f defines the particular function here. I used a helper function div which throws an error if the division fails (producing a non-integer or dividing by 0).

The program could be made more efficient by splitting out the blocks which involve division and aborting early if they fail. But since this takes only milliseconds to run through all 9! permutations I didn't think it was worth it.

Charles
  • 11,269
  • 13
  • 67
  • 105