このディレクトリの索引
%  
%  再帰を使わず、かつ、バックトラックを駆使したハノイの塔
%  

:- dynamic(ハノイの塔/3).
:- dynamic(ハノイの塔/1).
:- dynamic(ハノイの塔/0).
:- dynamic(履歴/3).


ハノイの塔(N) :-
        ハノイの塔列の生成(N),
        ハノイの塔_2(1),
        listing(履歴).

ハノイの塔列の生成(N) :-
        findall(M,between(1,N,M),A),
        assertz(履歴(A,[],[])),
        assertz(ハノイの塔(A,[],[])),
        between(1,1000000,N2),
        N3 is N2 + 1,
        assertz((ハノイの塔_2(N2) :- ハノイの塔,ハノイの塔_2(N3))),
        N3 = 1000000,
        assertz(ハノイの塔_2(1000000)).

ハノイの塔 :-
        ハノイの塔([],[],_),!.
ハノイの塔 :-
        ハノイの塔([A|R],B,C),
        \+(履歴(R,[A|B],C)),
        重ね検査(A,B),
        (
            asseretz(ハノイの塔(R,[A|B],C)),
            retract(ハノイの塔([A|R],B,C)),
            asserz(履歴(R,[A|B],C));
            retract(履歴(R,[A|B],C)),
            asseretz(ハノイの塔([A|R],B,C)),
            retract(ハノイの塔(R,[A|B],C)),
            fail).
ハノイの塔 :-
        ハノイの塔([A|R],C,B),
        \+(履歴(R,C,[A|B])),
        重ね検査(A,B),
        (
            asseretz(ハノイの塔(R,C,[A|B])),
            retract(ハノイの塔([A|R],C,B)),
            asserz(履歴(R,C,[A|B]));
            retract(履歴(R,C,[A|B])),
            asseretz(ハノイの塔([A|R],C,B)),
            retract(ハノイの塔(R,C,[A|B])),
            fail).
ハノイの塔 :-
        ハノイの塔(B,[A|R],C),
        \+(履歴([A|B],R,C)),
        重ね検査(A,B),
        (
            asseretz(ハノイの塔([A|B],R,C)),
            retract(ハノイの塔(B,[A|R],C)),
            asserz(履歴([A|B],R,C));
            retract(履歴([A|B],R,C)),
            asseretz(ハノイの塔(B,[A|R],C)),
            retract(ハノイの塔([A|B],R,C)),
            fail).
ハノイの塔 :-
        ハノイの塔(B,C,[A|R]),
        \+(履歴([A|B],C,R)),
        重ね検査(A,B),
        (
            asseretz(ハノイの塔([A|B],C,R)),
            retract(ハノイの塔(B,C,[A|R])),
            asserz(履歴([A|B],C,R));
            retract(履歴([A|B],C,R)),
            asseretz(ハノイの塔(B,C,[A|R])),
            retract(ハノイの塔([A|B],C,R)),
            fail).
ハノイの塔 :-
        ハノイの塔(C,[A|R],B),
        \+(履歴(C,R,[A|B])),
        重ね検査(A,B),
        (
            asseretz(ハノイの塔(C,R,[A|B])),
            retract(ハノイの塔(C,[A|R],B)),
            asserz(履歴(C,R,[A|B]));
            retract(履歴(C,R,[A|B])),
            asseretz(ハノイの塔(C,[A|R],B)),
            retract(ハノイの塔(C,R,[A|B])),
            fail).
ハノイの塔 :-
        ハノイの塔(C,B,[A|R]),
        \+(履歴(C,[A|B],R)),
        重ね検査(A,B),
        (
            asseretz(ハノイの塔(C,[A|B],R)),
            retract(ハノイの塔(C,B,[A|R])),
            asserz(履歴(C,[A|B],R));
            retract(履歴(C,[A|B],R)),
            asseretz(ハノイの塔(C,B,[A|R])),
            retract(ハノイの塔(C,[A|B],R)),
            fail).

重ね検査(A,[]).
重ね検査(A,[B|_]) :-
        A @< B.