约束编程:按照模式规则用颜色填充网格
Constraint-programming: Fill grid with colors following pattern rules
我是约束编程的新手(来自 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)];
但是,除了像这样对所有内容进行硬编码之外,我不确定如何处理具有许多模式的更大网格。我会再试验一下。
您所说的约束似乎很容易表示为正则表达式。例如,可以使用正则表达式 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
在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
.
我是约束编程的新手(来自 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)];
但是,除了像这样对所有内容进行硬编码之外,我不确定如何处理具有许多模式的更大网格。我会再试验一下。
您所说的约束似乎很容易表示为正则表达式。例如,可以使用正则表达式 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
在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
.