2

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.

Improve this question
2

2 Answers 2

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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
Improve this answer

1 Comment

It is indeed slower, but now I'm starting to get the results in less than a minute. This was a big help, I'll try to refine the idea to see if I can get a better result. Thank you very much!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.