Pop Quiz: Solve a math puzzle?
I found an article online about 3rd grade mathematics in Vietnam. I think it would be interesting to see how we can solve this problem. Mathematical or programmatically.
I wrote a test function for this, feel free to adapt it to any programming language you are comfortable with:
var answer = [1,1,1,1,1,1,1,1,1,1];
var isCorrect = function (answer) {
return ((((((((((((a[0]+13)*a[1])/a[2])+a[3])+12)*a[4])-a[5])-11)+a[6])*a[7])/a[8])-10) === 66;
};
Rule: there should be no repeatable number in the array. Accepted digits: 1-9.
source to share
from constraint import *
def formula(a, b, c, d, e, f, g, h, i):
return abs(a + (13 * (b / c)) + d + (12 * e) - f -
11 + ((g * h) / i) - 10 - 66) < 0.001
if __name__ == '__main__':
all_vals = [float(i) for i in xrange(1, 10)]
p = Problem()
[p.addVariable(l, all_vals) for l in 'abcdefghi']
p.addConstraint(AllDifferentConstraint())
p.addConstraint(FunctionConstraint(formula), 'abcdefghi')
result = p.getSolution()
print [s for s in sorted(result.items(), key=lambda (k,v): k)]
Answers:
[('a', 9.0), ('b', 8.0), ('c', 6.0),
('d', 2.0), ('e', 4.0), ('f', 1.0),
('g', 5.0), ('h', 7.0), ('i', 3.0)]
source to share
Marak, your MATLAB code works well, except that the S string must be modified to get correct arithmetic results. New code:
p = perms(1:9);
S = p(:,1)+(13.*p(:,2)./p(:,3))+p(:,4)+(12.*p(:,5))-p(:,6)-11+(p(:,7).*p(:,8)./p(:,9))-10 == 66;
sum(S)
p(S,:)
For example, one test solution (abcdefghi) = (3 2 1 5 4 7 9 8 6)
Using this code change, there are 128 unique solutions.
See link.
source to share
Matlab / Octave (brute force):
p = perms(1:9) ;
S = (((((((((((p(:,1)+13).*p(:,2))./p(:,3)+p(:,4))+12).*p(:,5))-p(:,6))-11)+p(:,7)).*p(:,8))./p(:,9))-10) == 66 ;
sum(S)
p(S,:)
I ran it on an octave online and it suggests there are 144 solutions that took only a fraction of a second to compute. ( http://octave-online.net the initial popup looks scary, but it just tries to help, click it and copy all the program code to the console below and hit [return] to see all 144 solutions, sometimes you get errors "too big download ", but it only shows, math works fine in the background.)
Explanation
For a math problem, obviously a programming language designed to solve these problems is a good choice and can take a lot of work off you, so I used Octave, even though I'm a Java programmer, this is what the program does:
-
1:9
gives a vector numbered1
up to9
(1 x 9) -
perms()
calculates all permutations of this vector and returns it as a matrix (9! x 9) -
;
suppresses output -
p =
the permutation matrix is stored inp
-
p(:,n)
accesses then
th columnp
, so all solutions are evaluated at once -
.*
and./
provide cell-by-cell multiplication rather than standard matrix multiplication. - comparing the resulting vector with
66
returns a vector of gates that is stored inS
and is similar to a vector1
when the equation is true and0
otherwise (9! x 1) -
sum(S)
displays the number of solutions -
p(S,:)
returns all rows where the equation from the previous was true, solutions (144 x 9)
source to share
I think there might be a more efficient approach to the problem, but in scince there are only 9 variables with 9 valid values and we have computers, brute force.
The idea is to try the check () function for each permutation, i.e. ways to put numbers from 1 to 9 in array a []. This means 9! iterations = 362880 which my laptop can work with in a couple of seconds.
I create recursove permutate (): For each level It in, the permutation function loops the numbers 1 through 9, puts each one at the position of the array level (but only if the number is not already in the previous positions) and does not call itself for the next level, When at level 9 the array is full, it can call the check function.
here's the code in java:
public class Test {
static float[] a = { 0, 0, 0, 0, 0, 0, 0, 0, 0};
private static int countSolutions = 0;
public static void main(String[] args){
permutate(0);
System.out.println(countSolutions);
}
public static boolean permutate( int level){
boolean isCorrect = false;
if(level == 9){
isCorrect = check();
if(!isCorrect){
}
}
else
for(int i = 1; i <= 9; i++){
int j = 0;
for(; j < level && a[j]!=i; j++);
if( j == level){
a[level] = i;
isCorrect = permutate( level + 1);
}
}
return isCorrect;
}
private static boolean check() {
float result = ((((((((((((a[0]+13)*a[1])/a[2])+a[3])+12)*a[4])-a[5])-11)+a[6])*a[7])/a[8])-10);
if ( result == 66){
countSolutions ++;
for (int i = 0; i < 9; i++) {
System.out.print(a[i]+",");
}
System.out.println();
return true;
}else{
return false;
}
}
}
Results (144):
1.0 2.0 4.0 7.0 5.0 8.0 3.0 6.0 9.0
1.0 2.0 7.0 5.0 3.0 4.0 9.0 8.0 6.0
....
....
source to share