PROGRAM Towers_of_Hanoi
!-----------------------------------------------------------------------
! Program to solve the Towers of Hanoi puzzle recursively, using
! subroutine Move.  Identifiers used:: labels for the pegs 
!   Number_of_Disks     : number of disks
!   Move                : subroutine to move the disks
!
!  Input:   Number_of_Disks
!  Output:  User prompts and a sequence of moves that solves 
!           the puzzle.
!-----------------------------------------------------------------------

  CHARACTER(*), PARAMETER :: Peg1 = "A",  Peg2 = "B", Peg3 = "C"
  INTEGER :: Number_of_Disks

  WRITE (*, '(1X, A)', ADVANCE = "NO") "Enter number of disks: "
  READ *, Number_of_Disks
  PRINT *
  CALL Move( Number_of_Disks, Peg1, Peg2, Peg3 )

CONTAINS

  !--Move---------------------------------------------------------------
  ! Recursive subroutine to move N disks from StartPeg to EndPeg using
  ! AuxPeg as an auxiliary peg.  Variables used are:
  !   N        : number of disks
  !   StartPeg : peg containing the disks
  !   EndPeg   : peg to which disks are to be moved
  !   AuxPeg   : extra peg used to store disks being moved
  !
  ! Accepts: N, StartPeg, AuxPeg, EndPeg.
  ! Output : A sequence of moves that solves the puzzle.
  !---------------------------------------------------------------------
  
  RECURSIVE SUBROUTINE Move(N, StartPeg, AuxPeg, EndPeg)
  
    INTEGER, INTENT(IN) :: N
    CHARACTER(*), INTENT(IN) :: StartPeg, AuxPeg, EndPeg
  
    IF (N == 1) THEN  ! Anchor
       PRINT *, "Move disk from ", StartPeg, " to ", EndPeg
 
    ELSE              ! Inductive step
       ! Move n - 1 disks from StartPeg to AuxPeg 
       ! using EndPeg as an auxiliary peg}
       CALL Move(N - 1, StartPeg, EndPeg, AuxPeg)
  
       ! Move disk from StartPeg to EndPeg}
       CALL Move(1, StartPeg, " ", EndPeg)
  
       ! Move n - 1 pegs from AuxPeg to EndPeg
       ! using StartPeg as an auxiliary peg}
       CALL Move(N - 1, AuxPeg, StartPeg, EndPeg)
    END IF
  
  END SUBROUTINE Move

END PROGRAM Towers_of_Hanoi