Prolog: Optimizing a puzzle solver

Question

I am currently solving a specific kenken problem, and I notice it takes about 5 seconds to solve. This is for a smaller puzzle. However, I also need to solve a larger one, and I am concerned that the solution will take far too long to find. Here is the most relevant parts of my code (I have removed redundant parts, they are of the expected form):

getlarger(First, Second, First) :- First >= Second.
getlarger(First, Second, Second) :- First < Second.

getsmaller(First, Second, Second) :- First >= Second.
getsmaller(First, Second, First) :- First < Second.

subtractsmallerfromlarger(First, Second, Result) :- getlarger(First, Second, Larger), 
    getsmaller(First, Second, Smaller), Result is Larger - Smaller.

intdividelargerbysmaller(First, Second, Result) :- getlarger(First, Second, Larger),
getsmaller(First, Second, Smaller), Result is Larger // Smaller.

groupof4(List) :- nodups(List).

allrowsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :-
    groupof4([X1, X5, X9, X13]), groupof4([X2, X6, X10, X14]), %snip....

allcolumnsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :-
    groupof4([X1, X2, X3, X4]), groupof4([X5, X6, X7, X8]), %snip....

validnumbers4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :-
    validnumber4(X1), validnumber4(X2), %.....

kenken([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :-
    %snip...
    validnumbers4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]),
    X5 * X1 * X2 =:= 2,
    %Additional Arithmetic contraints removed
    intdividelargerbysmaller(X11, X15, 2), %Dividend =:= 2,
    subtractsmallerfromlarger(X12, X16, 3), %Difference =:= 3,
    X13 * X14 =:= 6,
    allcolumnsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]),
    allrowsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]).

For the already defined values, I use the syntax: X1 is 5, and I put this at the top of my code thinking that it would speed up lookup.

Without having to make my code drastically complex, are there any spots where I can make it somewhat more efficient?

Also, I noticed that changing the intdividelargerbysmaller and subtractsmallerfromlarger "Result is" to "Result =" makes the query take a very long time / not solve, whereas if I use a variable in the third slot it solves with both.

Additionally I noticed that queries take a very long time if I move the row and column checking up to near the beginning.

mat mat · Accepted Answer · 2013-11-24T23:34:31

You appear to be using a generate-then-test approach, which first generates candidates and then checks whether they are valid solutions.

It is much more efficient to use constraints for this task. Consider using finite domain constraints, which are provided by library(clpfd) in SWI-Prolog.

Constraints allow you to declaratively state all requirements even before you search for concrete solutions. They can filter inconsistent elements before and during the search, which typically yields tremendous performance improvements.

Prolog: Optimizing a puzzle solver

1 Answers