在序言中解决带有限制的拼图游戏

发布于 2024-12-19 06:46:52 字数 158 浏览 1 评论 0原文

我现在开始使用 SICStus Prolog 学习 prolog 中的限制。虽然我知道如何使用它解决简单的问题，但我有一个练习必须解决拼图游戏。但是我不知道如何解决这个问题，因为我将有几个具有不同属性（片段）的不同元素，任何人都可以给我一个例子，说明如何在序言中表示片段列表以及我应该使用什么样的限制？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

允世 2024-12-26 06:46:52

第一次尝试时，我会按照以下方式做一些事情：

对于每个字段，使用 5 个变量。第一个变量表示进入该字段的拼图块。每件作品都有自己的 id。对于您在上面的评论中提到的拼图，有 12 块，因此每个变量的域为 {1..12}：

P #:: 1..12,

其他四个变量表示每个字段的四个边，以及拼图块是否放置在该字段中的地方有凹痕或标签。在您的拼图中，每个“上”或“下”侧都有一个选项卡和一个凹痕，因此您可以指示选项卡是左侧还是右侧。再次，布尔决策变量。

[EL,EU,ER,ED] #:: 0..1,

拼图块可以这样编码：

piece(1,  [](0,1,1,0)).

例如，这是您在评论中给出的网站上拼图描述中的 A 块。

现在您可以定义两个相邻字段之间的邻居关系。由于您有布尔变量，并且制表符需要满足凹痕，因此您设置了一个约束（不是“限制”），要求总和为一：

R1 + L2 #= 1,

即，字段一中的片段的右边缘必须与字段一中的片段的左边缘匹配您还可以为沿边界的

边缘设置类似的约束。

您设置一个约束，要求所有字段必须包含不同的块：（

alldifferent(Fields),

其中 Fields 是包含 P 变量的列表）

您需要一个变量来表示拼图块的方向：

O #:: 0..1,

您只需要一个，因为在您的拼图中，所有块必须朝向同一方向。

最后，您需要将每个字段的片段、方向和边缘变量组合在一起的约束，以便当您为字段选择片段（并且方向已知）时，您可以适当地设置边缘变量：（

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

该语法不适用于 Sicstus ，但是 FD 约束库应该足够相似）

请注意，当翻转一块时，我必须反转下边缘的编码。这允许我保持上/下边缘的“总和等于一”约束，但不是最优的，因为它阻止我轻松地将信息从边缘变量传播到片变量（一个片可能获得与另一种是倒置时的情况）。但我懒得改变第一次尝试的编码。

（编辑：这应该很容易通过反转下边缘的编码来解决，例如：piece(1, [](0,1,1,1))。，并使用需要的约束相邻块的上下边缘具有相同的值，而不是总和为 1。）

将所有内容放在一起并简单地标记 P 变量（首先实例化方向变量之后）给出了两个解决方案：

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

我使用矩阵而不是列表，按顺序使拼图区域的行数更多著名的。矩阵还允许更快地访问不同行中的相邻字段。

For a first try, I would do something along these lines:

For each field, use 5 variables. The first variable denotes the puzzle piece that goes into the field. Each piece has its own id. In the case of the puzzle that you mentioned in your comment above there are 12 pieces, so each variable would have a domain of {1..12}:

P #:: 1..12,

The other four variables denote the four edges of each field, and whether the puzzle piece placed in the field has a dent or tab there. In your puzzle, each "up" or "down" side has a tab and a dent, so you denote whether the tab is left or right. Again, boolean decision variables.

[EL,EU,ER,ED] #:: 0..1,

A puzzle piece can the be encoded like this:

piece(1,  [](0,1,1,0)).

This for instance is piece A in the description of your puzzle on the website that you gave in the comment.

Now you can define the neighbour relation between two adjacent fields. Since you have boolean variables, and a tab needs to meet a dent, you set a constraint (not "restriction") requiring that the sum be one:

R1 + L2 #= 1,

I.e., the right edge of the piece in field one must match the left edge of the piece in field 2.

You also set similar constraints for the edges along the borders.

The you set a constraint requiring that all fields must contain different pieces:

alldifferent(Fields),

(where Fields is the list containing the P variables)

You need a variable that denotes the orientation of the puzzle pieces:

O #:: 0..1,

You need just one, since in your puzzle, all pieces must be orientated in the same direction.

Finally, you need constraints that combine the piece, orientation and edge variables for each field, so that when you select a piece for a field (and the orientation is known) you can set the edge variables appropriately:

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

(the syntax is not for Sicstus, but ECLiPSe. The FD constraint libraries should be similar enough, though)

Note that I had to invert the encoding for the down edge when turning a piece upside-down. This is allowed me to keep the "sum equals one" constraints for up/down edges, but is sub-optimal, since it prevented me from easily propagating information from the edge variables to the piece variables (a piece may get the same encoding as another when turned upside down). But I was too lazy to change the encoding for this first try.

(Edit:this should be easy to fix by inverting the encoding for the down edge, e.g.: piece(1, [](0,1,1,1))., and using constraints that require up and down edges of neighbouring pieces to have the same value instead of having sum one.)

Throwing all together and simply labeling the P variables (after instantiating the orientation variable first) gives the two solutions:

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

I used matrices instead of lists, in order to make the rows of the puzzle field more prominent. Matrices also allow faster access to neighbouring fields in different rows.

回复收藏 0 原文

~没有更多了~