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

Question

所以我试图解决这里给出的布斯安排问题.它基本上是一个滑动瓷砖拼图,其中一个(展位)瓷砖必须到达目标点,最后所有其他(展位)瓷砖应该在其原始位置.每个图块/展位都有一个尺寸,以下是输入事实和关系描述:

• 形状室(W,H)的一个事实,它规定
  了房间的宽度W和高度H(3≤W,H≤20).
• 一个事实展位(B),
  规定了展位数量(1≤B≤20).
• 由形状尺寸(B,W,H)的事实组成的关系,其指定了展位B的宽度W和高度H.

• 由表格
  位置(B,W,H)的事实组成的关系,指定展位B的初始位置(W,H).

• 一个事实目标(B,W,H),指定
  目标摊位B 的目的地(W,H).

• 附加的事实视界(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

你需要根据谜题的状态之间的关系来表达任务.您当前的条款确定单个移动的有效性,并且还可以生成可能的移动.

但是,这还不够:您需要表达的不仅仅是单个移动及其对单个切片的影响.您需要以某种方式对整个拼图的状态进行编码,并编码单个动作如何更改整个任务的状态.

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

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

并表达一个给定的"世界" W0,一个可能的行动  M和由此产生的世界  之间的关系  W.这种关系应该是如此通用,以便在回溯时产生M可能的  每一个动作  W0.理想情况下,如果W0是自由变量,它甚至应该工作  ,为此您可能会发现clpfd很有用:约束允许您以比当前使用的更通用的方式表达算术关系.

一旦你有这样的关系,整个任务就是找到一系列 Ms动作,这样任何初始世界  W0都会转变为所需的状态  W.

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

moves(W0) --> { desired_world(W0) }.
moves(W0) --> [M], { world0_move_world(W0, M, W) }, moves(W).

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

?- length(Ms, _), initial_world(W0), phrase(moves(W0), Ms).