REVISED: Monday, September 15, 2025
1. OCAML TOWERS OF HANOI
The Towers of Hanoi is a game or puzzle. It consists of three vertical anchored rods of equal length and diameter, spaced an equal distance apart on a playing board. The puzzle includes a number of disks of different diameters and equal thickness with a hole in their center slightly larger than the diameter of the rods. The disks can slide onto any of the three rods. The puzzle starts with all the disks in a neat conical stack, the smallest disk at the top, in ascending order of size on one rod, the rod to the far left facing the player. The far right vertical rod can be used as a temporary resting place for the disks as they are moved back and forth between the three rods. The objective of the puzzle is to eventually move the entire stack of disks from the rod on the far left, to the rod in the middle, obeying the following rules:
A. Only one disk may be moved at a time.
B. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
C. No disk may be placed on top of a smaller disk.
A. Only one disk may be moved at a time.
B. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
C. No disk may be placed on top of a smaller disk.
The following OCaml program (* hanoi.ml *) solves the Towers Of Hanoi:
(* Define a recursive function named 'hanoi'.
'let rec' is used because the function calls itself.
It takes four arguments:
n: an integer representing the number of disks to move.
source: a character representing the starting peg.
dest: a character representing the destination peg.
aux: a character representing the auxiliary/temporary peg.
The function returns 'unit' (OCaml's equivalent of 'void') because its purpose
is to print the steps (a side effect), not to compute and return a value. *)
let rec hanoi n source dest aux =
(* Check for the base case of the recursion: when there is only one disk to move. *)
if n = 1 then
(* If there's only one disk, print the move directly from the source to the destination peg.
Printf.printf is used for formatted printing.
'%c' is a placeholder for a character.
'\n' is the newline character to move to the next line after printing. *)
Printf.printf "Move disk 1 from %c to %c\n" source dest
else
(* This is the recursive step, executed when n > 1. *)
begin
(* Step 1: Move the top (n-1) disks from the 'source' peg to the 'aux' peg.
For this sub-problem, the original 'dest' peg is used as the auxiliary peg.
This recursive call solves a smaller version of the same problem. *)
hanoi (n - 1) source aux dest;
(* Step 2: Move the largest remaining disk (the nth disk) from the 'source' peg
to the 'dest' peg. This is a single, direct move. *)
Printf.printf "Move disk %d from %c to %c\n" n source dest;
(* Step 3: Move the (n-1) disks from the 'aux' peg to the 'dest' peg.
For this final sub-problem, the original 'source' peg is used as the auxiliary peg. *)
hanoi (n - 1) aux dest source
end;; (* The 'begin' and 'end' keywords are used to group multiple expressions into one. *)
(* --- Main execution part of the script --- *)
(* Define the total number of disks to be used in the puzzle.
You can change this value to solve for a different number of disks. *)
let num_disks = 3;;
(* Print an introductory message to the console indicating the start of the solution.
The '%d' is a placeholder for the integer value of 'num_disks'. *)
Printf.printf "Solving Towers of Hanoi for %d disks:\n" num_disks;;
(* This is the initial call to the 'hanoi' function to start the process.
It's called with the total number of disks ('num_disks'), and the pegs are
conventionally named 'A' (source), 'C' (destination), and 'B' (auxiliary). *)
hanoi num_disks 'A' 'C' 'B';;
2. CONCLUSION
Windows PowerShell
Copyright (C) Microsoft Corporation. All rights reserved.
Install the latest PowerShell for new features and improvements! https://aka.ms/PSWindows
OCaml version: The OCaml toplevel, version 5.3.0
Coq-LSP version: 0.2.3
Loading personal and system profiles took 1082ms.
PS C:\Users\User> ocaml C:\AI2025\hanoi.ml
Solving Towers of Hanoi for 3 disks:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
PS C:\Users\User>
3. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Pierce, Benjamin C., et al., editors. Logical Foundations. Vol. 1 of Software Foundations. Electronic Textbook, 2024. Version 6.7, http://softwarefoundations.cis.upenn.edu.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.