Tower of Hanoi
Print the minimum sequence of moves that transfers all disks from the first peg to the third peg.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Move a stack of disks from peg \(1\) to peg \(3\), using peg \(2\) as auxiliary storage, while never placing a larger disk on top of a smaller one. Print the minimum number of moves and one optimal sequence.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
The recursive structure is the whole problem.
To move \(n\) disks from peg \(A\) to peg \(C\):
first move the top \(n - 1\) disks from \(A\) to the spare peg \(B\)
then move the largest disk from \(A\) to \(C\)
finally move the \(n - 1\) disks from \(B\) to \(C\)
That decomposition is forced, because the largest disk cannot move until every smaller disk has been cleared away, and once it moves, those smaller disks must still be transferred onto it.
The minimum move count therefore satisfies \[ T(n) = 2T(n - 1) + 1, \] with \(T(1) = 1\), so \[ T(n) = 2^n - 1. \]
Pseudocode
Natural algorithm flow before dropping to the concrete C++ implementation.
To move \(n\) disks from peg \(A\) to peg \(C\) using peg \(B\):
if \(n = 0\), stop
recursively move \(n - 1\) disks from \(A\) to \(B\)
print the move \(A \to C\)
recursively move \(n - 1\) disks from \(B\) to \(C\)
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(2^n)\), because that many moves must be printed
Memory: \(O(n)\) recursion depth
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
void solve(int disks, int from, int auxiliary, int to, std::vector<std::pair<int, int>>& moves) {
if (disks == 0) {
return;
}
solve(disks - 1, from, to, auxiliary, moves);
moves.push_back({from, to});
solve(disks - 1, auxiliary, from, to, moves);
}
int main() {
int n;
std::cin >> n;
std::vector<std::pair<int, int>> moves;
moves.reserve(static_cast<std::size_t>((1LL << n) - 1));
solve(n, 1, 2, 3, moves);
std::cout << moves.size() << '\n';
for (const auto& move : moves) {
std::cout << move.first << ' ' << move.second << '\n';
}
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
The output size already forces exponential work, so recursion is perfectly natural here.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.