如何在MiniZinc中实现数组折叠，简化密码算术求和？

问题描述 #

在MiniZinc中编写密码算术题时，通常需要手动展开求和约束，比如经典的SEND+MORE=MONEY案例：

constraint           1000 * S + 100 * E + 10 * N + D
                   + 1000 * M + 100 * O + 10 * R + E
       = 10000 * M + 1000 * O + 100 * N + 10 * E + Y;

这种手动编写的方式仅适用于单个简单场景，当需要处理更多密码算术题时，效率极低。希望能实现类似Haskell中foldl的功能，通过变量列表自动计算对应的数值，例如Haskell中可通过以下代码将列表转为数字：

ghci> foldl (\x y -> 10 * x + y) 0 [1, 3, 4, 1, 5]
13415

实现方案 #

MiniZinc虽无原生fold函数，但可通过递归函数或数组求和的方式实现等效功能，以下是两种实用方案：

方案1：递归函数实现 #

通过递归函数模拟foldl的累加逻辑，将数字列表转换为对应数值：

function var int: list_to_num(array[int] of var int: digits) =
  if length(digits) == 0 then
    0
  else
    list_to_num(array1d(digits[1..length(digits)-1])) * 10 + digits[length(digits)]
  endif;

使用示例（SEND+MORE=MONEY）：

% 声明变量
var 0..9: S; var 0..9: E; var 0..9: N; var 0..9: D;
var 0..9: M; var 0..9: O; var 0..9: R; var 0..9: Y;

% 约束条件：首位不能为0，所有变量唯一
constraint S != 0 /\ M != 0;
constraint alldifferent([S,E,N,D,M,O,R,Y]);

% 用递归函数构建求和约束
constraint list_to_num([S,E,N,D]) + list_to_num([M,O,R,E]) = list_to_num([M,O,N,E,Y]);

solve satisfy;
output [
  "SEND = ", show(S), show(E), show(N), show(D), "\n",
  "MORE = ", show(M), show(O), show(R), show(E), "\n",
  "MONEY = ", show(M), show(O), show(N), show(E), show(Y)
];

方案2：数组求和推导式 #

通过数组推导式计算每一位的权重并累加，逻辑更直观：

function var int: list_to_num(array[int] of var int: digits) =
  sum(i in index_set(digits)) (
    digits[i] * pow(10, length(digits) - i)
  );

该方案利用pow函数计算10的幂次，直接对每一位数字乘以对应权重后求和，无需递归。

注意事项 #

• 递归函数方案更贴近Haskell fold的核心逻辑，数组求和方案则更易理解和调试。
• 确保变量列表的顺序与数字的高位到低位一致（如[S,E,N,D]对应四位数SEND）。

内容的提问来源于stack exchange，提问作者AndrewShulaev