时间戳

首页 > 解决方案 > Prolog for 8 谜题

prolog - Prolog for 8 谜题

问题描述

在此处输入图像描述

%999 represent Blank tile.

goal([999,0,1, 2,3,4, 5,6,7]).

%To move left in any row ther are two cases:
%Case_1: Blank tile in the second index.
%Case_2: Blank tile in the third index.

% move left in the top row
move([X0,999,X2, X3,X4,X5, X6,X7,X8],
     [999,X0,X2, X3,X4,X5, X6,X7,X8]). %second

move([X0,X1,999, X3,X4,X5, X6,X7,X8],
     [X0,999,X1, X3,X4,X5, X6,X7,X8]). %third


% move left in the middle row
move([X0,X1,X2, X3,999,X5, X6,X7,X8],
     [X0,X1,X2, 999,X3,X5, X6,X7,X8]). %second

move([X0,X1,X2, X3,X4,999, X6,X7,X8]
    ,[X0,X1,X2, X3,999,X4, X6,X7,X8]). %third

% move left in the bottom row
move([X0,X1,X2, X3,X4,X5, X6,999,X8],
     [X0,X1,X2, X3,X4,X5, 999,X6,X8]). %second

move([X0,X1,X2, X3,X4,X5, X6,X7,999],
     [X0,X1,X2, X3,X4,X5, X6,999,X7]). %third

% To move right in any row there are two cases:
% Case_1: 999 tile in the first index.
% Case_2: 999 tile in the second index.

% move right in the top row
move([999,X1,X2, X3,X4,X5, X6,X7,X8],
     [X1,999,X2, X3,X4,X5, X6,X7,X8]). %first

move([X0,999,X2, X3,X4,X5, X6,X7,X8],
     [X0,X2,999, X3,X4,X5, X6,X7,X8]). %seond

%% move right in the middle row
move([X0,X1,X2, 999,X4,X5, X6,X7,X8],
     [X0,X1,X2, X4,999,X5, X6,X7,X8]). %first

move([X0,X1,X2, X3,999,X5, X6,X7,X8],
     [X0,X1,X2, X3,X5,999,X6,X7,X8]). %second

%% move right in the bottom row
move([X0,X1,X2, X3,X4,X5, 999,X7,X8],
     [X0,X1,X2, X3,X4,X5, X7,999,X8]). %first

move([X0,X1,X2, X3,X4,X5, X6,999,X8],
     [X0,X1,X2, X3,X4,X5, X6,X8,999]). %second

%It is not possible to move up when existing in the top row.
% so, moving up will only be possible from bottom and middle rows from
% the three indecies.

%% move up from the middle row
move([X0,X1,X2, 999,X4,X5, X6,X7,X8],
     [999,X1,X2, X0,X4,X5, X6,X7,X8]). %first

move([X0,X1,X2, X3,999,X5, X6,X7,X8],
     [X0,999,X2, X3,X1,X5, X6,X7,X8]). %second

move([X0,X1,X2, X3,X4,999, X6,X7,X8],
     [X0,X1,999, X3,X4,X2, X6,X7,X8]).  %third

%% move up from the bottom row
move([X0,X1,X2, X3,X4,X5, 999,X7,X8],
     [X0,X1,X2, 999,X4,X5, X3,X7,X8]). %first

move([X0,X1,X2, X3,X4,X5, X6,999,X8],
     [X0,X1,X2, X3,999,X5, X6,X4,X8]). %second

move([X0,X1,X2, X3,X4,X5, X6,X7,999],
     [X0,X1,X2, X3,X4,999, X6,X7,X5]). %third

%  moving down only from the middle and top rows from the three
%  indicies.

%  move down from the top row
move([999,X1,X2, X3,X4,X5, X6,X7,X8],
     [X3,X1,X2, 999,X4,X5, X6,X7,X8]). %first

move([X0,999,X2, X3,X4,X5, X6,X7,X8],
     [X0,X4,X2, X3,999,X5, X6,X7,X8]). %second

move([X0,X1,999, X3,X4,X5, X6,X7,X8],
     [X0,X1,X5, X3,X4,999, X6,X7,X8]). %third

%% move down from the middle row
move([X0,X1,X2, 999,X4,X5, X6,X7,X8],
     [X0,X1,X2, X6,X4,X5, 999,X7,X8]). %first

move([X0,X1,X2, X3,999,X5, X6,X7,X8],
     [X0,X1,X2, X3,X7,X5, X6,999,X8]). %second

move([X0,X1,X2, X3,X4,999, X6,X7,X8],
     [X0,X1,X2, X3,X4,X8, X6,X7,999]). %third



dfs(S, Path, Path) :-
    goal(S),!.

dfs(S, Checked, Path) :-
    % try a move
    move(S, S2),
    % ensure the resulting state is new
    \+member(S2, Checked),
    % and that this state leads to the goal
    dfs(S2, [S2|Checked], Path).

%SS: state start
%SE: state end
%path(SS, Checked, MoveList):-
   % move(SS, Snext),
   % \+member(Snext, Checked),
   % path(Snext,[Snext|Checked], [Snext, SS|MoveList]).

%path(_,_, MoveList):-
    %output(MoveList).

% Printing
%output([]) :- nl.
%output([[A,B]|MoveList]) :-
%   output(MoveList),
%   write(B), write(' -> '), write(A), nl.

find :-
    dfs([6,1,3 4,999,5, 7,2,0],_,_).

标签： prologsliding-tile-puzzle

解决方案

另一种替代解决方案，其中：

  • 状态表示为术语，并且
  • 迭代深化搜索是通过使用谓词来控制的length/2。

通过此实施，在大约 40 秒内找到了解决方案（SWI-Prolog，v.8.2.4）。

ids :-
   start(State),
   length(Moves, N),
   dfs([State], Moves, Path), !,
   show([start|Moves], Path),
   format('~nmoves = ~w~n', [N]).

dfs([State|States], [], Path) :-
   goal(State), !,
   reverse([State|States], Path).

dfs([State|States], [Move|Moves], Path) :-
   move(State, Next, Move),
   not(memberchk(Next, [State|States])),
   dfs([Next,State|States], Moves, Path).

show([], _).
show([Move|Moves], [State|States]) :-
   State = state(A,B,C,D,E,F,G,H,I),
   format('~n~w~n~n', [Move]),
   format('~w ~w ~w~n',[A,B,C]),
   format('~w ~w ~w~n',[D,E,F]),
   format('~w ~w ~w~n',[G,H,I]),
   show(Moves, States).

% Empty position is marked with '*'

start( state(6,1,3,4,*,5,7,2,0) ).

goal( state(*,0,1,2,3,4,5,6,7) ).

move( state(*,B,C,D,E,F,G,H,J), state(B,*,C,D,E,F,G,H,J), right).
move( state(*,B,C,D,E,F,G,H,J), state(D,B,C,*,E,F,G,H,J), down ).
move( state(A,*,C,D,E,F,G,H,J), state(*,A,C,D,E,F,G,H,J), left ).
move( state(A,*,C,D,E,F,G,H,J), state(A,C,*,D,E,F,G,H,J), right).
move( state(A,*,C,D,E,F,G,H,J), state(A,E,C,D,*,F,G,H,J), down ).
move( state(A,B,*,D,E,F,G,H,J), state(A,*,B,D,E,F,G,H,J), left ).
move( state(A,B,*,D,E,F,G,H,J), state(A,B,F,D,E,*,G,H,J), down ).
move( state(A,B,C,*,E,F,G,H,J), state(*,B,C,A,E,F,G,H,J), up   ).
move( state(A,B,C,*,E,F,G,H,J), state(A,B,C,E,*,F,G,H,J), right).
move( state(A,B,C,*,E,F,G,H,J), state(A,B,C,G,E,F,*,H,J), down ).
move( state(A,B,C,D,*,F,G,H,J), state(A,*,C,D,B,F,G,H,J), up   ).
move( state(A,B,C,D,*,F,G,H,J), state(A,B,C,D,F,*,G,H,J), right).
move( state(A,B,C,D,*,F,G,H,J), state(A,B,C,D,H,F,G,*,J), down ).
move( state(A,B,C,D,*,F,G,H,J), state(A,B,C,*,D,F,G,H,J), left ).
move( state(A,B,C,D,E,*,G,H,J), state(A,B,*,D,E,C,G,H,J), up   ).
move( state(A,B,C,D,E,*,G,H,J), state(A,B,C,D,*,E,G,H,J), left ).
move( state(A,B,C,D,E,*,G,H,J), state(A,B,C,D,E,J,G,H,*), down ).
move( state(A,B,C,D,E,F,*,H,J), state(A,B,C,D,E,F,H,*,J), left ).
move( state(A,B,C,D,E,F,*,H,J), state(A,B,C,*,E,F,D,H,J), up   ).
move( state(A,B,C,D,E,F,G,*,J), state(A,B,C,D,E,F,*,G,J), left ).
move( state(A,B,C,D,E,F,G,*,J), state(A,B,C,D,*,F,G,E,J), up   ).
move( state(A,B,C,D,E,F,G,*,J), state(A,B,C,D,E,F,G,J,*), right).
move( state(A,B,C,D,E,F,G,H,*), state(A,B,C,D,E,*,G,H,F), up   ).
move( state(A,B,C,D,E,F,G,H,*), state(A,B,C,D,E,F,G,*,H), left ).

运行示例：

?- time(ids).

start

6 1 3
4 * 5
7 2 0

left

6 1 3
* 4 5
7 2 0

up

* 1 3
6 4 5
7 2 0

right

1 * 3
6 4 5
7 2 0

down

1 4 3
6 * 5
7 2 0

right

1 4 3
6 5 *
7 2 0

down

1 4 3
6 5 0
7 2 *

left

1 4 3
6 5 0
7 * 2

left

1 4 3
6 5 0
* 7 2

up

1 4 3
* 5 0
6 7 2

right

1 4 3
5 * 0
6 7 2

right

1 4 3
5 0 *
6 7 2

down

1 4 3
5 0 2
6 7 *

left

1 4 3
5 0 2
6 * 7

left

1 4 3
5 0 2
* 6 7

up

1 4 3
* 0 2
5 6 7

right

1 4 3
0 * 2
5 6 7

right

1 4 3
0 2 *
5 6 7

up

1 4 *
0 2 3
5 6 7

left

1 * 4
0 2 3
5 6 7

left

* 1 4
0 2 3
5 6 7

down

0 1 4
* 2 3
5 6 7

right

0 1 4
2 * 3
5 6 7

right

0 1 4
2 3 *
5 6 7

up

0 1 *
2 3 4
5 6 7

left

0 * 1
2 3 4
5 6 7

left

* 0 1
2 3 4
5 6 7

moves = 26
% 97,719,612 inferences, 40.344 CPU in 40.991 seconds (98% CPU, 2422175 Lips)
true.

推荐阅读