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