#include <iostream>
using namespace std;
int moves;
/*
We have three pegs. On each of these pegs is a series
of disks decreasing in size from the bottom of the peg to the top of the peg. The goal is to move
all these disks to another peg following these rules:
-Only one disk can be moved at a time.
-Only the topmost disk of any given peg can be moved to another peg.
-A larger disk cannot be placed ontop a smaller disk.
Params:
diskSize refers to the maximum number of disks we wish to move. If we have 5 disks and we wish
to move all five disks to another peg then this value should be 5.
5 = largest disk and 1 = smallest disk.
source is the peg where the disks currently exist.
dest is the peg we want the disks to be moved to.
spare is the peg that temporally stores disks. This is necessary in order for us to shuffle disks
around without violating the rules.
*/
void hanoi(int diskSize, int source, int spare, int dest)
{
if (diskSize < 1) return;
cout << "Goal: Move disks 1 to " << diskSize << " from pin " << source << " to pin " << dest << endl;
//Move all disks smaller than this one over to the spare.
//So if diskSize is 5, we move 4 disks to the spare. This leaves us with 1 disk
//on the source peg.
//Note the placement of the params.
//We are now using the dest peg as the spare peg. This causes each recursion to ping-pong
//the spare and dest pegs.
hanoi(diskSize - 1, source, dest, spare);
//Move the remaining disk to the destination peg.
cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
moves++;
//Move the disks we just moved to the spare back over to the dest peg.
hanoi(diskSize - 1, spare, source, dest);
}
int main()
{
moves = 0;
//Move all 3 disks from peg 1 to peg 2 using peg 2 as a temporary.
hanoi(3, 1, 2, 3);
cout << "Done in " << moves << " moves." << endl;
return 0;
}