CODEWITHSUNDEEP
prologmagic-square
user3694499
user3694499

Reputation: 23

How to get a list of the Value of a number as the sum of 4 numbers in Prolog

I'm having trouble making this predicate work. The idea is to use diabolic([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) to obtain all the possible magic squares in that list.

At first I thought about using permutation/2 but it's hella slow for a list of 16 numbers.

Then I found an example here which uses an external library (clpfd) and has awesome performance, but I'm trying to solve it without any external library... so I tried something like this:

sum([X,Y,Z,W]) :-
  A = [1..16],
  member(X,A),
  member(Y,A),
  member(Z,A),
  member(W,A),
  X \== Y,
  X \== Z,
  X \== W,
  Y \== Z,
  Y \== W,
  Z \== W,
  34 is (X+Y+Z+W).

What I'm trying to do there is getting all the possible lists of different numbers which sum is 34 so I can then check which combination makes a magic square (in hopes of making it faster that using normal permutation.

Still, I'm getting an error about some Operator Expected in member(X,[1..16]), so maybe i'm doing something wrong. I'm pretty new to Prolog so I was hoping to get some help from you guys.

Thanks in advance.

Upvotes: 2

Views: 894

Answers (2)

MJBZA
MJBZA

Reputation: 5018

Look at the following link, I used one of the programs and it solved a same problem that I had for permutation:

prolog I have to make a program that calculates the magic matrix permutate

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

You are on the right track: enforce as soon as possible a constraint, to prune the search space.

The problem is how 'to split' the permutation process, to be able to prune results ASAP.

A simple minded way:

diabolic([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) :-
    N0=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],

    R1=[A,B,C,D],select_list(N0,R1,N1),sum_list(R1,34),
    R2=[E,F,G,H],select_list(N1,R2,N2),sum_list(R2,34),
    R3=[I,J,K,L],select_list(N2,R3,N3),sum_list(R3,34),
    R4=[M,N,O,P],select_list(N3,R4,[]),sum_list(R4,34),

    sum_list([A,E,I,M],34),
    sum_list([B,F,J,N],34),
    sum_list([C,G,K,O],34),
    sum_list([D,H,L,P],34),

    sum_list([A,F,K,P],34),
    sum_list([M,J,G,D],34).

select_list(X,[],X).
select_list(X,[H|T],Z) :- select(H,X,Y), select_list(Y,T,Z).

this is still much slower that CLP(FD), but could be a starting point...

edit simple code improvements.

The original performance:

?- forall(time(diabolic(L)),writeln(L)).
% 74,769,227 inferences, 23.739 CPU in 23.754 seconds (100% CPU, 3149688 Lips)
[1,2,15,16,12,14,3,5,13,7,10,4,8,11,6,9]
% 7,556,909 inferences, 2.396 CPU in 2.448 seconds (98% CPU, 3154252 Lips)
[1,2,15,16,13,14,3,4,12,7,10,5,8,11,6,9]
% 90,103,270 inferences, 28.475 CPU in 28.503 seconds (100% CPU, 3164265 Lips)
[1,2,16,15,13,14,4,3,12,7,9,6,8,11,5,10]
Action (h for help) ? aabort

Inlining select_list/3

select_(N0,[A,B,C,D],N1) :-
    select(A,N0,T0),
    select(B,T0,T1),
    select(C,T1,T2),
    select(D,T2,N1).

diabol_1([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) :-
    N0=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
    R1=[A,B,C,D],select_(N0,R1,N1),sum_list(R1,34),
    R2=[E,F,G,H],select_(N1,R2,N2),sum_list(R2,34),
    R3=[I,J,K,L],select_(N2,R3,N3),sum_list(R3,34),
    R4=[M,N,O,P],select_(N3,R4,[]),sum_list(R4,34),

    sum_list([A,E,I,M],34),
    sum_list([B,F,J,N],34),
    sum_list([C,G,K,O],34),
    sum_list([D,H,L,P],34),

    sum_list([A,F,K,P],34),
    sum_list([M,J,G,D],34).

we get a small improvement:

?- forall(time(diabol_1(L)),writeln(L)).
% 65,282,719 inferences, 21.137 CPU in 21.195 seconds (100% CPU, 3088524 Lips)
[1,2,15,16,12,14,3,5,13,7,10,4,8,11,6,9]
% 6,607,508 inferences, 2.074 CPU in 2.075 seconds (100% CPU, 3186362 Lips)
[1,2,15,16,13,14,3,4,12,7,10,5,8,11,6,9]
% 78,691,563 inferences, 24.914 CPU in 24.928 seconds (100% CPU, 3158505 Lips)
[1,2,16,15,13,14,4,3,12,7,9,6,8,11,5,10]
Action (h for help) ? aabort

inlining sum_list/2 we see a further small gain:

sum_([A,B,C,D]) :- A+B+C+D =:= 34.

diabol_2([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) :-
    N0=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
    R1=[A,B,C,D],select_(N0,R1,N1),sum_(R1),
    R2=[E,F,G,H],select_(N1,R2,N2),sum_(R2),
    R3=[I,J,K,L],select_(N2,R3,N3),sum_(R3),
    R4=[M,N,O,P],select_(N3,R4,[]),sum_(R4),

    sum_([A,E,I,M]),
    sum_([B,F,J,N]),
    sum_([C,G,K,O]),
    sum_([D,H,L,P]),

    sum_([A,F,K,P]),
    sum_([M,J,G,D]).

?- forall(time(diabol_2(L)),writeln(L)).
% 20,419,167 inferences, 10.425 CPU in 10.431 seconds (100% CPU, 1958699 Lips)
[1,2,15,16,12,14,3,5,13,7,10,4,8,11,6,9]
% 2,058,108 inferences, 1.046 CPU in 1.047 seconds (100% CPU, 1966993 Lips)
[1,2,15,16,13,14,3,4,12,7,10,5,8,11,6,9]
% 24,592,123 inferences, 12.462 CPU in 12.481 seconds (100% CPU, 1973394 Lips)
[1,2,16,15,13,14,4,3,12,7,9,6,8,11,5,10]
Action (h for help) ? aabort

Upvotes: 0

Related Questions