Yes it is true, logic programming languages like Prolog are indeed often a good fit to solve such combinatorial tasks.
For example, using Scryer Prolog and its CLP(ℤ) library for constraint logic programming over integers, we can solve the first optimization task from the article on the Prolog toplevel, without even having to define a predicate:
?- use_module(library(clpz)).
true.
?- Vs = [Swordsmen,Bowmen,Horsemen],
Vs ins 0..sup,
60*Swordsmen + 80*Bowmen + 140*Horsemen #=< 1200,
20*Swordsmen + 10*Bowmen #=< 800,
40*Bowmen + 100*Horsemen #=< 600,
Power #= Swordsmen*70 + Bowmen*95 + Horsemen*230,
labeling([max(Power)], Vs).
yielding solutions in decreasing amount of Power:
Vs = [6,0,6], Swordsmen = 6, Bowmen = 0, Horsemen = 6, Power = 1800
; Vs = [7,1,5], Swordsmen = 7, Bowmen = 1, Horsemen = 5, Power = 1735
; Vs = [5,0,6], Swordsmen = 5, Bowmen = 0, Horsemen = 6, Power = 1730
; ... .
On backtracking, alternatives are automatically generated. The above interaction shows that in this concrete example, the optimal solution is unique. In Scryer Prolog, we can press "a" on the toplevel, and it will automatically enumerate all solutions, 558 in total for this example, ending with:
...,
; Vs = [2,0,0], Swordsmen = 2, Bowmen = 0, Horsemen = 0, Power = 140
; Vs = [0,1,0], Swordsmen = 0, Bowmen = 1, Horsemen = 0, Power = 95
; Vs = [1,0,0], Swordsmen = 1, Bowmen = 0, Horsemen = 0, Power = 70
; Vs = [0,0,0], Swordsmen = 0, Bowmen = 0, Horsemen = 0, Power = 0
; false.
If we omit the actual search for solutions from the query above, i.e., if we post only the part before labeling/2:
?- Vs = [Swordsmen,Bowmen,Horsemen],
Vs ins 0..sup,
60*Swordsmen + 80*Bowmen + 140*Horsemen #=< 1200,
20*Swordsmen + 10*Bowmen #=< 800,
40*Bowmen + 100*Horsemen #=< 600,
Power #= Swordsmen*70 + Bowmen*95 + Horsemen*230.
then we see from the answer that the constraint solver has automatically deduced, from the posted constraints, significantly restricted domains of the occurring integer variables:
...,
clpz:(Swordsmen in 0..20),
clpz:(Bowmen in 0..15),
clpz:(Horsemen in 0..6),
clpz:(Power in 0..4205).
This automatic restriction is called constraint propagation, and this is what reduces the search space so significantly. It also allows the application of heuristics that often significantly speed up up the search in practice, such as starting with domain variables with smallest domains, in the hope to detect infeasible cases earlier. We can flexibly select these heuristics as options of labeling/2, while leaving all other parts of the query the same. For instance, in this concrete example, I obtained a more than 2-fold speedup by using the "min" labeling option, i.e., writing labeling([max(Power),min], Vs), so that the search always selects a variable with smallest lower bound for branching.
Constraint solvers blend in naturally in Prolog, and are often a reason for buying a fast commercial Prolog system. In fact, Prolog itself can be regarded as an instance of constraint programming: constraint logic programming over Herbrand terms, CLP(H), where (=)/2, i.e., terms are the same, and dif/2, i.e., terms are different, are the only constraints. Other specialized domains include CLP(B) over Boolean values, and CLP(Q) over the rational numbers, where dedicated algorithms allow very efficient and convenient solutions.
Constraint programming was also recently discussed in The Programming Paradigm to Find One Solution Among 8,080,104 Candidates:
Thanks for the detailed write-up, I find this stuff super interesting. If I wanted to read up and study the maths involved (CLP(Z)) what would be the best place to start (textbooks, courses etc)?
The second course is the last part of a three part series. The first two parts are on modeling of problems with MiniZinc. They are also quite enjoyable.
I appreciate the effort you have put into this comment, you have renewed my interest in learning Prolog. It's such a beautiful and still esoteric language to my eyes.
Any suggestion for good LP libraries/solvers for someone that isn't fond of Python? Isn't Prolog well suited for this kind of process?