Laborator 11

Laborator 11

solve :- StartingState = [1,3,3,0,0],

depth_first_search([],StartingState,Solution),

write(Solution),nl.

depth_first_search(CurrentPath,CurrentState,Solution) :-

CurrentState=[-1,0,0,3,3],

Solution=[CurrentState|CurrentPath].

depth_first_search(CurrentPath,CurrentState,Solution) :-

successor(CurrentState,NewState),

not(member(NewState,CurrentPath)),

depth_first_search([CurrentState|CurrentPath],NewState,Solution).

successor([Side,LM,LC,RM,RC],[NewSide,NewLM,LC,NewRM,RC]) :-

NewLM is LM-1*Side,

NewRM is RM+1*Side,

NewSide is (-1)*Side,

test(NewLM,LC,NewRM,RC).

successor([Side,LM,LC,RM,RC],[NewSide,LM,NewLC,RM,NewRC]) :-

NewLC is LC-1*Side,

NewRC is RC+1*Side,

NewSide is (-1)*Side,

test(LM,NewLC,RM,NewRC).

successor([Side,LM,LC,RM,RC],[NewSide,LM,NewLC,RM,NewRC]) :-

NewLC is LC-1*Side,

NewRC is RC+1*Side,

NewLM is LM-1*Side,

NewRM is RM+1*Side,

NewSide is (-1)*Side,

test(NewLM,NewLC,NewRM,NewRC).

successor([Side,LM,LC,RM,RC],[NewSide,NewLM,LC,NewRM,RC]) :-

NewLM is LM-2*Side,

NewRM is RM+2*Side,

NewSide is (-1)*Side,

test(NewLM,LC,NewRM,RC).

successor([Side,LM,LC,RM,RC],[NewSide,LM,NewLC,RM,NewRC]) :-

NewLC is LC-2*Side,

NewRC is RC+2*Side,

NewSide is (-1)*Side,

test(LM,NewLC,RM,NewRC).

test(LeftMissionaries,LeftCannibals,RightMissionaries,RightCannibals) :-

LeftMissionaries>=0,

LeftCannibals>=0,

RightMissionaries>=0,

RightCannibals>=0,

LeftMissionaries>=LeftCannibals,

RightMissionaries>=RightCannibals.

test(LeftMissionaries,LeftCannibals,RightMissionaries,RightCannibals) :-

LeftMissionaries>=0,

LeftCannibals>=0,

RightMissionaries>=0,

RightCannibals>=0,

LeftMissionaries>=LeftCannibals,

RightMissionaries=0.

test(LeftMissionaries,LeftCannibals,RightMissionaries,RightCannibals) :-

LeftMissionaries>=0,

LeftCannibals>=0,

RightMissionaries>=0,

RightCannibals>=0,

LeftMissionaries=0,

RightMissionaries>=RightCannibals.

solve2 :- breadth_first_search([[[1,3,3,0,0]]],[-1,0,0,3,3],Solution),

write(Solution),

nl.

breadth_first_search([[Node|Path]|_],TargetNode,[Node|Path]) :- Node=TargetNode.

breadth_first_search([[Node|Path]|RestPaths],TargetNode,Solution) :-

findall([NewNode,Node|Path],

(successor(Node,NewNode),not(member(NewNode,Path))),NewPaths),

append(RestPaths,NewPaths,CurrentPaths),

breadth_first_search(CurrentPaths,TargetNode,Solution).

hanoi :- StartingState = [3,0,0],

hanoiSearch([],StartingState,Solution),

reverse(Solution,S),

write(S),nl.

hanoiSearch(CurrentPath,CurrentState,Solution) :-

CurrentState=[0,0,3],

Solution=[CurrentState|CurrentPath].

hanoiSearch(CurrentPath,CurrentState,Solution) :-

successor2(CurrentState,NewState),

not(member(NewState,CurrentPath)),

hanoiSearch([CurrentState|CurrentPath],NewState,Solution).

%left to middle

successor2([Left,Middle,Right],[NewLeft,NewMiddle,Right]) :-

NewLeft is Left-1,

NewMiddle is Middle+1,

test2(NewLeft, NewMiddle, Right).

%left to right

successor2([Left,Middle,Right],[NewLeft,Middle,NewRight]) :-

NewLeft is Left-1,

NewRight is Right+1,

test2(NewLeft, Middle, NewRight).

%middle to left

successor2([Left,Middle,Right],[NewLeft,NewMiddle,Right]) :-

NewLeft is Left+1,

NewMiddle is Middle-1,

test2(NewLeft, NewMiddle, Right).

%right to left

successor2([Left,Middle,Right],[NewLeft,Middle,NewRight]) :-

NewLeft is Left+1,

NewRight is Right-1,

test2(NewLeft, Middle, NewRight).

%middle to right

successor2([Left,Middle,Right],[Left,NewMiddle,NewRight]) :-

NewRight is Right+1,

NewMiddle is Middle-1,

test2(Left, NewMiddle, NewRight).

%right to middle

successor2([Left,Middle,Right],[Left,NewMiddle,NewRight]) :-

NewRight is Right-1,

NewMiddle is Middle+1,

test2(Left, NewMiddle, NewRight).

test2(Left, Middle, Right) :- Left>=0, Middle>=0, Right>=0.