Search code examples
listprologsudokudeclarative

Prolog: split a list into a list of N lists containing N items each


I've been searching through the many existing Prolog questions on SO relevant to splitting but couldn't find one as generic as the one that I want. I'd like to point out that I've been able to split lists into lists of 2/3/4 elements by using 2/3/4 variables piped before a list variable. This question is different from that only because of its genericness.

So, my list will always contain N*N items, N being unknown beforehand(usually will vary from 4 to 36, yes N is also a perfect square). I want to split it into a list of N lists containing N items each because that'll allow me to treat it as a matrix, hence allowing to transpose and certain operations of that sort. I haven't really been able to get too far with the logic because I'm relatively new to declarative programming; please see below my incomplete(faulty) attempt:

listmodel(1,L):- L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16].
size(L,N) :- length(L,N1), N is round(sqrt(N1)).

% add_tail(+Liste, +Element, -ResultantList)
add_tail([],L,[L]).
add_tail([X|L1],L2,[X|LI]):-add_tail(L1,L2,LI).

% partition the list containing N*N items into a list of N lists containing N elements each.
% part(+Liste, +Size, -ResultantList)
part([],_,DL).
part(L,N,DL) :-
    length(P,N), % P(refix) initialized
    append(P,S,L), % S(uffix) contains rest of L, using append in (-,-,+) mode
    add_tail(DL,P,DL1), %add P(first N elements) as first element of DL.
    part(S,N,DL1).

Now running ?- listmodel(1,L),size(L,N),part(L,N,DL). will produce DL=[] because that is what it gets initialized to in the first add_tail call in the part predicate. I can't seem to figure out how to store all elements in a list that's preserved through the recursion.

Any help/direction of any kind will be appreciated. I'm stuck here since over 23 hours 10 minutes now.

Thanks.


Solution

  • This should do it:

    part([], _, []).
    part(L, N, [DL|DLTail]) :-
       length(DL, N),
       append(DL, LTail, L),
       part(LTail, N, DLTail).
    

    Base case is first/last arguments are empty lists.

    Recursive step takes a fresh list of N elements, takes the first N elements from L (which will be one of the items of the third argument) and calls recursively.