Generate a matrix for a puzzle solver prolog program

Question

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?

If you want to create a list of a given size, N, just use length(List, N). — lurker
It is strange that you should be able to notice (or even measure) a slowdown of your program because of this code. Can you show the timings you got? — user1812457
@Boris makes an excellent point. Are you creating a very large number of small matrices, or one or a few very large ones? Or a lot of large ones? :) — lurker

lurker lurker · Accepted Answer · 2015-03-21T14:37:02

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.

Generate a matrix for a puzzle solver prolog program

1 Answers