Search code examples
performanceprolog

Where is the source of my time out error (swi-prolog)?


I am having difficulty finding the source of my time-out error, when I run the following code.

crossword(H1,H2,V3,V1,V2) :- word(H1), word(H2), word(V3), word(V1), word(V2), word(H2) \= word(V2), string_length(H1,3), string_length(H2,7), string_length(V3,6), string_length(V1,4), string_length(V2,5).

Preceding this section I have a series of words, such as word("coding"), word("is"), word("fun"), ...

I have a lot of words, could this be the problem? Or is it how I have defined my rules?


Solution

  • The chain of five independent unconstrained selections in a row word(H1), word(H2), word(V3), word(V1), word(V2) means there will be made n5 choices overall, if you have n words defined in your knowledge base.

    Instead, move the constraining calls up in the predicate's body, for the wrong choices to fail as early as possible, preventing the futile nested selections from being performed at all:

    crossword(H1,H2,V3,V1,V2) :- 
        word(H1), string_length(H1,3),
        word(H2), string_length(H2,7),
        word(V3), string_length(V3,6),
        word(V1), ... .