4

8-puzzle 将由一个 3x3 的列表位置列表表示，其中空框将由值 9 表示，如下所示： [[9,1,3],[5,2,6],[4, 7,8]]

可能解：8 拼图的初始位置只有一半是可解的。有一个公式可以让您从一开始就知道您是否可以解决难题。要确定是否可以解决一个 8 难题，对于每个包含值 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 = abs(3-1) + abs(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；但是还有其他一些后果有时会导致错误的输出......我在我的代码中做错了什么以及如何更改它？

4

2 回答 2

3

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

  • 单板配置使用复合结构表示board/9。
  • 相当于滑动单件的配置是通过关系连接的m/2。

所以让我们定义m/2！

m（板（''，B，C，D，E，F，G，H，I），板（D，B，C，''，E，F，G，H，I））。
m（板（''，B，C，D，E，F，G，H，I），板（B，''，C，D，E，F，G，H，I））。

在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述

m（板（A，''，C，D，E，F，G，H，I），板（''，A，C，D，E，F，G，H，I））。
m（板（A，''，C，D，E，F，G，H，I），板（A，C，''，D，E，F，G，H，I））。
m（板（A，''，C，D，E，F，G，H，I），板（A，E，C，D，''，F，G，H，I））。

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

m（板（A，B，''，D，E，F，G，H，I），板（A，''，B，D，E，F，G，H，I））。
m（板（A，B，''，D，E，F，G，H，I），板（A，B，F，D，E，''，G，H，I））。

在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述

m（板（A，B，C，''，E，F，G，H，I），板（''，B，C，A，E，F，G，H，I））。
m（板（A，B，C，''，E，F，G，H，I），板（A，B，C，E，''，F，G，H，I））。
m（板（A，B，C，''，E，F，G，H，I），板（A，B，C，G，E，F，''，H，I））。

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

m（板（A，B，C，D，''，F，G，H，I），板（A，B，C，''，D，F，G，H，I））。
m（板（A，B，C，D，''，F，G，H，I），板（A，''，C，D，B，F，G，H，I））。
m（板（A，B，C，D，''，F，G，H，I），板（A，B，C，D，F，''，G，H，I））。
m（板（A，B，C，D，''，F，G，H，I），板（A，B，C，D，H，F，G，''，I））。

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

m（板（A，B，C，D，E，''，G，H，I），板（A，B，''，D，E，C，G，H，I））。
m（板（A，B，C，D，E，''，G，H，I），板（A，B，C，D，''，E，G，H，I））。
m（板（A，B，C，D，E，''，G，H，I），板（A，B，C，D，E，I，G，H，''））。

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

m（板（A，B，C，D，E，F，''，H，I），板（A，B，C，''，E，F，D，H，I））。
m（板（A，B，C，D，E，F，''，H，I），板（A，B，C，D，E，F，H，''，I））。

在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述

m（板（A，B，C，D，E，F，G，''，I），板（A，B，C，D，''，F，G，E，I））。
m（板（A，B，C，D，E，F，G，''，I），板（A，B，C，D，E，F，''，G，I））。
m（板（A，B，C，D，E，F，G，''，I），板（A，B，C，D，E，F，G，I，''））。

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

m（板（A，B，C，D，E，F，G，H，''），板（A，B，C，D，E，''，G，H，F））。
m（板（A，B，C，D，E，F，G，H，''），板（A，B，C，D，E，F，G，''，H））。

在此处输入图像描述 在此处输入图像描述
在此处输入图像描述 在此处输入图像描述

快完成了！为了连接这些步骤，我们将 path/4与length/2执行迭代深化一起使用。

以下问题实例来自@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 = [...] ? ;
...
于 2015-07-15T22:15:09.240 回答
0

这是一个求解器，而不是原始问题的答案。Joel76 已经在评论中解决了这个问题，因此当他回答时，他将获得应有的声誉。

但是 8-puzzle 解决起来很有趣，并且带来了一些效率问题。这是我的最大努力，我使用库（nb_set）试图在完整的解决方案枚举上实现合理的效率。

注意：需要 nb_set 来跟踪失败路径上的访问。另一种选择是，:- dynamic visited/1.但结果太慢了。

/*  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)

Joel76 在我的第一次尝试中展示了这个错误的测试用例：

?- 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.
于 2013-02-08T09:39:09.700 回答