prolog - 8-puzzle 在 prolog 中有一个使用曼哈顿距离的解决方案

Question

8 拼图将由 3x3 列表位置列表表示，其中空框将由值 9 表示，如下所示:[[9,1,3],[5,2,6],[4, 7,8]]

可能性解:8 拼图的初始位置只有一半是可解的。有一个公式可以让你从一开始就知道你是否能解决这个谜题。要确定一个8-puzzle是否可解，对于每个包含值N的方格，计算当前单元格后面有多少个小于N的数字。以初始状态为例:

1 没有数字小于 = 0

空 (9) - 必须随后 3,5,2,6,4,7,8 = 7

3 有 = 1 到 2

5 有随后到 2,4 = 2

2 下面没有数字发生 = 0

6 随后是 4 = 1

4 没有数字小于 = 0

7 = 0

之后没有次要号码

8 没有数字小于 = 0

之后，我们计算空位和空位之间的曼哈顿距离
位置 (3.3)。对于上面的例子，空框在位置(1.2)，所以
曼哈顿距离是:
d = 绝对 (3-1) + 绝对 (3-2) = 3
最后，将所有计算值相加。如果结果是偶数，则意味着
谜题是可以解决的，但奇怪的是不能解决。
0 +7 +1 +2 +0 +1 +0 +0 +0 +3 = 14

该解决方案旨在创建一个知识库，其中包含板上数字的所有可能状态，我们将看到当前位置之后有多少个数字小于 N。

这是我的代码:

%***********************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).

问题是我犯了一个错误，因为在某些情况下我可以有多个选择，例如>:

|  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).

posC(C,Pc)的正确解是posC(3,1)，即1；但是还有其他一些后果有时会导致错误的输出......我在我的代码中做错了什么以及如何更改它？

Answer 1

这个答案从不同的角度看问题:

单板配置使用复合结构表示 board/9 .

等于滑动单件的配置通过关系连接 m/2 .

所以让我们定义 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)).

---

Almost done!To connect the steps, we use the meta-predicate path/4 together with length/2 for performing iterative deepening.

The following problem instances are from @CapelliC's answer:

?- 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 = [...] ? ;
...