1 %------------- Command line options ---------------
   2 % -nofdcheck -N=15 -filter=move 
   3 %--------------------------------------------------
   4 
   5 %------ Initial settings
   6 
   7 number_of_moves(15).
   8 
   9 largest_disc(4).
  10 
  11 %------ Initial state
  12 
  13 initial_state(towers([4,3,2,1],[],[])).
  14 
  15 % ------ Goal state
  16 
  17 goal(towers([],[],[4,3,2,1])).
  18 
  19 % ------ all discs involved ------
  20 
  21 disc(X) :- largest_disc(X).
  22 disc(X) :- disc(#succ(X)), X != 0.
  23 
  24 % ------ legal stacks ------
  25 
  26 legalStack([]).
  27 legalStack([T]) :- disc(T).
  28 legalStack([T|[T1|S]]) :- legalStack([T1|S]), disc(T), T > T1.
  29 
  30 % ------ possible moves ------
  31 
  32 possible_state(0,towers(S1,S2,S3)) :- initial_state(towers(S1,S2,S3)).
  33 possible_state(I,towers(S1,S2,S3)) :- possible_move(I,_,towers(S1,S2,S3)), legalStack(S1), legalStack(S2), legalStack(S3).
  34 
  35 % From stack one to stack two.
  36 
  37 possible_move(#succ(I),towers([X|S1],S2,S3),towers(S1,[X|S2],S3)) :-  possible_state(I,towers([X|S1],S2,S3)),
  38                                legalMoveNumber(I),
  39                                legalStack([X|S2]).
  40 
  41 % From stack one to stack three.
  42 
  43 possible_move(#succ(I),towers([X|S1],S2,S3),towers(S1,S2,[X|S3])) :-  possible_state(I,towers([X|S1],S2,S3)),
  44                                legalMoveNumber(I),
  45                                legalStack([X|S3]).
  46 
  47 % From stack two to stack one.
  48 
  49 possible_move(#succ(I),towers(S1,[X|S2],S3),towers([X|S1],S2,S3)) :-  possible_state(I,towers(S1,[X|S2],S3)),
  50                                legalMoveNumber(I),
  51                                legalStack([X|S1]).
  52 
  53 % From stack two to stack three.
  54 
  55 possible_move(#succ(I),towers(S1,[X|S2],S3),towers(S1,S2,[X|S3])) :-  possible_state(I,towers(S1,[X|S2],S3)),
  56                                legalMoveNumber(I),
  57                                legalStack([X|S3]).
  58 
  59 % From stack three to stack one.
  60 
  61 possible_move(#succ(I),towers(S1,S2,[X|S3]),towers([X|S1],S2,S3)) :-  possible_state(I,towers(S1,S2,[X|S3])),
  62                                legalMoveNumber(I),
  63                                legalStack([X|S1]).
  64 
  65 % From stack three to stack two.
  66 
  67 possible_move(#succ(I),towers(S1,S2,[X|S3]),towers(S1,[X|S2],S3)) :-  possible_state(I,towers(S1,S2,[X|S3])),
  68                                legalMoveNumber(I),
  69                                legalStack([X|S2]).
  70 
  71 %------ actual moves ------
  72 % a solution exists if and only if there is a "possible_move"
  73 % leading to the goal.
  74 % in this case, starting from the goal, we proceed backward
  75 % to the initial state to single out the full set of moves.
  76 
  77 % Choose from the possible moves.
  78 
  79 move(I,towers(S1,S2,S3)) :- goal(towers(S1,S2,S3)), possible_state(I,towers(S1,S2,S3)).
  80 
  81 move(I,towers(S1,S2,S3)) v nomove(I,towers(S1,S2,S3)) :- 
  82         move(#succ(I),towers(A1,A2,A3)),
  83         possible_move(#succ(I),towers(S1,S2,S3),towers(A1,A2,A3)).
  84 
  85 %------ precisely one move at each step ------
  86 
  87 moveStepI(I) :- move(I,_).
  88 
  89 :- legalMoveNumber(I), not moveStepI(I). 
  90 
  91 :- legalMoveNumber(I), move(I,T1), move(I,T2), T1!=T2.
  92 
  93 legalMoveNumber(0).
  94 legalMoveNumber(#succ(I)) :- legalMoveNumber(I), number_of_moves(J), I < J.