Print the moves that shift a tower of disks from one peg to another.
What to build
A recursive function which solves a problem that looks very hard, in only a few lines.
Requirements
- There are three pegs: A, B and C. All n disks start on A, and must end on C.
- Only one disk can move at a time, and a larger disk can never sit on a smaller one. Disk 1 is the smallest.
- For each move, print
move disk D from X to Y. - Finally, print
N moves.
Input
One whole number n.
Output
One line per move, then the total.
Constraints
n is from 1 to 8.
Example
Input:
2
Output:
move disk 1 from A to B
move disk 2 from A to C
move disk 1 from B to C
3 moves
Why it works
The largest disk can only move when all the others are out of the way. That gives two smaller versions of the same problem, one on each side of that single move. The base case of zero disks stops the calls, and the number of moves is 2 ** n - 1.
Examples
Example 1 · Input
1
Expected output
move disk 1 from A to C 1 moves
Example 2 · Input
2
Expected output
move disk 1 from A to B move disk 2 from A to C move disk 1 from B to C 3 moves
Hints
Hint 1
To move n disks from A to C, first move n - 1 disks out of the way onto B.
Hint 2
Then move disk n from A to C, and move the n - 1 disks from B to C.
Hint 3
Write solve(n, from, to, spare). When n is 0 there is nothing to do.
Solution
Show one correct solution (try it yourself first)
let moves = 0;
function solve(n, from, to, spare) {
if (n === 0) {
return;
}
solve(n - 1, from, spare, to);
console.log(`move disk ${n} from ${from} to ${to}`);
moves++;
solve(n - 1, spare, to, from);
}
const n = Number(prompt());
solve(n, "A", "C", "B");
console.log(`${moves} moves`);