Solving string constraints in MiniZinc

Question

I attempted to define a constraint with the string concatenation operator in MiniZinc, solving for the variables a and b:

include "disjunctive.mzn";

var string:a;
var string:b;
constraint("var1/var2" = (a ++ "/" ++ b));

solve satisfy;
output ["\nx=", show(a)];

Nonetheless, this appears to be a syntax error:

MiniZinc: type error: type error in operator application for `++'. No matching operator found with left-hand side type `string' and right-hand side type `var string'

Is it still possible to solve constraints in MiniZinc with strings or arrays as variables?

Answer 1

Constraints directly on string are quite rare in the Constraint Programming community. There is some research in this, though I haven't seen any general CP system that supports string variables. (See below for non-general CP systems.)

In MiniZinc, it's better to convert strings to integers (e.g. a=1, b=2, etc) and then simulate all operations as integer operations.

One simple example is a crossword generator: http://hakank.org/minizinc/crossword3/crossword3.mzn, which is described in http://hakank.org/minizinc/crossword3/.

One important string operation is concatenation of two string, but since MiniZinc only support static (fixed length) arrays, this must handled by defining a large enough "target array".

Regarding Picat, the cp/sat modules don't support strings either, so the same conversion to integers must be applied. But since Picat is a logic programming language (think Prolog), one can use traditional logic programming approaches.

Note that MiniZinc and Picat - as well as most other CP systems - supports the global constraint "regular" which use a DFA (deterministic finite automaton) to create the constraints. See for example a Nonogram solver: http://hakank.org/minizinc/nonogram_create_automaton2.mzn and the decomposition of the global contiguity constraint: http://hakank.org/minizinc/contiguity_regular.mzn

MiniZinc also supports a NFA (nondeterministic) variant of the regular constraint.

That said, there are systems using a kind of constraint solving approach that supports string variables, though AFAIK they tend to support only string variables, not the general repertoire of integers, sets, etc. See for example Hampi (http://people.csail.mit.edu/akiezun/hampi/). Note: it was quite a long time since I checked out these dedicated systems.