4

我是约束编程的新手（来自 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# or-tools 和 MiniZinc 中解决它，但我遇到的最大问题是构建约束。我可以从一个序列中生成模式（以 c# 命令式的方式），但是如何将它变成一个约束呢？

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

上面拼图中顶行的示例：rgb to [4-length sequences] -> 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)];

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

4

2 回答 2

4

您正在谈论的约束似乎很容易表示为正则表达式。例如abc，可以使用正则表达式捕获具有不同长度的示例abc.*，它需要一个a然后是一个b，然后是一个c，之后它将接受任何其他内容。

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

示例表达式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
于 2018-03-05T03:01:29.517 回答
0

在 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 中，这是基于 prolog 的 CLP 系统（不是 IDE 系统），上面的 predicate( color_chunk_list) 可以通过propia机制转换为 clp 约束，并且可以生成 clp propagation。

于 2018-04-13T04:07:33.603 回答