prolog - 使用逻辑编程具有不同瓷砖尺寸的滑动瓷砖拼图

Question

所以我想解决这个展位布置问题given here .它基本上是一个滑动瓷砖拼图，其中一个(展位)瓷砖必须到达目标位置，最后所有其他(展位)瓷砖应位于其原始位置。每个瓷砖/展位都有一个维度，以下是输入事实和关系描述:

表格 room(W,H) 的一个事实，它指定宽度 W 和
房间的高度 H(3 ≤ W，H ≤ 20)。

一个事实展位(B)，其中
指定展位数量(1 ≤ B ≤ 20)。

包含的关系
形式维度(B，W，H)的事实，指定宽度W
和展位B的高度H。

由以下形式的事实组成的关系
position(B, W, H)，指定展位B的初始位置(W, H)。

一个事实目标(B，W，H)，指定目标(W，H)
目标展位B。

一个额外的事实视界(H)给出了一个上限
要执行的移动次数。

该程序应该从文件中读取输入事实，但我只是想解决这个问题，所以我现在只是复制粘贴了一个可能的输入，并且我已经编写了一些基本条款:

room(3, 3).
booths(3).
dimension(1, 2, 1).
dimension(2, 2, 1).
dimension(3, 1, 1).
position(1, 0, 1).
position(2, 1, 2).
position(3, 0, 0).
target(3, 0, 2).
horizon(10).

xlim(X) :- room(X,_).
ylim(X) :- room(_,X).

sum(X,Y,Z) :- Z is X+Y .

do(position(B,X,Y),movedown,position(B,X,Z)) :- Y > 0 , sum(Y,-1,Z) .
do(position(B,X,Y),moveup,position(B,X,Z)) :- ylim(L), Y < L , sum(Y,1,Z) .
do(position(B,X,Y),moveleft,position(B,Z,Y)) :- X > 0 , sum(X,-1,Z) .
do(position(B,X,Y),moveright,position(B,Z,Y)) :- xlim(L), X < L, sum(X,1,Z) .

noverlap(B1,B2) :- 
    position(B1,X1,Y1), 
    position(B2,X2,Y2), 
    ends(Xe1,Ye1,B1), 
    ends(Xe2,Ye2,B2), 
    ( Xe1 < X2 ; 
      Xe2 < X1 ; 
      Ye1 < Y2 ; 
      Ye2 < Y1 ).

ends(Xe,Ye,B) :- 
    dimension(B,W,H), 
    position(B,X,Y), 
    Xe is X+W-1, 
    Ye is Y+H-1.

between(X,Y,Z) :- 
    X > Y , 
    X < Z .

validMove(M,B) :- do(position(B,X,Y),M,position(B,Xn,Yn)) .

我是 Prolog 的新手，我被困在如何从这里开始，我有 no_overlap 规则，所以我可以测试移动是否有效，但我不确定我拥有的当前条款如何。我当前的移动条款 do/3 可能需要一些修改。任何指针？

Answer 1

你需要用 来表达任务国家关系的谜题。您当前的子句决定了单个移动的有效性，并且还可以生成可能的移动。

然而，这还不够:您需要表达的不仅仅是一个 Action 及其对单个图块的影响。您需要以某种方式对整个拼图的状态进行编码，并且还需要对单个移动如何改变整个任务的状态进行编码。

首先，我建议您考虑以下关系:

world0_move_world(W0, M, W) :- ...

并表达给定“世界”之间的关系 W0 ，可能的举动 M ，以及由此产生的世界 W .这种关系应该是如此普遍，以至于在回溯时，每次移动都会产生 M这在 W0 中是可能的.理想情况下，如果 W0，它甚至应该可以工作是一个自由变量，为此你可能会发现 clpfd有用:约束允许您以比当前使用的更通用的方式表达算术关系。

一旦你有了这样的关系，整个任务就是找到一个序列 Ms移动使得任何初始世界 W0转换为所需状态 W .

假设您已实现 world0_move_world/3作为构建块，您可以轻松地将其提升到如下移动列表(使用 dcg ):

移动(W0)--> {desired_world(W0)}。
移动(W0)--> [M]，{ world0_move_world(W0，M，W)}，移动(W)。

然后，您可以使用迭代深化来找到解决难题的最短移动序列:

?- 长度(女士，_)，初始世界(W0)，短语(移动(W0)，女士)。