logic - 约束编程:按照模式规则用颜色填充网格

Question

我是约束编程的新手(来自 c#)，我正在尝试解决这个问题。不幸的是，我没有这种拼图的名称，所以我不确定要搜索什么。我能找到的最接近的例子是 Nonogram 和 Tomography 谜题。

拼图说明:
给玩家一个空的游戏板(不同大小)，他们必须用 n 种颜色填充，使用行和列的线索模式。每个线索模式是该行/列中的颜色序列，但删除了连续的重复项。

这是一个简单的小 4x4 网格示例，具有 3 种颜色:

rbg,rbr,grb,bgbg       <- (top-to-bottom column constraints)

    _,_,_,_     rgb    <- (row constraints)
    _,_,_,_     brg 
    _,_,_,_     b
    _,_,_,_     grbg

解决方案(2):

    r,r,g,b
    b,?,r,g     
    b,b,b,b     
    g,r,b,g 

?可以是红色或蓝色，但不能是绿色。

下面的模式示例。
示例给出了 6 个长度的序列以进行模式化:

aaaaaa -> a
aabbcc -> abc
abbbbc -> abc
cabbbc -> cabc
bbbaac -> bac
abbaab -> abab
abcabc -> abcabc

示例给出了潜在解决方案序列的模式:

abc -> abc (3 length solution)
abc -> abcc, abbc, aabc (4 length solutions)
abc -> abccc, abbcc, abbbc, aabbc, aaabc (5 length solutions)

我尝试在 C# 或工具和 MiniZinc 中解决它，但我遇到的最大问题是构建约束。我可以从序列中生成模式(以 c# 命令方式)，但是如何将其转换为约束？

我是怎么想的:从每个线索模式生成所有潜在的序列。然后对相应的行/列进行约束，表明它必须是这些序列之一。

上面拼图顶行的示例:rgb 到 [4 长度序列] -> rgbb、rggb、rrgb，然后为该行添加约束:必须等于这些序列之一。

我这样想对吗？有没有更聪明的方法来做到这一点？

感谢您的任何建议。

======================================

一些进展后编辑:

此 MiniZinc 正确求解模式 abc 的顶行，该模式具有 3 个长度为 4 的解:aabc、abbc、abcc。

include "globals.mzn";

array [1..4, 1..4] of var 1..3: colors;

constraint regular(row(colors, 1), 4, 3, 
[|
  % a, b, c
    2,0,0| % accept 'a'
    2,3,0| % accept 'a' or 'b' ?
    0,3,4| % accept 'b' or 'c' ?
    0,0,4| % accept 'c'
|], 1, {4}); 

% Don't care about rest of grid for now.
constraint forall(i,j in 1..4 where i > 1) (row(colors, i)[j] = 1);

solve satisfy;

output [show(colors)]; 

但是，除了像这样对所有内容进行硬编码之外，我不确定如何处理具有许多模式的较大网格。我会多做一些实验。

Answer 1

您所谈论的约束似乎很容易表示为正则表达式。例如您的 abc可以使用正则表达式 abc.* 捕获长度可变的示例，这需要一个 a然后一个 b ，然后是一个 c ，之后它会接受其他任何东西。

在 MiniZinc 中，这些类型的约束使用 regular predicate 表示。 .常规谓词模拟具有接受状态的自动机。通过提供允许的状态转换，模型是约束。

示例表达式 abc.*将由以下约束项强制执行:

% variables considered, nr states, input values
constraint regular(VARS, 4, 1..3, [|
    % a, b, c
    2,0,0| % accept 'a'
    0,3,0| % accept 'b'
    0,0,4| % accept 'c'
    4,4,4| % accept all
|], 1, {4}); % initial state, accepting states