Mathematics × Programming Competition #5 - Prolog solution

armandocat (63)in #contest • 7 years ago

A week ago, @kenchung posted a contest with this funny puzzle to solve. I'm a super nerd cat 😼, so I decided to try and solve it using Prolog, a logic programming language that is very suitable for solving this kind of problem.

Here is a link to the original post:
https://steemit.com/contest/@kenchung/question-mathematics-programming-competition-5
I suggest you to follow @kenchung if you like these kind of puzzles.

Basicaly the idea with Prolog is that one can just state the facts, what you want to achieve (in this case the relations you want the variables to have with each others) and then the Prolog engine will attempt to find a solution by trying all the different possibilities (in a smart way).

I will cite wikipedia here: (https://en.wikipedia.org/wiki/Prolog)

In Prolog, program logic is expressed in terms of relations, and a computation is initiated by running a query over these relations. Relations and queries are constructed using Prolog's single data type, the term. Relations are defined by clauses. Given a query, the Prolog engine attempts to find a resolution refutation of the negated query. If the negated query can be refuted, i.e., an instantiation for all free variables is found that makes the union of clauses and the singleton set consisting of the negated query false, it follows that the original query, with the found instantiation applied, is a logical consequence of the program. This makes Prolog (and other logic programming languages) particularly useful for database, symbolic mathematics, and language parsing applications.

Now, let's dive into the problem and its solution 😼

Question

Complete the 4 × 4 puzzle above using the numbers 1 to 16 without repetition, subject to the following constraints:

A, B, J, K can only be filled with the numbers 2, 4, 6 or 8
E + F = 26
K + O = 9
B + K = 14
A + L = 9
C + I = 25
A + G = 13
C + P = 24
B + M = 9
A + K = 12
D + E = 25
| E - N | = 4

Working out the solution using Prolog

Main rule

The first thing I will do when I'm presented with a problem like this one, is to write down the rule that needs to be satisfied from the solution:

run(Sol):- 
    Sol = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P],
    N1=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
    check_number(A, [2,4,6,8], N1, N2),
    check_number(B, [2,4,6,8], N2, N3),
    check_number(J, [2,4,6,8], N3, N4),
    check_number(K, [2,4,6,8], N4, N5),
    check_add(B, K, 14, N5, N6),
    check_add(E, F, 26, N6, N7),
    check_add(K, O, 9, N7, N8),
    check_add(A, L, 9, N8, N9),
    check_add(C, I, 25, N9, N10),
    check_add(A, G, 13, N10, N11),
    check_add(C, P, 24, N11, N12),
    check_add(B, M, 9, N12, N13),
    check_add(A, K, 12, N13, N14),
    check_add(D, E, 25, N14, N15),
    check_abs_diff(E, N, 4, N15, N16),
    ensure_number(H, N16, []).

Now I will go into detail explaining what is the meaning of each line.
With the first conditions Sol = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P] and N1=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] I'm defining a list of variables and the possible numbers each variable can take. There are 16 variables from A to P, that can have values between 1 and 16.

The next line, check_number(A, [2,4,6,8], N1, N2), and the following lines for the other variables B, J and K, check that the variables have values in the list [2,4,6,8], as indicated in the constraint #1.
I will explain why this rule and others has N1 and N2 at the end later.
This rule basically stops prolog if the number chosen for the variable
is not 2, 4, 6 or 8. If prolog would have chosen the value 5 for the variable, it will stop here and go back to try out other values. If the value is for instance 4, everything is fine, and prolog can go on e look at the following rules.

Now, we need to express the constraints #2 to #11, and for this we will use the rule check_add.
For instance, check_add(B, K, 14, N5, N6) will check that the choosen values for the variables B and K satisfy the constraint #4 (B + K = 14).

Then there is the constraint #12, | E - N | = 4. For this we need to check that the absolute value of E - N is 4. We can use create a rule check_abs_diff(E, N, 4, N15, N16) that will check that the constraint is satisfied.

The last rule of the program is ensure_number(H, N16, []). This is needed because there is no constraint for the variable H in the definition of the problem, so prolog doesn't know what value to assign to it. But, after having check all the other constraints, we know that just one number is left out. So we can just say that H is the last number remaining that has not been assigned to other variables.

Helper rules

Let's look now rule by rule how they are implemented.
I will start from ensure_number, used on the last line of the main rule of the program.

% Ensure a number is bound
ensure_number(N, Numbers, Numbers):- nonvar(N).
ensure_number(N, NumbersIn, NumbersOut):- var(N), select(N, NumbersIn, NumbersOut).

What this rule wants to achieve, is to make sure that the variable N (first argument of the rule) has a value bound to it, and this value is one of the values in the list of allowed numbers.
So, if the variable has already a value (this is checked with the nonvar function), everything is fine, prolog doesn't have to do anything.
Instead, if the variable is not bound, it needs to select a number from NumbersIn (the second argument). NumbersOut (the third argument) will be a new list of the allowed number without the chosen number for the variable. In this way, we can be sure that if a variable has a value, no other variables will be allowed to have that same number.

Let's try with an example. If run the query

ensure_number(N, [1,2,3], ListWithoutN).

Prolog will assign to N (that is a variable that is not yet assigned to a number) the value 1, 2 or 3. For each choice, it will also assign to ListWithoutN a new list, created from the list [1,2,3] by removing the number that has been assigned to N.
Prolog will list all the possible solution:

N = 1
ListWithoutN = [2, 3]

N = 2
ListWithoutN = [1, 3]

N = 3
ListWithoutN = [1, 2]

"Check add" rule

This rule will check that given to variables V1 and V2 and a result R, the constraint V1 + V2 = R is satisfied.

% Check V1 + V2 = R
check_add(V1, V2, R, NumbersIn, NumbersOut):-
    ensure_number(V1, NumbersIn, N2),
    ensure_number(V2, N2, NumbersOut),
    S is V1 + V2, S = R.

First of all, the rule needs to check that the variables V1 and V2 have values assigned to them, using the previously defined rule ensure_number. Then, it will compute the sum S, and check that S = R.

"Check absolute difference" rule

This rule will check that given to variables X and Y and a result R, the constraint | X - Y | = R is satisfied.

% Check abs(X-Y) = R
check_abs_diff(X, Y, R, NumbersIn, NumbersOut):- 
    ensure_number(X, NumbersIn, N2),
    ensure_number(Y, N2, NumbersOut),
    D is abs(X - Y), D = R.

Similarly to before, the rule needs to check that the variables X and Y have values assigned to them using the rule ensure_number. Then, it will compute the absolute difference D, and check that D = R.

"Check number" rule

This rule will check a that given variable X has one of the values in the list Allowed.

% Check one of the allowed number
check_number(X, Allowed, NumbersIn, NumbersOut):-
    ensure_number(X, NumbersIn, NumbersOut),
    member(X, Allowed).

Similarly to before, the rule needs to check that the variable X has a value assigned using the rule ensure_number. Then, it will just say that X is a "member" of the list Allowed.

Running the program

You run the program by writing the query

run(Sol).

There is only one result. Prolog will output:

Sol = [4, 6, 13, 15, 10, 16, 9, 7, 12, 2, 8, 5, 3, 14, 1, 11]

You can see and run the program and play with it here:
https://swish.swi-prolog.org/p/HTegnvoO.pl

Conclusion

As you can see, Prolog is different for other imperative programming languages. Here, you need to express what you want to happen with a set of rules that needs to be satisfied, you don't care how this is computed, the Prolog engine will take care of the how.

Hope you like this post! Let me know in the comments if you have any question or if you have a better way to solve the problem using Prolog or other programming languages!

Armando
🐾

#cn-contest #cn #math #programming