Solving twenty-four puzzles (blog.plover.com)

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:

    :- op(400, yfx, ×).
    :- op(400, yfx, ÷).

Next, I describe the relation between a list of numbers and possible shapes of binary trees we can build from these numbers. We distinguish between leaves and inner nodes of the tree, and consequently use two functors that let us symbolically distinguish the different cases:

    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).

For example:

    ?- numbers_tree([1,2], T).
    T = binary(leaf(1), leaf(2)) ;
    T = binary(leaf(2), leaf(1)) ;
    false.

This does not yet say anything about the arithmetic operators that we can use. Note that this definition may yield redundant solutions, as in:

    ?- numbers_tree([1,1], T).
    T = binary(leaf(1), leaf(1)) ;
    T = binary(leaf(1), leaf(1)) ;
    false.

That's completely OK though, and we can think about making it more efficient if necessary.

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 to try it out, using for example the following query:

    ?- time((numbers_tree([2,5,6,6], T),
             tree_op_expr_value(T, _, Expr, 17))).

This yields:

    % 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 .

It seems to work nicely. On backtracking, all solutions are generated. Note that this solution uses built-in rational numbers that are available in several Prolog systems.

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

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!

This was the problem for round 2 of the C International Conciseness Contest in early 1993. Submitted programs were to take on stdin a file consisting of one or more problem instances, where each instance consisted of three lines, and solve those there were solvable, and report as unsolvable those that were not.

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...)

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

    :- 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.

    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.