CODEWITHSUNDEEP
matrixprolog
mmgro27
mmgro27

Reputation: 515

Generate a matrix for a puzzle solver prolog program

I have written a prolog program to solve and display the solution for a sudoku like puzzle. At first I used something like this if the grid was e.g. 4x4:

main:-
     Matrix = [[_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]],
     solve_puzzle(Matrix),
     display_matrix(Matrix).

But I'd like to be able to set the size of the matrix so then I wrote this:

generate_list(N, [ ]) :-
    N =< 0, !.
generate_list(N, [_ | T]) :-
    N > 0,
    N2 is N - 1,
    generate_list(N2, T).

generate_matrix(_, N, []) :-
    N =< 0, !.
generate_matrix(M, N, [R|T]) :-
    generate_list(M,R),
    N2 is N - 1,
    generate_matrix(M, N2, T).

And then I could do:

main:-
    Rows = 4, Columns = 4,
    generate_matrix(Columns,Rows,Matrix),
    solve_puzzle(Matrix),
    display_matrix(Matrix).

But this seems to slow down my program. Is there a better way to generate an N x M matrix?

Upvotes: 2

Views: 2027

Answers (1)

lurker
lurker

Reputation: 58234

A combination of length/2 and maplist/2 works well here:

length_list(N, List) :- length(List, N).

generate_matrix(Cols, Rows, Matrix) :-
    length_list(Rows, Matrix),
    maplist(length_list(Cols), Matrix).

I defined length_list/2 to put the length argument first in order to use it in maplist/2.

length/2 is relational, so when you call length/2 with the length instantiated (say, N), but with the list argument as variable, it results in [_,_, ..., _] with N elements. So the first length_list creates a list, Matrix, that looks like, [_, _, _, ..., _] with length Rows. Then the following maplist/2 will, for each element (row R) of Matrix, call length_list(Cols, R) which yields in place of each _ a list, [_, _, ..., _] of length Cols.

maplist/2 will call the first argument as a predicate on each element of the second argument, a list. Since we're giving it length_list(Cols), it is calling, for each element in [_, _, ..., _], call(length_list(Cols), _), which is equivalent to, call(length_list(Cols, _)), which will instantiate _ with [_, _, ..., _], an anonymous variable list with length Cols.

I did some quick timing checks using SWI Prolog's time/1 and the above approach appears to be significantly faster.

Upvotes: 5

Related Questions