Getting possible product combinations of number in a list Prolog

user_15779043 0
Viewed 81

I am using constraint logic programming and I want to output a list with the product of the list (excluding the first element) is equal to the first element. For example,

[24 6 _ _] the output would be [24 6 1 4] or [24 6 4 1] or [24 6 2 2] etc. I am trying to solve something similar to sudoku but I am stuck on this step.

clpfd sudoku prolog list
2 Answers

Using foldl/2, you will need:

mul_(A, S0, S) :-
    S #= S0 * A.

And you can do:

?- N #= 24, length(Vs, 3), Vs ins 1..N, Vs=[6|_], foldl(mul_, Vs, 1, N), label(Vs).
user_144143240

For this problem, clpfd is far slower than a sensible alternative:

product(1, []).
product(Prod, [N|Lst]) :-
    between(1, Prod, N), 
    divmod(Prod, N, N1, 0),
    product(N1, Lst).

Results in swi-prolog:

?- length(L, 20), time(bagof(L, product(24, L), Ls)), length(Ls, Sols).
% 602,066 inferences, 0.065 CPU in 0.066 seconds (100% CPU, 9196344 Lips)
Sols = 30800

Vs

?- N #= 24, length(L, 20), L ins 1..N,
   time(bagof(L, (foldl(mul_, L, 1, N), label(L)), Ls)), length(Ls, Sols).
% 62,070,425 inferences, 2.783 CPU in 2.786 seconds (100% CPU, 22301363 Lips)
Sols = 30800
user_176283360
Related