# 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/

.

**Follow-Ups**:**Re: Prime Sums In A Grid***From:*LudovicoVan

**Re: Prime Sums In A Grid***From:*LudovicoVan

**Re: Prime Sums In A Grid***From:*LudovicoVan

- Prev by Date:
**DEADLINE EXTENSION: IEEE TKDE Special Issue on Rules** - Next by Date:
**Re: Prime Sums In A Grid** - Previous by thread:
**DEADLINE EXTENSION: IEEE TKDE Special Issue on Rules** - Next by thread:
**Re: Prime Sums In A Grid** - Index(es):