As a beginner, I am trying to solve a matrix problem, in which the solution is either the summation or the multiplication of the distinct digit in the matrix. For example,[[14,_,_,_],[15,_,_,_],[28,_,1,_]]. The predicate should generate the solution according to the matrix. However, I bumped into a problem that my combined predicate failed, but each of them succeeded independently.
I broke the problem down to summation and multiplication. Therefore, using clpfd library, and some predicates, for summation:
removeHead([Head|Tail],Tail).
get_head_element([],_).
get_head_element([Head|Rest],Head).
solve_sum(Row,RestRow):-
get_head_element(Row, Goal),
removeHead(Row,RestRow),
RestRow ins 1..9,
all_distinct(RestRow),
sum(RestRow, #=, Goal).
For multiplication:
multiply(List,Result):-
multiply(List,1,Result).
multiply([Element|RestList],PrevResult,Result):-
NextResult #= PrevResult * Element,
multiply(RestList,NextResult, Result).
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).
Both solve_sum and solve_multiply works for a single row, but here I combine these two predicates to:
solve_row_sum_or_multiply([],_).
solve_row_sum_or_multiply([HeadRow|Matrix],Solution):-
maplist(all_distinct,Matrix),
get_head_element(HeadRow,Goal),
( Goal >= 25
-> solve_multiply(HeadRow,Solution),
write(Solution)
; ( solve_sum(HeadRow,Solution),
write(Solution)
; solve_multiply(HeadRow,Solution),
write(Solution))
),solve_row_sum_or_multiply(Matrix,Solution).
When I use the solve_row_sum_or_multiply([[14,_,_,_],[15,_,_,_],[28,_,_,_]],X), it will give me the possible combinations. However, when solve_row_sum_or_multiply([[14,_,_,_],[15,_,_,_],[28,_,1,_]],X), it gave me false, but there's a solution possible there, such as [[14,7,2,1],[15,3,7,5],[28,4,1,7]].
I am wondering what could be wrong. Any help is highly appreciated!
EDIT
The problem is inside the combined predicate, and it's better to write the predicate which the answer suggests instead of a nested if-then-else predicate.
Let's review this code.
intro code
:- use_module(library(clpfd)).
% ---
% Make sure you see all the information in a list printed at the
% toplevel, i.e. tell the toplevel to not elide large lists (print
% them in full, don't use '...')
% ---
my_print :-
Depth=100,
Options=[quoted(true), portray(true), max_depth(Depth), attributes(portray)],
set_prolog_flag(answer_write_options,Options),
set_prolog_flag(debugger_write_options,Options).
:- my_print.
multiply/2
Recode the multiply/2 predicate so that it can be read more easily. Add test code to make sure it actually does what we think it does:
% ---
% Set up constraint: all the elements in List, multiplied
% together, must yield Result. If the List is empty, the
% Result must be 1.
% ---
multiply(Factors,Product):-
multiply_2(Factors,1,Product).
multiply_2([Factor|Factors],PartialProduct,Product):-
PartialProduct2 #= PartialProduct * Factor,
multiply_2(Factors,PartialProduct2,Product).
multiply_2([],Product,Product).
solve_multiply([Product|Factors]):-
Factors ins 1..9,
multiply(Factors,Product),
all_distinct(Factors).
% ---
% Testing
% ---
:- begin_tests(multiply).
test(1) :-
multiply([X,Y,Z],6),
[X,Y,Z] ins 1..9,
X #=< Y, Y #=< Z,
bagof([X,Y,Z],label([X,Y,Z]),Bag),
sort(Bag,BagS),
assertion(BagS == [[1, 1, 6], [1, 2, 3]]).
test(2) :-
multiply([],Result),
assertion(Result == 1).
test(3) :-
multiply([X,Y],3),
[X,Y] ins 1..9,
X #=< Y,
bagof([X,Y],label([X,Y]),Bag),
sort(Bag,BagS),
assertion(BagS == [[1,3]]).
test(4) :-
solve_multiply([6,X,Y,Z]),
bagof([X,Y,Z],label([X,Y,Z]),Bag),
sort(Bag,BagS),
assertion(BagS == [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]).
test(5) :-
solve_multiply([362880,F1,F2,F3,F4,F5,F6,F7,F8,F9]),
F1 #=< F2,
F2 #=< F3,
F3 #=< F4,
F4 #=< F5,
F5 #=< F6,
F6 #=< F7,
F7 #=< F8,
F8 #=< F9,
bagof([F1,F2,F3,F4,F5,F6,F7,F8,F9],label([F1,F2,F3,F4,F5,F6,F7,F8,F9]),Bag),
sort(Bag,BagS),
assertion(BagS == [[1,2,3,4,5,6,7,8,9]]).
test(6,fail) :-
solve_multiply([-1,X,Y,Z]).
:- end_tests(multiply).
solve_sum/1
For summation, after simplifying and re-coding to Prolog's "pattern matching" style instead of (for want of a better word) "Algol calling style" as is used in the original the question (which confused me greatly I have to say).
This looks ok too. Note that the predicate solve_sum/1 is quite different-in-argument-style from multiply/2 It is better - and easier on the reader (and oneself) - if one keeps the same calling conventions.
solve_sum([Sum|Terms]):-
Terms ins 1..9,
all_distinct(Terms),
sum(Terms, #=, Sum).
% ---
% Testing
% ---
:- begin_tests(sum).
test(0) :-
solve_sum([0]).
test(1) :-
solve_sum([6,X,Y,Z]),
X #=< Y, Y #=< Z,
bagof([X,Y,Z],label([X,Y,Z]),Bag),
sort(Bag,BagS),
assertion(BagS == [[1, 2, 3]]).
test(2) :-
solve_sum([9,X,Y,Z]),
X #=< Y, Y #=< Z,
bagof([X,Y,Z],label([X,Y,Z]),Bag),
sort(Bag,BagS),
assertion(BagS == [[1,2,6],[1,3,5],[2,3,4]]).
test(3,fail) :-
solve_sum([1,_X,_Y,_Z]).
:- end_tests(sum).
A printing predicate to get nice results
Prolog makes it easy to construct arbitrary structures "on the fly", one just has to stipulate exactly how the structure shall look.
Our "solution" is:
row(Result,Op,RowValues) where Result is the left-hand-side of an equation, Op is one of add or mult and RowValues is a list with the values found for the values in the equation.print_solution([]).
print_solution([Labeling|Labelings]) :-
format("---~n"),
print_rows_of_solution(Labeling),
format("---~n"),
print_solution(Labelings).
print_rows_of_solution([]).
print_rows_of_solution([row(Result,Op,RowValues)|Rows]) :-
print_row(Result,RowValues,Op),
print_rows_of_solution(Rows).
print_row(Result,[RowEntry|RowEntries],Op) :-
format("~q = ~q",[Result,RowEntry]),
print_row_2(RowEntries,Op).
print_row_2([RowEntry|RowEntries],Op) :-
((Op == mult) -> OpChar = '*'
; (Op == add) -> OpChar = '+'
; OpChar = '?'),
format(" ~q ~q",[OpChar,RowEntry]),
print_row_2(RowEntries,Op).
print_row_2([],_) :-
format("~n").
solve_row_sum_or_multiply/2
This has been modified to also collect the operation selected in a second argument (a list).
Note that the "maplist-all-distinct over the matrix" is not done here because that seems wrong.
solve_row_sum_or_multiply([],[]).
solve_row_sum_or_multiply([Row|MoreRows],[mult|Ops]) :-
Row = [X|_Xs],
X >= 25,
solve_multiply(Row), % we now have imposed a product constraint on the current Row
solve_row_sum_or_multiply(MoreRows,Ops).
solve_row_sum_or_multiply([Row|MoreRows],[add|Ops]) :-
Row = [X|_Xs],
X < 25,
solve_sum(Row), % we now have imposed a sum constraint on the current Row
solve_row_sum_or_multiply(MoreRows,Ops).
solve_row_sum_or_multiply([Row|MoreRows],[mult|Ops]) :-
Row = [X|_Xs],
X < 25,
solve_multiply(Row), % alternatively, we now have imposed a product constraint on the current Row
solve_row_sum_or_multiply(MoreRows,Ops).
And finally a "main" predicate
In trial_run/1 we stipulate that all variables except X32 be distinct and that X32 be 1. If X32 were in the "distinct set", none of the variables could take on the value 1 - there is no solution in that case.
We also impose a sorting to get only a set of "canonical" solutions:
We collect all possible solutions for solving and labeling using bagof/3:
trial_run(Solutions) :-
all_distinct([X11,X12,X13,X21,X22,X23,X31,X33]),
X32=1,
X11 #=< X12, X12 #=< X13,
X21 #=< X22, X22 #=< X23,
X31 #=< X33,
% multiple solutions solving x labeling may exist; collect them all
bagof(
[
row(14,Op1,[X11,X12,X13]),
row(15,Op2,[X21,X22,X23]),
row(28,Op3,[X31,X32,X33])
],
(
solve_row_sum_or_multiply( [[14,X11,X12,X13],[15,X21,X22,X23],[28,X31,X32,X33]], [Op1,Op2,Op3] ),
label([X11,X12,X13,X21,X22,X23,X31,X32,X33])
),
Solutions).
Does it work?
Apparently yes, and there is only one solution:
?- trial_run(Solutions),print_solution(Solutions).
---
14 = 2 + 3 + 9
15 = 1 + 6 + 8
28 = 4 * 1 * 7
---
Solutions = [[row(14,add,[2,3,9]),row(15,add,[1,6,8]),row(28,mult,[4,1,7])]].