0 Replies - 1101 Views - Last Post: 30 December 2010 - 04:18 AM Rate Topic: -----

#1 zetamagica   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 11
  • Joined: 24-May 09

Hanoi in Prolog

Posted 30 December 2010 - 04:18 AM

Hello. I must implement a heuristic algorithm and use it to give solutions to Hanoi tower for 5 disks, in Prolog.
I chose A* and have written -and found- some code. First, I found a working example of A* code and adapted it to my needs and then
I wrote my possible moves for Hanoi Tower. My problems are:

I can't find an admissible heuristic that could be written in Prolog (like manhatan distance, which works for 8puzzle).
For example, a heuristic for Hanoi is One-Follows-Two, which means that whenever the second smaller disk has moved,
the smallest one must be placed on top of it. But how on earth can this be described in prolog???

My code doesnt print any solutions and im not sure whether its how ive written my moves, A*, or my useless heuristic to blame...
I run it in SWI, and test it with the command
?- solve([[],[],[1,2,3,4,5]],S).
What I get in return is
S = [] and if i try to get more options for S with ; i get
false

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%     A* Algorithm
%%%
%%%
%%%     Nodes have form    S#D#F#A
%%%            where S describes the state or configuration
%%%                  D is the depth of the node
%%%                  F is the evaluation function value
%%%                  A is the ancestor list for the node

:- op(400,yfx,'#').    /* Node builder notation */

solve(State,Soln) :- f_function(State,0,F),
                     search([State#0#F#[]],S), reverse(S,Soln).

f_function(State,D,F) :- h_function(State,H),
                         F is D + H.

search([State#_#_#Soln|_], Soln) :- goal(State).
search([B|R],S) :- expand(B,Children),
                   insert_all(Children,R,Open),
                   search(Open,S).

insert_all([F|R],Open1,Open3) :- insert(F,Open1,Open2),
                                 insert_all(R,Open2,Open3).
insert_all([],Open,Open).

insert(B,Open,Open) :- repeat_node(B,Open), ! .
insert(B,[C|R],[B,C|R]) :- cheaper(B,C), ! .
insert(B,[B1|R],[B1|S]) :- insert(B,R,S), !.
insert(B,[],[B]).

repeat_node(P#_#_#_, [P#_#_#_|_]).

cheaper( _#_#F1#_ , _#_#F2#_ ) :- F1 < F2.

expand(State#D#_#S,All_My_Children) :-
     bagof(Child#D1#F#[Move|S],
           (D1 is D+1,
             move(State,Child,Move),
	     update(State, Child, Move),
             f_function(Child,D1,F)),
           All_My_Children).

% Hanoi Solution %

goal([[], [], [1,2,3,4,5]]). % or [[], [1,2,3,4,5], []]

% possible disk moves (from T1-T6 of report)
% move shows FROM which peg we move top disk
move([[Top1 | Stack1]|OtherStacks], move12).                % from peg A to peg B
move([[Top1 | Stack1]|OtherStacks], move13).                % from peg A to peg C
move([Stack1, [Top2 | Stack2]|OtherStacks], move21).        % from peg B to peg A
move([Stack1, [Top2 | Stack2]|OtherStacks], move23).        % from peg B to peg C
move([Stack1, Stack2, [Top3 | Stack3]|OtherStacks], move31).% from peg C to peg A
move([Stack1, Stack2, [Top3 | Stack3]|OtherStacks], move32).% from peg C to peg B

% for each move, a new node must be constructed
% update shows TO which peg we move top disk
update([[Top1 | Stack1], Stack2 | OtherStacks], move12,
[Stack1, [Top1 | Stack2] | OtherStacks]).
update([[Top1 | Stack1], Stack2, Stack3 | OtherStacks], move13,
[Stack1, Stack2, [Top1 | Stack3] | OtherStacks]).
update([Stack1, [Top2 | Stack2], Stack3 | OtherStacks], move21,
[[Top2 | Stack1], Stack2, Stack3 | OtherStacks]).
update([Stack1, [Top2 | Stack2], Stack3 | OtherStacks], move23,
[Stack1, Stack2, [Top2 | Stack3] | OtherStacks]).
update([Stack1, Stack2, [Top3 | Stack3] | OtherStacks], move31,
[[Top3 | Stack1], Stack2, Stack3 | OtherStacks]).
update([Stack1, Stack2, [Top3 | Stack3] | OtherStacks], move32,
[Stack1, [Top3| Stack2], Stack3 | OtherStacks]).

% A node is legal if every ring is above a larger ring.
% We need only test the top two rings, since if these are never
% illegal then lower rings, which must have once been at the top,
% can never be in an illegal order.

legal([Peg1, Peg2, Peg3]) :-
legalTower(Peg1),
legalTower(Peg2),
legalTower(Peg3).
legalTower([]).
legalTower([A]).
legalTower([A, B|Rest]) :- A < B.

h_function(Hanoi,H):-
H is 1.



I am completely new to Prolog and I'm having great trouble understanding it... ANY help and/or advice and/or idea is welcome...

Is This A Good Question/Topic? 0
  • +

Page 1 of 1