Скользящая мозаика с изменяющимся размером мозаики с использованием логического программирования

Question

Итак, я пытаюсь решить эту проблему с организацией стенда, приведенную здесь. Это в основном головоломка с раздвижными плитками, в которой одна (будка) плитка должна достигать целевого места, и в конце концов все остальные (будки) плитки должны быть в своем первоначальном положении. Каждая плитка / будка имеет размерность, и ниже приводятся описания фактов и отношений:

• Один факт формы комнаты (W,H), который определяет ширину W и
  высота H комнаты (3 ≤ W, H ≤ 20).
• Один факт кабины (B), который
  указывает количество кабин (1 ≤ B ≤ 20).
• Отношение, состоящее из фактов измерения формы (B, W, H), которое определяет ширину W и высоту H кабины B.

• Отношение, состоящее из фактов вида
  положение (B, W, H), указывающее начальное положение (W, H) стенда B.

• Одна фактическая цель (B, W, H), указывающая пункт назначения (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)) .

Я новичок в Прологе, и я застрял на том, как идти дальше, у меня есть правило 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):

ходы (W0) -> {требуемый мир (W0) }.
ходы (W0) -> [M], { world0_move_world(W0, M, W) }, ходы (W).

Затем вы можете использовать итеративное углубление, чтобы найти кратчайшую последовательность ходов, которая решает головоломку:

? - длина (Ms, _), initial_world(W0), фраза (ходы (W0), Ms).