prolog knowledge-management 8-puzzle

8-puzzle tiene una solución en prolog usando la distancia de manhattan



knowledge-management (2)

Aquí hay un solucionador , no una respuesta a la pregunta original. Joel76 ya abordó el problema en los comentarios, y así obtendrá la merecida reputación cuando responda.

Pero el 8-puzzle fue interesante de resolver y plantea algún problema de eficiencia. Este es mi mejor esfuerzo, donde utilicé la biblioteca ( nb_set ) para intentar lograr una eficiencia razonable en la enumeración de soluciones completas .

Nota: nb_set es necesario para realizar un seguimiento de los visitados también en las rutas fallidas. La alternativa es a :- dynamic visited/1. pero eso resultó ser demasiado lento.

/* File: 8-puzzle.pl Author: Carlo,,, Created: Feb 4 2013 Purpose: solve 8-puzzle */ :- module(eight_puzzle, [eight_puzzle/3 ]). :- use_module(library(nb_set)). % test cases from Stack Overflow thread with Joel76 test0(R) :- eight_puzzle([1,2,3,4,5,6,7,8,0], [1,0,3, 5,2,6, 4,7,8], R). test1(R) :- eight_puzzle([1,2,3,4,5,6,7,8,0], [8,7,4, 6,0,5, 3,2,1], R). %% eight_puzzle(+Target, +Start, -Moves) is ndet % % public interface to solver % eight_puzzle(Target, Start, Moves) :- empty_nb_set(E), eight_p(E, Target, Start, Moves). %% -- private here -- eight_p(_, Target, Target, []) :- !. eight_p(S, Target, Current, [Move|Ms]) :- add_to_seen(S, Current), setof(Dist-M-Update, ( get_move(Current, P, M), apply_move(Current, P, M, Update), distance(Target, Update, Dist) ), Moves), member(_-Move-U, Moves), eight_p(S, Target, U, Ms). %% get_move(+Board, +P, -Q) is semidet % % based only on coords, get next empty cell % get_move(Board, P, Q) :- nth0(P, Board, 0), coord(P, R, C), ( R < 2, Q is P + 3 ; R > 0, Q is P - 3 ; C < 2, Q is P + 1 ; C > 0, Q is P - 1 ). %% apply_move(+Current, +P, +M, -Update) % % swap elements at position P and M % apply_move(Current, P, M, Update) :- assertion(nth0(P, Current, 0)), % constrain to this application usage ( P > M -> (F,S) = (M,P) ; (F,S) = (P,M) ), nth0(S, Current, Sv, A), nth0(F, A, Fv, B), nth0(F, C, Sv, B), nth0(S, Update, Fv, C). %% coord(+P, -R, -C) % % from linear index to row, col % size fixed to 3*3 % coord(P, R, C) :- R is P // 3, C is P mod 3. %% distance(+Current, +Target, -Dist) % % compute Manatthan distance between equals values % distance(Current, Target, Dist) :- aggregate_all(sum(D), ( nth0(P, Current, N), coord(P, Rp, Cp), nth0(Q, Target, N), coord(Q, Rq, Cq), D is abs(Rp - Rq) + abs(Cp - Cq) ), Dist). %% add_to_seen(+S, +Current) % % fail if already in, else store % add_to_seen(S, [A,B,C,D,E,F,G,H,I]) :- Sig is A*100000000+ B*10000000+ C*1000000+ D*100000+ E*10000+ F*1000+ G*100+ H*10+ I, add_nb_set(Sig, S, true)

Caso de prueba que Joel76 planteó para mostrar el error en mi primer esfuerzo:

?- time(eight_puzzle:test1(R)). % 25,791 inferences, 0,012 CPU in 0,012 seconds (100% CPU, 2137659 Lips) R = [5, 8, 7, 6, 3, 0, 1, 2, 5|...] ; % 108,017 inferences, 0,055 CPU in 0,055 seconds (100% CPU, 1967037 Lips) R = [5, 8, 7, 6, 3, 0, 1, 2, 5|...] ; % 187,817,057 inferences, 93,761 CPU in 93,867 seconds (100% CPU, 2003139 Lips) false.

El 8-puzzle estará representado por una lista 3x3 de posiciones de listas donde el cuadro vacío estará representado por el valor 9, como se muestra a continuación: [[9,1,3], [5,2,6], [4, 7,8]]

Posibilidad de solución: solo la mitad de las posiciones iniciales del 8-puzzle son solucionables. Hay una fórmula que permite saber desde el principio si puedes resolver el rompecabezas. Para determinar si un 8-puzzle es solvente, para cada cuadrado que contenga un valor N se calcula cuántos números hay menos de N después de la celda actual. Por ejemplo, al estado inicial:

  • 1 no hay números menos entonces = 0
  • Vacío (9) - tiene que posteriormente 3,5,2,6,4,7,8 = 7
  • 3 tienen = 1 a 2
  • 5 tiene subsecuentemente a 2,4 = 2
  • 2 no hay número debajo de él sucederá = 0
  • 6 es subsecuentemente 4 = 1
  • 4 sin números menos entonces = 0
  • 7 no hay números menores después = 0
  • 8 sin números menos entonces = 0

Después de eso, calculamos la distancia de Manhattan entre la posición del vacío y la posición (3.3). Para el ejemplo anterior, el cuadro vacío está en la posición (1.2), por lo que la distancia de Manhattan es: d = abs (3-1) + abs (3-2) = 3 Finalmente, sume todos los valores calculados. Si el resultado es par, implica que el acertijo puede resolverse, pero es extraño que no se resuelva. 0 +7 +1 +2 +0 +1 +0 +0 +0 +3 = 14

La solución está diseñada para crear una base de conocimiento con todos los estados posibles de un número en el tablero y veremos cuántos números hay menos de N después de la posición actual.

Aquí está mi código:

%***********************Have Solution********************************* posA(9,8). posA(8,7). posA(7,6). posA(6,5). posA(5,4). posA(4,3). posA(3,2). posA(2,1). posA(1,0). posB(9,7). posB(8,7). posB(8,6). posB(7,6). posB(7,5). posB(7,4). posB(6,5). posB(6,4). posB(6,3). posB(6,2). posB(5,4). posB(5,3). posB(5,2). posB(5,1). posB(5,0). posB(4,3). posB(4,2). posB(3,2). posB(3,1). posB(2,1). posB(2,0). posB(1,0). posC(9,6). posC(8,6). posC(8,5). posC(7,6). posC(7,5). posC(7,4). posC(6,5). posC(6,4). posC(6,3). posC(5,4). posC(5,3). posC(5,2). posC(4,3). posC(4,2). posC(4,1). posC(4,0). posC(3,2). posC(3,1). posC(3,0). posC(2,1). posC(1,0). posD(9,5). posD(8,5). posD(8,4). posD(7,5). posD(7,4). posD(7,3). posD(6,5). posD(6,4). posD(6,3). posD(6,2). posD(5,4). posD(5,3). posD(5,2). posD(5,1). posD(4,3). posD(4,2). posD(4,1). posD(5,0). posD(3,2). posD(3,1). posD(3,0). posD(2,1). posD(1,0). posE(9,4). posE(8,4). posE(8,3). posE(7,4). posE(7,3). posE(7,2). posE(6,4). posE(6,3). posE(6,2). posE(6,1). posE(5,4). posE(5,3). posE(5,2). posE(5,1). posE(5,0). posE(4,3). posE(4,2). posE(4,1). posE(4,0). posE(3,2). posE(3,1). posE(3,0). posE(2,1). posE(2,0). posE(1,0). posF(9,3). posF(8,3). posF(8,2). posF(7,1). posF(7,2). posF(7,3). posF(6,0). posF(6,1). posF(6,2). posF(6,3). posF(5,0). posF(5,1). posF(5,2). posF(5,3). posF(4,0). posF(4,1). posF(4,2). posF(4,3). posF(2,0). posF(2,1). posF(3,0). posF(3,1). posF(3,2). posF(1,0). posG(9,2). posG(8,0). posG(8,1). posG(8,2). posG(7,0). posG(7,1). posG(7,2). posG(6,0). posG(6,1). posG(6,2). posG(5,0). posG(5,1). posG(5,2). posG(4,0). posG(4,1). posG(4,2). posG(3,0). posG(3,1). posG(3,2). posG(2,0). posG(2,1). posG(1,0). posH(9,1). posH(8,0). posH(8,1). posH(7,0). posH(7,1). posH(6,0). posH(6,1). posH(5,0). posH(5,1). posH(4,0). posH(4,1). posH(3,0). posH(3,1). posH(2,0). posH(1,1). posH(1,0). posI(9,0). posI(8,0). posI(7,0). posI(6,0). posI(5,0). posI(4,0). posI(3,0). posI(2,0). posI(1,0). haveSolution([[A,B,C],[D,E,F],[G,H,I]]):- distManhattan([A,B,C,D,E,F,G,H,I], Z), posA(A,Pa), posB(B,Pb), posC(C,Pc), posD(D,Pd), posE(E,Pe), posF(F,Pf), posG(G,Pg), posH(H,Ph), posI(I,Pi), P is Pa+Pb+Pc+Pd+Pe+Pf+Pg+Ph+Pg+Pi+Z, 0 is P mod 2, write(''The 8-puzzle have solution''). %%*************************Manhattan distance*********************** distManhattan([A,B,C,D,E,F,G,H,I], Dist):- A=9, Dist is abs(3-1)+abs(3-1), !; B=9, Dist is abs(3-1)+abs(3-2), !; C=9, Dist is abs(3-1)+abs(3-3), !; D=9, Dist is abs(3-2)+abs(3-1), !; E=9, Dist is abs(3-2)+abs(3-2), !; F=9, Dist is abs(3-2)+abs(3-3), !; G=9, Dist is abs(3-3)+abs(3-1), !; H=9, Dist is abs(3-3)+abs(3-2), !; I=9, Dist is abs(3-3)+abs(3-3).

El problema es que estoy cometiendo un error porque hay situaciones en las que puedo tener más de una alternativa, por ejemplo>:

| 1 | 9 | 3 | | 5 | 2 | 6 | | 4 | 7 | 8 | posA(1,0)+posB(9,7)+posC(3,1)+posD(5,2)+posE(2,0)+posF(6,1)+posG(4,0)+posH(7,0)+posI(8,0).

La solución correcta para posC (C, Pc) es posC (3,1), es decir 1; pero hay otras ramificaciones que a veces causan resultados incorrectos ... ¿Qué estoy haciendo mal en mi código y cómo puedo cambiarlo?

Esta respuesta trata de ver el problema en cuestión desde un punto de vista diferente:

  • Las configuraciones de placa única se representan utilizando la board/9 estructura compuesta board/9 .
  • Las configuraciones que son iguales a deslizar una sola pieza se conectan por relación m/2 .

¡Comencemos y definamos m/2 !

m(board('' '',B,C,D,E,F,G,H,I), board(D, B ,C,'' '',E,F,G,H,I)). m(board('' '',B,C,D,E,F,G,H,I), board(B,'' '',C, D ,E,F,G,H,I)).


m(board(A,'' '',C,D,E,F,G,H,I), board('' '',A, C , D, E ,F,G,H,I)). m(board(A,'' '',C,D,E,F,G,H,I), board( A ,C,'' '', D, E ,F,G,H,I)). m(board(A,'' '',C,D,E,F,G,H,I), board( A ,E, C , D,'' '',F,G,H,I)).


m(board(A,B,'' '',D,E,F,G,H,I), board(A,'' '',B,D,E, F ,G,H,I)). m(board(A,B,'' '',D,E,F,G,H,I), board(A, B ,F,D,E,'' '',G,H,I)).


m(board(A,B,C,'' '',E,F,G,H,I), board('' '',B,C,A, E ,F, G ,H,I)). m(board(A,B,C,'' '',E,F,G,H,I), board( A ,B,C,E,'' '',F, G ,H,I)). m(board(A,B,C,'' '',E,F,G,H,I), board( A ,B,C,G, E ,F,'' '',H,I)).


m(board(A,B,C,D,'' '',F,G,H,I), board(A, B ,C,'' '',D, F ,G, H ,I)). m(board(A,B,C,D,'' '',F,G,H,I), board(A,'' '',C, D ,B, F ,G, H ,I)). m(board(A,B,C,D,'' '',F,G,H,I), board(A, B ,C, D ,F,'' '',G, H ,I)). m(board(A,B,C,D,'' '',F,G,H,I), board(A, B ,C, D ,H, F ,G,'' '',I)).


m(board(A,B,C,D,E,'' '',G,H,I), board(A,B,'' '',D, E ,C,G,H, I )). m(board(A,B,C,D,E,'' '',G,H,I), board(A,B, C ,D,'' '',E,G,H, I )). m(board(A,B,C,D,E,'' '',G,H,I), board(A,B, C ,D, E ,I,G,H,'' '')).


m(board(A,B,C,D,E,F,'' '',H,I), board(A,B,C,'' '',E,F,D, H ,I)). m(board(A,B,C,D,E,F,'' '',H,I), board(A,B,C, D ,E,F,H,'' '',I)).


m(board(A,B,C,D,E,F,G,'' '',I), board(A,B,C,D,'' '',F, G ,E, I )). m(board(A,B,C,D,E,F,G,'' '',I), board(A,B,C,D, E ,F,'' '',G, I )). m(board(A,B,C,D,E,F,G,'' '',I), board(A,B,C,D, E ,F, G,I,'' '')).


m(board(A,B,C,D,E,F,G,H,'' ''), board(A,B,C,D,E,'' '',G, H ,F)). m(board(A,B,C,D,E,F,G,H,'' ''), board(A,B,C,D,E, F ,G,'' '',H)).


¡Casi termino! Para conectar los pasos, usamos la ruta de metadato / 4 junto con la length/2 para realizar la profundización iterativa.

Las siguientes dos instancias de problema son tomadas de esta respuesta por @CapelliC :

?- length(Path,N), path(m,Path,/* from */ board(1,'' '',3,5,2,6,4,7, 8 ), /* to */ board(1, 2 ,3,4,5,6,7,8,'' '')). N = 6, Path = [board(1,'' '',3,5,2,6,4,7,8), board(1,2,3,5,'' '',6,4,7,8), board(1,2,3,'' '',5,6,4,7,8), board(1,2,3,4,5,6,'' '',7,8), board(1,2,3,4,5,6,7,'' '',8), board(1,2,3,4,5,6,7,8,'' '')] ? ; N = 12, Path = [board(1,'' '',3,5,2,6,4,7,8), board(1,2,3,5,'' '',6,4,7,8), board(1,2,3,5,7,6,4,'' '',8), board(1,2,3,5,7,6,'' '',4,8), board(1,2,3,'' '',7,6,5,4,8), board(1,2,3,7,'' '',6,5,4,8), board(1,2,3,7,4,6,5,'' '',8), board(1,2,3,7,4,6,'' '',5,8), board(1,2,3,'' '',4,6,7,5,8), board(1,2,3,4,'' '',6,7,5,8), board(1,2,3,4,5,6,7,'' '',8), board(1,2,3,4,5,6,7,8,'' '')] ? ; ... ?- length(Path,N), path(m,Path,/* from */ board(8,7,4,6,'' '',5,3,2, 1 ), /* to */ board(1,2,3,4, 5 ,6,7,8,'' '')). N = 27, Path = [board(8,7,4,6,'' '',5,3,2,1), board(8,7,4,6,5,'' '',3,2,1), board(8,7,4,6,5,1,3,2,'' ''), board(8,7,4,6,5,1,3,'' '',2), board(8,7,4,6,5,1,'' '',3,2), board(8,7,4,'' '',5,1,6,3,2), board('' '',7,4,8,5,1,6,3,2), board(7,'' '',4,8,5,1,6,3,2), board(7,4,'' '',8,5,1,6,3,2), board(7,4,1,8,5,'' '',6,3,2), board(7,4,1,8,5,2,6,3,'' ''), board(7,4,1,8,5,2,6,'' '',3), board(7,4,1,8,5,2,'' '',6,3), board(7,4,1,'' '',5,2,8,6,3), board('' '',4,1,7,5,2,8,6,3), board(4,'' '',1,7,5,2,8,6,3), board(4,1,'' '',7,5,2,8,6,3), board(4,1,2,7,5,'' '',8,6,3), board(4,1,2,7,5,3,8,6,'' ''), board(4,1,2,7,5,3,8,'' '',6), board(4,1,2,7,5,3,'' '',8,6), board(4,1,2,'' '',5,3,7,8,6), board('' '',1,2,4,5,3,7,8,6), board(1,'' '',2,4,5,3,7,8,6), board(1,2,'' '',4,5,3,7,8,6), board(1,2,3,4,5,'' '',7,8,6), board(1,2,3,4,5,6,7,8,'' '')] ? ; N = 29, Path = [...] ? ; ...

Quiero expandir esta respuesta en los próximos días ... ¿Qué sigue?

  • Más visualización (es)
  • Código del visualizador.
  • Heurística diferente
  • Una generalización de path/4 que utiliza heurística admisible.
  • Mediciones de tiempo de ejecución empírico.
  • Reflexiones sobre varias posibles compensaciones de tiempo / espacio.