prolog - Sliding tile puzzle con diferentes tamaños de mosaico usando programación lógica

xsb

Question

Así que estoy tratando de resolver este problema de arreglo de Booth dado aquí . Básicamente es un rompecabezas deslizante de baldosas donde una baldosa (cabina) tiene que llegar a un punto objetivo y al final todas las demás (baldosas) deben estar en su ubicación original. Cada azulejo / cabina tiene una dimensión y los siguientes son los datos de entrada y las descripciones de las relaciones:

• Un hecho de la sala de formulario (W, H), que especifica el ancho W y
  altura H de la habitación (3 ≤ W, H ≤ 20).
• Cabinas de hecho (B), que
  especifica el número de cabinas (1 ≤ B ≤ 20).
• Una relación que consiste en hechos de la dimensión del formulario (B, W, H), que especifica el ancho W y la altura H del stand B.

• Una relación que consta de hechos de la forma
  posición (B, W, H), especificando la posición inicial (W, H) del stand B.

• Un objetivo de hecho (B, W, H), que especifica el destino (W, H) del
  cabina de destino B.

• Un horizonte de hechos adicional (H) da un límite superior en el número de movimientos que se realizarán.

Se supone que el programa debe leer los datos de entrada de un archivo, pero solo estoy tratando de resolverlo, así que acabo de copiar una única entrada posible, y he escrito algunas cláusulas básicas:

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)) .

Soy nuevo en Prolog y estoy atascado sobre cómo ir desde aquí, tengo la regla no_overlap, así que puedo probar si un movimiento es válido o no, pero no estoy seguro de cómo con las cláusulas actuales que tengo. Mis cláusulas actuales para movimientos do / 3 probablemente necesiten alguna modificación. ¿Alguna sugerencia?

Answer 1

Debe expresar la tarea en términos de relaciones entre los estados del rompecabezas. Sus cláusulas actuales determinan la validez de un solo movimiento y también pueden generar posibles movimientos.

Sin embargo, eso no es suficiente: debe expresar más que un solo movimiento y su efecto en un solo mosaico. Necesita codificar, de alguna manera, el estado de todo el rompecabezas, y también codificar cómo un solo movimiento cambia el estado de toda la tarea.

Para empezar, te recomiendo que pienses en una relación como:

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

y expresar la relación entre un "mundo" dado W0 , un posible movimiento M , y el mundo resultante W Esta relación debe ser tan general como para generar , al retroceder, cada movimiento M que sea posible en W0 . Idealmente, debería funcionar incluso si W0 es una variable libre, y para esto puede resultarle útil a clpfd : Las restricciones le permiten expresar relaciones aritméticas de una manera mucho más general que la que está utilizando actualmente.

Una vez que tienes esa relación, toda la tarea es encontrar una secuencia Ms de movimientos de modo que cualquier mundo inicial W0 se transforme en un estado deseado W

Asumiendo que ha implementado world0_move_world/3 como un bloque de construcción, puede levantarlo fácilmente a listas de movimientos de la siguiente manera (usando dcg ):

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

A continuación, puede utilizar la profundización iterativa para encontrar la secuencia más corta de movimientos que resuelve el rompecabezas:

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