Find a mathematical algorithm for an equation
I'm just asking a math question at math.stackexchange, but I'm asking for a programmatic recursive algorithm here.
Problem: fill in a blank number from 1 to 9 (once and only once each blank) to complete the equation.
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 would like to have a recursive algorithm to find out all the solutions.
PS: I would like to learn about the recursive algorithm, improving performance. I tried to solve the problem using brute force. My computer freezes for a while.
source to share
You must find the right substitutions
9! = 362880
This is not a large number and you can do your calculations like this:
isValid(elements)
//return true if and only if the permutation of elements yields the expected result
end isValid
isValid
is a validator that checks the validity of the given permutation.
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
like this:
calculate(emptySet, 1)
source to share
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)))
A function f
defines a specific function here. I used a helper function div
that throws an error if division fails (create non-integer or divide by 0).
The program can be more efficient by breaking up blocks that involve division and interruption earlier if they fail. But since it only takes milliseconds to go through all 9! permutation I didn't think it was worth it.
source to share