Prolog Applying Constraints to Original List Items in Matrix

Question

I am currently working on a project that involves a matrix. I am stuck in my attempt to apply constraints to specific elements in my matrix. This is my matrix and domain definitions of the main class/predicate. So, the first 3 predicates are just creating the matrix and defining the domains while the last 2 predicates labels the different variables in regards to the domain and prints it out.

test(Solution, N) :-
    length(Solution,8),
    maplist(length_(8), Solution), %The variables
    maplist(define_domain, Solution), %The domains
    constraint(Solution),
    maplist(labeling([]), Solution), %Labeling the variables
    maplist(print_row, Solution).

length_(Length, List) :- length(List, Length).

define_domain(X):- X ins 0..9.

ww(X):-
    write(X).

print_row(Row):-
     %nested maplist call so it works on each element in the
    maplist(ww, Row),
    nl.

So, the constraints predicate which applies the constraint on my variables is where I am having problems. I have some facts that I need to capture so I tried using findall to loop through all the facts and use them to determine the which elements inside the list of the matrix that I need to apply the constraints to. The facts contains the row, column and length.

The nested findall predicate call uses row to determine which list inside the matrix, column to determine the index of the element of the that list to take and extracting a sublist based on the index of the element and its length. The outer findall predicate finds all the position predicates and collects all the sublists. Therefore, I have a collection of sublists contains the elements of the matrix where constraint needs to be applied. The constraint is applied in the constraint_apply predicate.

However, I discovered that the findall predicate creates copies of the original list instead of using the actual elements/variables in the original list after struggling for many hours. So, all the constraints that are being applied only affects the copies and not the originals.

Right now, I am thinking that maybe I am using the findall predicate wrongly to apply the constraints and trying out different ways to use it.

I would be grateful if someone could explain to me a better way to propagate my constraints in this scenario.Any helps/tips will be appreciated. How would you apply the constraints to the original list and elements in the matrix above?

constraint_apply([]).
constraint_apply([X|Xs]):-
    sum(X, #<, 10),
    all_different(X),
    constraint_apply(Xs).

%Extract a slice from the lsit

constraint(Xs):-
       findall(X, (position(R, C, L), End is C+L-1,
 findall(Y, (nth1(R, Xs, N),between(C, End, M), nth1(M, N,Y)), X)), Row),
       constraint_apply(Row).

score 0 · Accepted Answer · answered Mar 29 '15 at 05:08

0

I had a similar problem, and I solved using bagof/3 instead of findall/3. I cannot test your code, so here is just a hint to the needed syntax

constraint(Xs):-
    bagof(X, R^C^L^End^(
        position(R, C, L),
        End is C+L-1,
        bagof(Y, N^M^(nth1(R, Xs, N), between(C, End, M), nth1(M, N, Y)), X)
    ), Row),
    constraint_apply(Row).

answered Mar 29 '15 at 05:08

CapelliC

59,646
5
47
90

Thanks Mr CapelliC, it works and this time I can even see the constraints being propagated in gtrace. What I am interested to know now is that why does the bagof predicate work where findall fails? Is it retaining the variables of the original list as it produces solution 1 by 1 (which is why the ^ is needed)? – t22000 Mar 29 '15 at 12:34
@t22000: glad I can help. bagof/3 allows finer control wrt findall/3. It's not really easy to explain, mmm ... the ^ symbol declares the **aggregating variables**, that ends up - functionally massaged - in the result list. I think you could also be interested in [this my other answer](http://stackoverflow.com/questions/8458945/optimizing-pathfinding-in-constraint-logic-programming-with-prolog/8530427#8530427). More low level: bagof doesn't bind / copy variables – CapelliC Mar 29 '15 at 16:45
Thanks a lot of your reply. I shall read your other answer over dinner. :) It is amazing how the finer details with the predicates make so much difference. By the way, I hope you don't mind but I have another quick question. Is there another way besides using findall or bagof to loop through facts such as position(R, C, L)? This is because I find that the solution takes about 6 seconds to produce even with cuts so I am just curious. I tried using failure driven loops to access each position predicate but it seemed like the constraints does't propagate upwards like findall. – t22000 Mar 29 '15 at 18:29
@t22000: beware, avoid cuts as far they are **really** required. AFAIK, they don't play a significant role in CLP(FD) programming. Try hard instead to keep the code as simpler as you can, and cuts are - almost - never easy. IMHO that's the right approach to *declarative programming*, that CLP(FD) contribute so much – CapelliC Mar 29 '15 at 18:44
1

Thanks for the advice and it was helpful as I am new to the declarative programming. I played closer attention to the speed and I noticed that cuts did not do much as well. I was able to get the time that the solution takes down to 0.04secs by re-arranging my predicates and refactoring the algorithm a little so I am satisfied now. :D – t22000 Mar 31 '15 at 13:03

Prolog Applying Constraints to Original List Items in Matrix

1 Answers1