Solving twenty-four puzzles(blog.plover.com)
blog.plover.com
Solving twenty-four puzzles
http://blog.plover.com/math/24-puzzle.html
11 comments
I never bothered creating a program to solve this as I prefer to do the exercise mentally. I've been playing with 1440 puzzles: one for each display of a 24 hour clock. The puzzle is simple: take a displayed time and using the 4 displayed numbers and the 4 basic operations (+ - x /), make it solve to zero. To make it more complex, it is forbidden to multiply by zero. Eg. 12:34 >> (1+4)-(2+3)=0. The puzzle does not solve for all hours, but it does for 12:3x and many other times
[deleted]
That's a neat puzzle! Here is the Prolog code I posted earlier, extended and adapted to solve such tasks:
First, let us again start with a suitable operator definition, so that we can use × as an infix operator in expressions:
The puzzle now asks for expressions that evaluate to 0. We can relate any given clock display to an expression like this:
First, let us again start with a suitable operator definition, so that we can use × as an infix operator in expressions:
:- op(400, yfx, ×).
clock(Vs) :-
Vs = [H0,H1,M1,M2],
Vs ins 0..9,
H0*10 + H1 #< 24,
M1*10 + M2 #< 60,
label(Vs).
?- clock(Vs).
Vs = [0, 0, 0, 0] ;
Vs = [0, 0, 0, 1] ;
Vs = [0, 0, 0, 2] ;
Vs = [0, 0, 0, 3] .
?- findall(., clock(Vs), Ls), length(Ls, L).
Ls = ['.', '.', '.', '.', '.', '.', '.', '.', '.'|...],
L = 1440.
The puzzle now asks for expressions that evaluate to 0. We can relate any given clock display to an expression like this:
clock_solution(Vs, Expr) :-
clock(Vs),
numbers_tree(Vs, T),
tree_op_expr_value(T, _, Expr, 0).
numbers_tree([N], leaf(N)).
numbers_tree(Vs0, binary(Left, Right)) :-
permutation(Vs0, Vs),
append([L|Ls], [R|Rs], Vs),
numbers_tree([L|Ls], Left),
numbers_tree([R|Rs], Right).
tree_op_expr_value(leaf(N), _, N, N).
tree_op_expr_value(binary(Left0, Right0), Op, Expr, Value) :-
tree_op_expr_value(Left0, _, Left, VL),
tree_op_expr_value(Right0, _, Right, VR),
op_values_value(Op, VL, VR, Value),
Expr =.. [Op,Left,Right].
op_values_value(+, A, B, V) :- V is A + B.
op_values_value(-, A, B, V) :- V is A - B.
op_values_value(×, A, B, V) :- A =\= 0, B =\= 0, V is A * B.
op_values_value(/, A, B, V) :- B =\= 0, V is A rdiv B.
?- clock(C),
once(clock_solution(C, S)).
C = [0, 0, 0, 0],
S = 0+(0+(0+0)) ;
C = [0, 0, 0, 1],
S = 0/(0+(0+1)) ;
C = [0, 0, 0, 2],
S = 0/(0+(0+2)) ;
C = [0, 0, 0, 3],
S = 0/(0+(0+3)) .
?- clock(C),
\+ clock_solution(C, S).
C = [1, 6, 4, 8] ;
C = [1, 7, 4, 9] ;
C = [1, 7, 5, 9] ;
C = [1, 8, 4, 6] ;
C = [1, 9, 4, 7] ;
C = [1, 9, 5, 7] ;
false.Hmm, I think there also needs to be a rule that you can't have a numerator of 0, otherwise any case where you have an expression a * b = 0 with a = 0 then either b=0 or a / b = 0. So the restriction that you can't multiply by 0 becomes somewhat meaningless.
The constraints I impose are sufficient to exclude such cases in multiplications: a/b is first evaluated, and if the result is 0, it is precluded from multiplications. To avoid also divisions resulting in 0, you are right: We can easily constrain the nominator to express this, completely analogously to multiplication. This goes beyond the initial requirements though.
Nice, thank you for sharing! For comparison, here is a Prolog solution for one of the mentioned puzzles, namely "an unusually difficult puzzle of this type, which is to make 2,5,6,6 total to 17".
Let us start by defining suitable operators so that we can conveniently use the domain-specific language to reason about such tasks, using infix notation:
Now we are almost done. It only remains to describe how different arithmetic operations affect the result of the evaluation. This can be expressed with the following relations:
Let us start by defining suitable operators so that we can conveniently use the domain-specific language to reason about such tasks, using infix notation:
:- op(400, yfx, ×).
:- op(400, yfx, ÷).
numbers_tree([N], leaf(N)).
numbers_tree(Vs0, binary(Left, Right)) :-
permutation(Vs0, Vs),
append([L|Ls], [R|Rs], Vs),
numbers_tree([L|Ls], Left),
numbers_tree([R|Rs], Right).
?- numbers_tree([1,2], T).
T = binary(leaf(1), leaf(2)) ;
T = binary(leaf(2), leaf(1)) ;
false.
?- numbers_tree([1,1], T).
T = binary(leaf(1), leaf(1)) ;
T = binary(leaf(1), leaf(1)) ;
false.
Now we are almost done. It only remains to describe how different arithmetic operations affect the result of the evaluation. This can be expressed with the following relations:
tree_op_expr_value(leaf(N), _, N, N).
tree_op_expr_value(binary(Left0, Right0), Op, Expr, Value) :-
tree_op_expr_value(Left0, _, Left, VL),
tree_op_expr_value(Right0, _, Right, VR),
op_values_value(Op, VL, VR, Value),
Expr =.. [Op,Left,Right].
op_values_value(+, A, B, V) :- V is A + B.
op_values_value(-, A, B, V) :- V is A - B.
op_values_value(×, A, B, V) :- V is A * B.
op_values_value(÷, A, B, V) :- B =\= 0, V is A rdiv B.
?- time((numbers_tree([2,5,6,6], T),
tree_op_expr_value(T, _, Expr, 17))).
% 6,060 inferences, 0.004 CPU in 0.004 seconds (92% CPU, 1551459 Lips)
T = binary(binary(leaf(2), binary(leaf(5), leaf(6))), leaf(6)),
Expr = (2+5÷6)×6 .
I used to ask this as an interview question at Parse. I don't think it's that good of an interview question any more though. But it is definitely interesting to see how people try to solve it!
i wonder what the complexity of the generalized version of the problem is. it is a bit similar to subset sum, which is np complete.
in this problem we have 4 operators (+, -, /, *) to consider instead of just 1 (+), so it is more complex than subset sum in this regard. also as a result of having different operators, the ordering of the numbers matter in this case, which doesn't matter in subset sum. however the fact that we have to use each number exactly once significantly reduces the search space
in this problem we have 4 operators (+, -, /, *) to consider instead of just 1 (+), so it is more complex than subset sum in this regard. also as a result of having different operators, the ordering of the numbers matter in this case, which doesn't matter in subset sum. however the fact that we have to use each number exactly once significantly reduces the search space
The first line of each instance gave the number of numbers you had to work with, the second line gave those numbers separated by space, and the third line gave the target number.
Conciseness was measured by the number of tokens in the source code. Here is a copy of the problem specification: http://computer-programming-forum.com/47-c-language/3e0a04a3...
Here was the token counter used for that round: https://pastebin.com/bdaEedD7
Here is the first runner up and the winner: https://pastebin.com/JcamKieX
The runner up is 336 tokens. The winner is 335 tokens.
The best I was able to do was 460 tokens. (Well, the best without exploiting limitations of the token counter, but I was on dial up and so did not have the time to upload a 4 GB source file...)