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

所以我试图解决这个展位安排问题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的子句可能需要进行一些修改。有指针吗？

最佳答案

您需要根据拼图状态之间的关系来表达任务。您当前的条款确定了单个举动的有效性，并且还可以生成可能的举动。

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

首先，我建议您考虑一个类似以下的关系:

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

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

一旦有了这种关系，整个任务就是找到一系列 Action 的Ms，以便将任何初始世界的W0转换为所需的状态W。

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

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

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

？-length(Ms，_)，initial_world(W0)，短语(moves(W0)，Ms)。
关于prolog - 使用逻辑编程滑动具有不同瓷砖尺寸的瓷砖拼图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46509371/

w0

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