O 8-puzzle no Prolog

Esta seção refere-se a um conhecido e popular quebra-cabeça de peças deslizantes que já existe há pelo menos quarenta anos. As versões anteriores mais frequentes desse quebra-cabeça têm números ou letras nas peças deslizantes, e o jogador deve deslizar as peças para novas posições para realinhar um quebra-cabeça embaralhado de volta ao alinhamento do objetivo. Para ilustração, usamos a versão 3 x 3 de 8 blocos, que é representada aqui na configuração do objetivo

Fig. 5.2

Para representar esses "estados" do quebra-cabeça, usaremos uma representação de termo do Prolog empregando '/' como separador. As posições das peças são listadas (separadas por '/') de cima para baixo e da esquerda para a direita. Use "0" para representar o ladrilho vazio (espaço). Por exemplo, o objetivo é goal(1/2/3/8/0/4/7/6/5)..

Os movimentos são descritos para o solucionador de quebra-cabeças em termos da direção em que a peça vazia deve mover.

left( A/0/C/D/E/F/H/I/J , 0/A/C/D/E/F/H/I/J ).
left( A/B/C/D/0/F/H/I/J , A/B/C/0/D/F/H/I/J ).
left( A/B/C/D/E/F/H/0/J , A/B/C/D/E/F/0/H/J ).
left( A/B/0/D/E/F/H/I/J , A/0/B/D/E/F/H/I/J ).
left( A/B/C/D/E/0/H/I/J , A/B/C/D/0/E/H/I/J ).
left( A/B/C/D/E/F/H/I/0 , A/B/C/D/E/F/H/0/I ).

up( A/B/C/0/E/F/H/I/J , 0/B/C/A/E/F/H/I/J ).
up( A/B/C/D/0/F/H/I/J , A/0/C/D/B/F/H/I/J ).
up( A/B/C/D/E/0/H/I/J , A/B/0/D/E/C/H/I/J ).
up( A/B/C/D/E/F/0/I/J , A/B/C/0/E/F/D/I/J ).
up( A/B/C/D/E/F/H/0/J , A/B/C/D/0/F/H/E/J ).
up( A/B/C/D/E/F/H/I/0 , A/B/C/D/E/0/H/I/F ).

right( A/0/C/D/E/F/H/I/J , A/C/0/D/E/F/H/I/J ).
right( A/B/C/D/0/F/H/I/J , A/B/C/D/F/0/H/I/J ).
right( A/B/C/D/E/F/H/0/J , A/B/C/D/E/F/H/J/0 ).
right( 0/B/C/D/E/F/H/I/J , B/0/C/D/E/F/H/I/J ).
right( A/B/C/0/E/F/H/I/J , A/B/C/E/0/F/H/I/J ).
right( A/B/C/D/E/F/0/I/J , A/B/C/D/E/F/I/0/J ).

down( A/B/C/0/E/F/H/I/J , A/B/C/H/E/F/0/I/J ).
down( A/B/C/D/0/F/H/I/J , A/B/C/D/I/F/H/0/J ).
down( A/B/C/D/E/0/H/I/J , A/B/C/D/E/J/H/I/0 ).
down( 0/B/C/D/E/F/H/I/J , D/B/C/0/E/F/H/I/J ).
down( A/0/C/D/E/F/H/I/J , A/E/C/D/0/F/H/I/J ).
down( A/B/0/D/E/F/H/I/J , A/B/F/D/E/0/H/I/J ).

A função heurística que usamos aqui é uma combinação de dois outros estimadores: p_fcn, a função de distância de Manhattan, e s_fcn, a função de sequência, tudo conforme explicado em Nilsson (1980), que estima o quão fora de sequência as peças estão (ao redor do lado de fora).

h_function(Puzz,H) :- p_fcn(Puzz,P),
                      s_fcn(Puzz,S),
                      H is P + 3*S.

O predicado 'move' é definido como segue.

move(P,C,left) :-  left(P,C).
move(P,C,up) :-  up(P,C).
move(P,C,right) :-  right(P,C).
move(P,C,down) :-  down(P,C).

Segue o código para p e s.

   %%% Manhattan distance 
p_fcn(A/B/C/D/E/F/G/H/I, P) :-
     a(A,Pa), b(B,Pb), c(C,Pc),
     d(D,Pd), e(E,Pe), f(F,Pf),
     g(G,Pg), h(H,Ph), i(I,Pi),
     P is Pa+Pb+Pc+Pd+Pe+Pf+Pg+Ph+Pg+Pi.

a(0,0). a(1,0). a(2,1). a(3,2). a(4,3). a(5,4). a(6,3). a(7,2). a(8,1).
b(0,0). b(1,0). b(2,0). b(3,1). b(4,2). b(5,3). b(6,2). b(7,3). b(8,2).
c(0,0). c(1,2). c(2,1). c(3,0). c(4,1). c(5,2). c(6,3). c(7,4). c(8,3).
d(0,0). d(1,1). d(2,2). d(3,3). d(4,2). d(5,3). d(6,2). d(7,2). d(8,0).
e(0,0). e(1,2). e(2,1). e(3,2). e(4,1). e(5,2). e(6,1). e(7,2). e(8,1).
f(0,0). f(1,3). f(2,2). f(3,1). f(4,0). f(5,1). f(6,2). f(7,3). f(8,2).
g(0,0). g(1,2). g(2,3). g(3,4). g(4,3). g(5,2). g(6,2). g(7,0). g(8,1).
h(0,0). h(1,3). h(2,3). h(3,3). h(4,2). h(5,1). h(6,0). h(7,1). h(8,2).
i(0,0). i(1,4). i(2,3). i(3,2). i(4,1). i(5,0). i(6,1). i(7,2). i(8,3).

   %%% the out-of-cycle function
s_fcn(A/B/C/D/E/F/G/H/I, S) :-
     s_aux(A,B,S1), s_aux(B,C,S2), s_aux(C,F,S3),
     s_aux(F,I,S4), s_aux(I,H,S5), s_aux(H,G,S6),
     s_aux(G,D,S7), s_aux(D,A,S8), s_aux(E,S9),
     S is S1+S2+S3+S4+S5+S6+S7+S8+S9.

s_aux(0,0) :- !.
s_aux(_,1).

s_aux(X,Y,0) :- Y is X+1, !.
s_aux(8,1,0) :- !.
s_aux(_,_,2).

O programa Prolog da seção anterior (5.1) e o programa descrito nesta seção podem ser usados como um solucionador de 8-puzzle.

?- solve(0/8/1/2/4/3/7/6/5, S).
   
S = [right, right, down, left, left, up, right, down] ;
...

O código para esta seção também contém um controlador de animação para demonstrar a solução (explicado na Seção 8.2).

Exercício 5.2.1 Adicionar estatísticas para o 'solve'; ou seja, retorne também o número de nós expandidos e o número de nós que ficaram abertos (no final de uma busca bem-sucedida). [Adicione qualquer outra estatística que você considere interessante de ver.]

Exercício 5.2.2 Procure na literatura um algoritmo que decida, dada uma configuração inicial S para o 8-puzzle, se o objetivo G é ou não alcançável de S. (Metade, 9! / 2 = 181.440, será alcançável. ) Implemente este algoritmo no Prolog.

Exercício 5.2.3 Modifique o programa para usar f(n) = g(n) + p_fcn(n). Essas buscas resultarão em soluções ótimas (se houver). Use as estatísticas do Exercício 5.2.1 para fazer comparações práticas entre soluções usando h(n) = p_fcn(n)+3*s_fcn(n) e h(n) = p_fcn(n).

Veja Também

• Código do Prolog para as seções 5.1, 5.2 e 8.2.
• 5.1 O algoritmo A * no Prolog
• 5.3 Busca-αβ no Prolog
• 8.2 Animando o 8-puzzle (§5.2) usando gráficos de personagens
• Prolog Tutorial Sumário