prolog - 8 パズルはプロローグにマンハッタン距離を使用した解があります

Question

8 パズルは、[[9,1,3]、[5,2,6]、[4、[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 です。しかし、時々誤った出力を引き起こす他の影響があります...コードで何が間違っているのですか?どうすればそれを変更できますか?

score 3 · Accepted Answer

この回答は、別の観点から問題を見ています。

シングルボード構成は、複合構造を使用して表されますboard/9。
1 つのピースをスライドさせることまで等しい構成は、リレーションによって接続され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 ))。

ここに画像の説明を入力

ほぼ完了！ステップを接続するために、メタ述語 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 = [...] ? ;
...

score 0 · Accepted Answer

これはソルバーであり、元の質問に対する回答ではありません。Joel76 はすでにコメントでこの問題に対処しているため、彼が回答すると、当然の評判が得られます。

しかし、8 パズルは解くのが面白く、効率の問題がありました。これが私の最善の努力です。完全なソリューションの列挙で合理的な効率を達成するためにライブラリ（ nb_set ）を使用しました。

注: nb_set は、失敗したパスでも訪問済みを追跡するために必要です。代替手段は a です:- 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.

prolog - 8 パズルはプロローグにマンハッタン距離を使用した解があります

2 に答える 2

Related

Reference