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

Question

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

谜题说明：给玩家一个空的游戏板（大小不一），他们必须使用 n 种颜色填充它，使用行和列的线索模式。每个线索模式都是 row/col 中的颜色序列，但删除了连续的重复项。

这是一个简单的 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# or-tools 和 MiniZinc 解决它，但我遇到的最大问题是构建约束。我可以从序列中生成模式（以 C# 命令式方式），但如何将其转换为约束？

我是怎么想的：从每个线索模式中生成所有可能的序列。然后对相应的 row/col 进行约束，表示它必须是这些序列之一。

上面拼图中顶行的示例：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 表示。常规谓词模拟具有接受状态的自动机。通过提供允许的 state-transitions 模型是约束。

示例表达式 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

Answer 2

在Prolog(language)中，我用DCG形式来描述这类问题。它是扩展的 BNF 形式。因此，我建议在您的环境中寻找使用扩展 BNF 表单的方法。

SWI-Prolog 示例：

color_chunk_list(Encoded,Decoded):-
    phrase(chunk_list(Encoded),Decoded),
    chk_continuity(Encoded).

chunk_list([])-->[].
chunk_list([First|Rest])-->colorrow(First),chunk_list(Rest).

colorrow(Color)-->[Color],colorrow(Color).
colorrow(Color)-->[Color].

chk_continuity([First,Second|Rest]):-First \= Second,chk_continuity([Second|Rest]).
chk_continuity([_]).

在这个程序中，编码和解码是双向的。

测试：

?- length(L,4),color_chunk_list([r,g],L).
L = [r, r, r, g] ;
L = [r, r, g, g] ;
L = [r, g, g, g] ;
false.

?- length(L,6),color_chunk_list([a,b,c],L).
L = [a, a, a, a, b, c] ;
L = [a, a, a, b, b, c] ;
L = [a, a, a, b, c, c] ;
L = [a, a, b, b, b, c] ;
L = [a, a, b, b, c, c] ;
L = [a, a, b, c, c, c] ;
L = [a, b, b, b, b, c] ;
L = [a, b, b, b, c, c] ;
L = [a, b, b, c, c, c] ;
L = [a, b, c, c, c, c] ;
false.

?- color_chunk_list(L,[a,a,b,b,c,c]).
L = [a, b, c] ;
false.

?- color_chunk_list(L,[b,r,b,r,r,g,g,b]).
L = [b, r, b, r, g, b] ;
false.

在 ECLiPSe 中，它是基于序言的 CLP 系统（不是 IDE 一个）， above predicate(color_chunk_list) 可以变成 clp constraint 具有 propia 机制并且可以生成 clp propagation.

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

Constraint-programming: Fill grid with colors following pattern rules

logic

constraint-programming

minizinc

or-tools