# Re: Prime Sums In A Grid

• From: Markus Triska <triska@xxxxxxxx>
• Date: Tue, 24 Feb 2009 20:57:37 +0100

LudovicoVan <julio@xxxxxxxxxxxxx> writes:

My attempted Prolog code is below, and I wouldn't know how to make it
any faster, considering also that the test for primality here is not
the significant bottleneck.

First a few general points: Some of the !/0 are unnecessary due to first
argument indexing. Second, there is a nice way to write transpose/2 such
that you can use first argument indexing there as well and need no !/0,
left as an exercise. Further, get_row/4 and get_rows/4 seem unnecessary:
You can use lists of lists in the first place and use append/2 (!) to
get the right representation for the CLP(FD) predicates. Instead of
fail/0, there is of recent the much nicer false/0 in SWI. Instead of
label([X]), you can use indomain(X).

Now how to make it run faster? In the previous solution, the constraint
solver is not used to its fullest advantage: Instead, it is essentially
a generate-and-test approach, where sums are generated and then tested
for primality. The final label/1 call in matrix/2 is not even needed in
that approach: All elements are already instantiated.

Suppose we have the following simplistic sieve:

primes_upto(N, Ps) :-
numlist(2, N, Ps0),
sieve(Ps0, Ps).

sieve([], []).
sieve([P|Ns0], [P|Rest]) :-
sublist(no_multiple(P), Ns0, Ns),
sieve(Ns, Rest).

no_multiple(P, N) :- N mod P =\= 0.

And in matrix/2 use:

...
MaxSum is Square * Side,
primes_upto(MaxSum, Primes),
list_to_domain(Primes, PD),
constraint_tuples(Rows, PD),
constraint_tuples(Cols, PD),
...

where the auxiliary predicate list_to_domain/2 is defined like:

list_to_domain([], 1..0).
list_to_domain([L|Ls], L \/ D) :-
list_to_domain(Ls, D).

And rewrite constraint_tuples/2 as:

constraint_tuples([], _).
constraint_tuples([Tuple| Tuples], Primes) :-
sum(Tuple, #=, Sum),
Sum in Primes,
constraint_tuples(Tuples, Primes).

You get a faster version:

%?- time(matrix_output(4)).
%@ 1, 2, 3, 5,
%@ 4, 6, 7, 12,
%@ 8, 9, 15, 11,
%@ 10, 14, 16, 13,
%@ % 47,966 inferences, 0.01 CPU in 0.01 seconds (67% CPU, 4796600 Lips)
%@ true.

%?- time(matrix_output(12)).
%@ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13,
%@ 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 26,
%@ 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 39,
%@ 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 50,
%@ 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61,
%@ 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72,
%@ 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 89,
%@ 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95,102,
%@ 96, 97, 98, 99,100,101,103,104,105,106,107,113,
%@ 108,109,110,111,112,114,115,116,117,118,119,124,
%@ 120,121,122,123,125,126,127,129,140,143,131,142,
%@ 135,134,133,139,141,132,144,138,137,128,130,136,
%@ % 5,068,426 inferences, 1.24 CPU in 1.27 seconds (97% CPU, 4087440 Lips)
%@ true.

And then it also makes sense to try different labeling options.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
.