在下面的谜题中,我们尝试用以下方式用蓝色和白色方 block 填充网格:
- 不允许有 3 个相同颜色的行(或列)。
- 每一行和每一列都有相同数量的蓝色和白色方 block 。
如果我们现在用 0 表示白色,用 1 表示蓝色,我们得到:
0 _ _ _ 1 _
_ 0 _ _ _ _
_ _ _ _ _ 0
1 _ _ 0 _ _
_ _ 1 1 _ _
_ 0 _ _ 1 _
我们可以很快验证
0 1 0 0 1 1
0 0 1 1 0 1
1 1 0 1 0 0
1 1 0 0 1 0
0 0 1 1 0 1
1 0 1 0 1 0
是这个例子的解决方案。
作为约束,我写了以下内容:
constraints(Board,N) :-
N2 is N // 2,
( for(I,1,N), param(Board,N2,N)
do
Row is Board[I,1..N],
Col is Board[1..N,I],
ic_global:sequence_total(N2,N2,1,2,3,Row),
ic_global:sequence_total(N2,N2,1,2,3,Col)
).
sequence_total/6确保值 1 应在行/列中恰好出现 N2 次(N 次的一半),并且 3 个元素的指定行/列中的每个序列应包含值 1 的 1 到 2 倍(因此没有 3值为 1 的方 block 可以彼此相邻出现)。
对于 18x18 拼图实例 (*),我得到以下结果:
Solved in 147 backtracks
Yes (10.39s cpu, solution 1)
在执行任何搜索之前,约束似乎已经很好地完成了它们的工作,因为“只”需要 147 次回溯。然而,运行时间对我来说似乎真的很长,尤其是与回溯的数量相比。我猜这是由于必须进行的所有序列检查?更改 search/6 中的任何选择/选择方法的事实对运行时间几乎没有任何影响似乎证实了这一点。
如果是这样,是否有任何其他更有效的方法来限制列表/数组中的序列,使 N 个相同的元素彼此相邻并缩短运行时间?
编辑
使用下面@jschimpf提供的分解版本后,得到如下结果:
Solved in 310 backtracks
Yes (0.22s cpu, solution 1)
新的约束不如 sequence/6 强,我们确实需要更多的回溯,但我们的运行时间从 10.39 秒下降到 0.22 秒,所以整体结果非常理想。
示例数据:
本题使用的谜题(无回溯求解)
problem(p(6,1),[(1,1,0),(1,5,1),(2,2,0),(3,6,0),(4,1,1),(4,4,0),(5,3,1),(5,4,1),(6,2,0),(6,5,1)]).
我发布结果的拼图 (*):
problem(p(18,1),[(1,3,0),(1,9,0),(1,10,0),(1,12,0),(1,14,0),(1,18,1),(2,4,0),(2,7,1),(2,8,1),(3,2,1),(3,6,0),(3,16,0),(3,17,0),(4,2,1),(4,4,1),(4,10,1),(4,13,1),(4,18,1),(5,8,1),(5,10,1),(5,15,0),(5,16,1),(6,12,1),(7,3,0),(7,4,0),(7,6,1),(7,9,0),(7,12,1),(7,17,0),(8,1,1),(8,4,0),(8,8,1),(8,15,1),(8,16,1),(9,7,0),(9,10,0),(9,14,0),(10,2,1),(10,4,1),(10,6,1),(10,13,1),(11,7,0),(11,10,1),(12,1,1),(12,4,1),(12,7,1),(12,15,1),(12,16,1),(13,1,1),(13,6,0),(13,8,1),(13,10,0),(13,16,1),(14,5,1),(14,10,0),(14,13,1),(15,1,1),(15,3,1),(15,12,0),(15,13,1),(15,15,0),(16,2,1),(16,4,0),(16,12,0),(16,18,0),(17,9,0),(17,15,0),(17,18,0),(18,2,1),(18,8,1),(18,11,1),(18,15,1),(18,16,1)]).
最佳答案
事实证明,在这种情况下,sequence 约束的手工制作分解版本效率更高。使用示例
sequence_1_2([X1,X2,X3|Xs]) :- !,
S #:: 1..2,
X1+X2+X3 #= S,
sequence_1_2([X2,X3|Xs]).
sequence_1_2(_).
将任何3元素子序列的和约束为1或2,并将sequence_total/6约束替换为
...,
sum(Row) #= N2,
sequence_1_2(Row),
这使求解时间缩短到 0.2 秒。
关于prolog - 3 行逻辑谜题 : optimisation for sequence constraints in lists/arrays,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36202351/