*/
после( [Пусто | Спис], [Фшк | Спис1], 1) :-
% Стоимости всех дуг равны 1
перест( Пусто, Фшк, Спис, Спис1).
% Переставив Пусто и Фшк, получаем СПИС1
перест( П, Ф, [Ф | С], [П | С] ) :-
расст( П, Ф, 1).
перест( П, Ф, [Ф1 | С], [Ф1 | С1] ) :-
перест( П, Ф, С, С1).
расст( X/Y, X1/Y1, Р) :-
% Манхеттеновское расстояние между клетками
расст1( X, X1, Рх),
расст1( Y, Y1, Ру),
Р is Рх + Py.
расст1( А, В, Р) :-
Р is А-В, Р >= 0, ! ;
Р is B-A.
% Эвристическая оценка h равна сумме расстояний фишек
% от их 'целевых' клеток плюс 'степень упорядоченности',
% умноженная на 3
h( [ Пусто | Спис], H) :-
цель( [Пусто1 | Цспис] ),
сумрасст( Спис, ЦСпис, Р),
упоряд( Спис, Уп),
Н is Р + 3*Уп.
сумрасст( [ ], [ ], 0).
сумрасст( [Ф | С], [Ф1 | С1], Р) :-
расст( Ф, Ф1, Р1),
сумрасст( С, Cl, P2),
Р is P1 + Р2.
упоряд( [Первый | С], Уп) :-
упоряд( [Первый | С], Первый, Уп).
упоряд( [Ф1, Ф2 | С], Первый, Уп) :-
очки( Ф1, Ф2, Уп1),
упоряд( [Ф2 | С], Первый, Уп2),
Уп is Уп1 + Уп2.
упоряд( [Последний], Первый, Уп) :-
очки( Последний, Первый, Уп).
очки( 2/2, _, 1) :- !. % Фишка в центре - 1 очко
очки( 1/3, 2/3, 0) :- !.
% Правильная последовательность - 0 очков
очки( 2/3, 3/3, 0) :- !.
очки( 3/3, 3/2, 0) :- !.
очки( 3/2, 3/1, 0) :- !.
очки( 3/1, 2/1, 0) :- !.
очки( 2/1, 1/1, 0) :- !.
