Решение 8 головоломок с поиском лучших в прологе

Question

Как следует из названия, я должен сделать пролог-программу, которая решает 8 задач с использованием поиска по принципу "лучший вначале", я новичок в Прологе и ИИ, поэтому мне трудно.

На данный момент у меня есть правила перемещения:

%% move left in the top row
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
     [0,X1,X3, X4,X5,X6, X7,X8,X9]).
move([X1,X2,0, X4,X5,X6, X7,X8,X9],
     [X1,0,X2, X4,X5,X6, X7,X8,X9]).

%% move left in the middle row
move([X1,X2,X3, X4,0,X6,X7,X8,X9],
     [X1,X2,X3, 0,X4,X6,X7,X8,X9]).
move([X1,X2,X3, X4,X5,0,X7,X8,X9],
     [X1,X2,X3, X4,0,X5,X7,X8,X9]).

%% move left in the bottom row
move([X1,X2,X3, X4,X5,X6, X7,0,X9],
     [X1,X2,X3, X4,X5,X6, 0,X7,X9]).
move([X1,X2,X3, X4,X5,X6, X7,X8,0],
     [X1,X2,X3, X4,X5,X6, X7,0,X8]).

%% move right in the top row 
    move([0,X2,X3, X4,X5,X6, X7,X8,X9],
     [X2,0,X3, X4,X5,X6, X7,X8,X9]).
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
     [X1,X3,0, X4,X5,X6, X7,X8,X9]).

%% move right in the middle row 
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
     [X1,X2,X3, X5,0,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
     [X1,X2,X3, X4,X6,0, X7,X8,X9]).

%% move right in the bottom row
move([X1,X2,X3, X4,X5,X6,0,X8,X9],
     [X1,X2,X3, X4,X5,X6,X8,0,X9]).
move([X1,X2,X3, X4,X5,X6,X7,0,X9],
     [X1,X2,X3, X4,X5,X6,X7,X9,0]).

%% move up from the middle row
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
     [0,X2,X3, X1,X5,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
     [X1,0,X3, X4,X2,X6, X7,X8,X9]).
move([X1,X2,X3, X4,X5,0, X7,X8,X9],
     [X1,X2,0, X4,X5,X3, X7,X8,X9]).

%% move up from the bottom row
move([X1,X2,X3, X4,X5,X6, X7,0,X9],
 [X1,X2,X3, X4,0,X6, X7,X5,X9]).
move([X1,X2,X3, X4,X5,X6, X7,X8,0],
     [X1,X2,X3, X4,X5,0, X7,X8,X6]).
move([X1,X2,X3, X4,X5,X6, 0,X8,X9],
     [X1,X2,X3, 0,X5,X6, X4,X8,X9]).

%% move down from the top row
move([0,X2,X3, X4,X5,X6, X7,X8,X9],
     [X4,X2,X3, 0,X5,X6, X7,X8,X9]).
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
     [X1,X5,X3, X4,0,X6, X7,X8,X9]).
move([X1,X2,0, X4,X5,X6, X7,X8,X9],
     [X1,X2,X6, X4,X5,0, X7,X8,X9]).

%% move down from the middle row
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
     [X1,X2,X3, X7,X5,X6, 0,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
     [X1,X2,X3, X4,X8,X6, X7,0,X9]).
move([X1,X2,X3, X4,X5,0, X7,X8,X9],
     [X1,X2,X3, X4,X5,X9, X7,X8,0]).

(Я знаю, что есть более простой способ использования списков, но это то, что сработало для меня)

И лучший первый код, который я нашел в Интернете: http://www.cs.unm.edu/~luger/ai-final/code/PROLOG.best.html

Но в этом лучшем первом коде есть эвристическая функция, которая не запускается:

go(Start, Goal) :- 
   empty_set(Closed),
   empty_sort_queue(Empty_open),
   heuristic(Start, Goal, H),
   state_record(Start, nil, 0, H, H, First_record),
   insert_sort_queue(First_record, Empty_open, Open),
   path(Open,Closed, Goal).

Я предполагаю, потому что он нигде не определен, и мне нужно определить его самому, поскольку эвристика меняется в зависимости от проблемы.

Так что я подумал об использовании эвристики "тайлы с места" для головоломки "8", так как она звучит проще, чем манхэттенское расстояние или что-то еще. Но теперь я застрял в том, как это программировать, везде гуглил, как сравнивать списки и как добавлять переменные, и я вроде как сделал это, что я не знаю, сработает ли это:

heuristic([],[],H).
heuristic([Head1|Tail1],[Head2|Tail2], H):-
   not(samePlace(Head1,Head2))->H1 is H + 1,
   heuristic(Tail1, Tail2, H1).

Моя идея состоит в том, что он ищет каждый элемент стартового списка и сравнивает его со списком целей, а затем, если они отличаются, добавляет 1 к H, где H количество плиток неуместно.

Для чего я также определил "плитки в тех же правилах места":

samePlace([X,_,_,_,_,_,_],[X,_,_,_,_,_,_]).
samePlace([_,X,_,_,_,_,_],[_,X,_,_,_,_,_]). 
samePlace([_,_,X,_,_,_,_],[_,_,X,_,_,_,_]).
samePlace([_,_,_,X,_,_,_],[_,_,_,X,_,_,_]).
samePlace([_,_,_,_,X,_,_],[_,_,_,_,X,_,_]).
samePlace([_,_,_,_,_,X,_],[_,_,_,_,_,X,_]).
samePlace([_,_,_,_,_,_,X],[_,_,_,_,_,_,X]). 
(etc...)

Но, конечно, я получаю "ОШИБКА: эвристика /3: Аргументы не достаточно созданы", что, как я полагаю, означает, что я никогда не инициализировал H.

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

Мои вопросы: - Я на правильном пути, или я совершенно не понял, что означает эта "эвристическая" функция? - Как я могу инициализировать H? - Является ли мой код эвристической функции синтаксически правильным?

Извините за длинный пост, но правила говорят, что я должен дать много информации. Я надеюсь, что вы можете помочь мне с этим, любая помощь приветствуется, поэтому, если вы знаете какие-либо другие способы сделать это, не стесняйтесь публиковать их, я новичок.

Заранее спасибо.

Answer 1

( ->;;)/2 в Прологе была введена для упрощения моделирования логики if..then..else.., но имеет важное отличие от императивных языков: без ветки 'else' происходит сбой, когда условие не выполняется.

Теперь вы пропустите ветку else в эвристике /3. Это может быть задумано, но я думаю, что если samePlace(Head1,Head2) где-то имеет значение true, это не сможет вернуть значение, и, таким образом, начинается возврат в вызывающий код. По моему опыту, это часто является причиной для последующих странных сообщений об ошибках, таких как то, что вы сообщаете.

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

heuristic([],[],0).
heuristic([Head1|Tail1],[Head2|Tail2], H):-
   heuristic(Tail1, Tail2, H1),
   (   not(samePlace(Head1,Head2))
   ->  H is H1 + 1
   ;   H is H1
   ).