The trick for achieving efficient Prolog solutions of such tasks is to use the Prolog system's built-in features for constraint logic programming, abbreviated a

The trick for achieving efficient Prolog solutions of such tasks is to use the Prolog system's built-in features for constraint logic programming, abbreviated as CLP. Constraints automatically prune those parts of the search space that do not contain solutions. This typically leads to extremely significant speedups over naively generating all possibilities. For example, integer constraints are available under the name "constraint logic programming over finite domains", abbreviated as CLP(FD), in all most widely used Prolog implementations. To solve combinatorial optimization tasks with Prolog, I recommend to start with CLP(FD). If necesseary, you can always combine it with other approaches, such as applying the simplex algorithm and also custom methods and heuristics. Please note that constraints have become widely available in Prolog systems only after the book you cite was published, and it does not mention these methods at all. With current systems, you can elegantly and efficiently solve the task using CLP(FD) constraints.