How do you check the elements of a submatrix in Prolog

Question

I am trying to write a Shikaku solver in EclipsE Prolog. My contraints are defined as follow:

solve(Problemname):-
writeln("Start shikaku."),
problem(Problemname, Width, Height, Hints),
shikaku(Width, Height, Hints).

shikaku(Width, Height, Hints):- 
length(Hints, HintCount),
array_list(HintsArray, Hints),

% Prepare the matrix and assign an ID to every Hint (from 1 to HintCount)
dim(Matrix, [Width, Height]),
Matrix[1..Width,1..Height] :: 1..HintCount,

%flatten_array(Matrix,FlattenedMatrix),
(for(ID,1,HintCount), foreach((HintX, HintY, HintNumber), Hints), param(Width, Height, Matrix, HintsArray) do
    (   
        occurrences(ID, Matrix, HintNumber),
        L :: 1..Width, R :: 1..Width,
        T :: 1..Height, B :: 1..Height,

        % Hint coordinates are inside the rectangle.
        L #=< HintX,
        R #>= HintX,
        T #=< HintY,
        B #>= HintY,
        DeltaX #= R-L+1,
        DeltaY #= B-T+1,
        HintNumber #= DeltaX * DeltaY,

        Matrix[L..R,T..B] :: ID..ID
        %writematrix(Submatrix, DeltaX, DeltaY, HintsArray),

        %flatten(Submatrix, FlatSubmatrix), 
        %array_list(FlatSubmatrixArray, FlatSubmatrix),

        % Cell count in rectangle must equal HintNumber
        %length(FlatSubmatrix, HintNumber),

        % All cells in rectangle must have ID as value
        %FlatSubmatrixArray[1..HintNumber] :: ID    

    )
),

% Start searching
labeling(Matrix),

writematrix(Matrix, Width, Height, HintsArray). 

writematrix(Matrix, Width, Height, HintsArray):-
writeln("Writing as classic view:"),
(for(I, 1, Height), param(Matrix, Width, HintsArray) do
    write("["),
    Row is Matrix[I],
    (for(J, 1, Width), param(Row, HintsArray) do
        ID is Row[J],
        (_,_,Val) is HintsArray[ID],
        write(" "),
        write(Val),
        write(" ")
    ),

    writeln("]")
).

The line in comments should check if the submatrix going from L..R - T..B only contains elements that are equal to ID. How can this be done?

Running this gives an "instantiation fault in _3264{1 .. 3} =< 3"

edit1: full code

edit2 It seems that eclipse is not able to reduce the domain of the LR/TB variables to apply an instantiation. Is this a correct assumption? If so, how would this be solvable?

Aha, maybe the problem lies in the fact that you access Matrix for a subset of L..R, T..B, but those variables may not always be ground upon entering the line of code. You cannot specify ranges for array subsets that have a domain. A possibility could be to perform search after setting the LRTB variables' domain, but before setting the ID..ID domain to the Matrix subset. — SND, May 22 '16 at 09:01
Using ECLiPSe's built-in search/6, as you are doing while making a call to labeling/1. Only, instead of calling it after the loop, call it inside the loop between the domain instantiations of L..R and T..B, but before the line with Matrix[L..R,T..B] :: ID..ID. — SND, May 22 '16 at 09:11
Well, it runs :D does not return a solution although it should, but it's something. — JorenV, May 22 '16 at 09:16
Great :D ! Now that the problem is revealed, you can adapt the program. I guess it boils down to: either you set all constraints of all LRTB variables on beforehand, but don't use them yet to access Matrix inside the loop, or you perform the search inside the loop as you're doing now and can keep the Matrix calls there. However, note that calling search inside the loop will need to create different choice points for different solutions which might slow down execution when working with large domains. Always try to constrain your model as strong as possible/required to avoid unnecessary search. — SND, May 22 '16 at 09:25

SND · Accepted Answer · 2016-05-22T08:41:39.280

2

I haven't run your code, but looking at the documentation of the :: operator for instantiating domains, we see that it expects a lower and upper bound of the domain range. For your example, if you just want every number in a subset of an array to be equal to let's say 4, you could simply write the following:

Matrix[A..B,C..D] :: 4..4

EDIT

The error you are receiving is not triggered by that line of code. It gives an instantiation fault while comparing a domain variable with an integer. My guess is that you accidentally wrote =< instead of #=< somewhere in code that isn't included in this question, since the domain of {1..3} is in fact =< 3 and shouldn't give any error were constraint operators correctly used.

If you can't seem to figure out which line of code is producing the error, try performing a trace - it (almost) always reveals the cause. If you are using tkeclipse, a built-in tracer tool is available.

edited May 22 '16 at 08:41

answered May 22 '16 at 08:33

SND

1,552
2
16
29

changing :: ID to :: ID..ID returns with the same error – JorenV May 22 '16 at 08:36
I have amended the answer. – SND May 22 '16 at 08:42
see updated code. Tracing fails when reaching the Matrix :: ID..ID line for the second time. It seems that eclipse is not able to reduce the domain of the LR/TB variables to apply an instantiation – JorenV May 22 '16 at 08:52

How do you check the elements of a submatrix in Prolog

1 Answers1