Prolog: generate solution according to the original list

Question

I am a beginner in Prolog, and I've searched a lot but cannot solve the problem. The question is giving me a list given the head of the list, such as [20,_,_,_].

The length of the list is unknown. For example, it could be [30,_,_,_,_,_].
the _ is the distinct factor, which only consists of the digit from 1 to 9. For example, [20,_,_,_] could generate [1,4,5] and its combination.
The list could be filled with a number first. For example, [20,_,4,_]. The output would be still [1,4,5] and [5,4,1].

What I've tried is to rip off the head of the list, and try to generate the rest of the elements back to the original list, but I failed, and cannot understand the debugger and its trace information.

removeHead([Head|Tail],Tail).

get_head_element([],_).
get_head_element([Head|Rest],Head).

divide(1,[],_).
divide(Number,[Head|List],Result):-
    0 is mod(Number,Head),
    Quotient is Number/Head,
    divide(Quotient,List,Result).

solve_multiply(Row,RestRow):-
    get_head_element(Row, Goal),
    removeHead(Row,RestRow),
    all_distinct(RestRow),
    RestRow ins 1..9,
    divide(Goal,RestRow,RestRow).

Any hint of resource that I can keep approaching this question? Thanks.

EDIT: I think it another way that the elements multiplied in the list would be the same at the head, so I wrote a multiply predicate.

%% multiply(+List,-Result)
%
% for calling the multiply(+List,+PrevResult,+Result) with accumulator set to 1
multiply(List,Result):-
    multiply(List,1,Result).

%% multiply(+List,+PrevResult,+Result)
%
% multiply each element in the list
multiply([Element|RestList],PrevResult,Result):-
    NextResult is PrevResult * Element,
    multiply(RestList,NextResult, Result).

%% multiply([], -Result, -Result).
%
% multiply predicate stops when all the elements have been multiplied
multiply([], Result, Result).

%% solve_multiply(+Row,-RestRow)
solve_multiply(Row,RestRow):-
    get_head_element(Row, Goal),
    removeHead(Row,RestRow),
    RestRow ins 1..9,
    multiply(RestRow,Goal), % get the Arguments not sufficiently instantiated message
    all_distinct(RestRow).

Why the clpfd tag. I don't see any use of clpfd. Which Prolog are you using, e.g. SWI-Prolog. — Guy Coder
As a suggestion think about creating a conical form for the result and how the expected answer and the generated answers can be converted and compared to a conical form. — Guy Coder
I have not written any code to test my ideas as I am busy with something else and only posted during the few seconds of waiting. I think you will also need something like Subsets in Prolog and Deleting anonymous variables in a list — Guy Coder
Another way would be to just use member/2 and remove the known factors of the smaller list from the larger list of factors and see if the list is empty when done. Then you know all of the factors from the smaller list are in the larger list. — Guy Coder

Woden Woden · Accepted Answer · 2021-04-11T08:54:27

The simplest way to find the solution is to:

Compare the multiplied elements to the head element.
Use the constraint provided by clpfd.

Therefore, the code should be:

multiply(List,Result):-
    multiply(List,1,Result).

multiply([Element|RestList],PrevResult,Result):-
    NextResult #= PrevResult * Element, % constraint that works for both side ?X #= ?Y
    multiply(RestList,NextResult, Result). % tail recursion

multiply([], Result, Result).

solve_multiply(Row,RestRow):-
    get_head_element(Row, Goal),
    removeHead(Row,RestRow),
    RestRow ins 1..9,
    multiply(RestRow,Goal),
    all_distinct(RestRow).

When calling the solve_multiply([20,_,_,_],X), labeling([],X). The result is:

X = [1, 4, 5] ;
X = [1, 5, 4] ;
X = [4, 1, 5] ;
X = [4, 5, 1] ;
X = [5, 1, 4] ;
X = [5, 4, 1] ;
false.

When calling the solve_multiply([20,_,1,_],X), labeling([],X). The result is:

X = [4, 1, 5] ;
X = [5, 1, 4].

Prolog: generate solution according to the original list

1 Answers