NOGDUS

Articles, Tutorials, and other things. => General Programming => : Richard Marks January 06, 2009, 02:01:15 PM



: C++ Program to Solve Towers of Hanoi
: Richard Marks January 06, 2009, 02:01:15 PM
In respect to this article (http://ccpssolutions.com/nogdusforums/index.php?topic=351.0) here is a program that will solve the Towers of Hanoi puzzles at nearly any depth.

Here I ran it in both brief and verbose output modes.
:
$ ./tohsolver -b 3
Towers of Hanoi Solver
Programmed by Richard Marks <ccpsceo@gmail.com>

7 step solution for 3 layer puzzle: "ACABCBACBABCAC"

:
$ ./tohsolver
Towers of Hanoi Solver
Programmed by Richard Marks <ccpsceo@gmail.com>

Solving 3 story tower puzzle...
Move the topmost layer from Tower A to Tower C.
Move the topmost layer from Tower A to Tower B.
Move the topmost layer from Tower C to Tower B.
Move the topmost layer from Tower A to Tower C.
Move the topmost layer from Tower B to Tower A.
Move the topmost layer from Tower B to Tower C.
Move the topmost layer from Tower A to Tower C.
Puzzle is Solved!


Here is the full C++ source.

:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>

unsigned int steps = 0;
std::string solution = "";
bool briefMode = false;
typedef unsigned int ui;
void SolveTowersOfHanoi(ui layers, ui startTower, ui destTower, ui intermediateTower)
{
if (briefMode)
{
if (0x1 == layers)
{
solution += static_cast<char>(0x40+startTower);
solution += static_cast<char>(0x40+destTower);
steps++;
}
else
{
SolveTowersOfHanoi(layers - 1, startTower, intermediateTower, destTower);
solution += static_cast<char>(0x40+startTower);
solution += static_cast<char>(0x40+destTower);
steps++;
SolveTowersOfHanoi(layers - 1, intermediateTower, destTower, startTower);
}
}
else
{
if (0x1 == layers)
{
fprintf(stdout, "Move the topmost layer from Tower %c to Tower %c.\n", 0x40+startTower, 0x40+destTower);
steps++;
}
else
{
SolveTowersOfHanoi(layers - 1, startTower, intermediateTower, destTower);

fprintf(stdout, "Move the topmost layer from Tower %c to Tower %c.\n", 0x40+startTower, 0x40+destTower);
steps++;
SolveTowersOfHanoi(layers - 1, intermediateTower, destTower, startTower);
}
}
}

// usage: $ tohsolver [-b] [layers]
int main(int argc, char* argv[])
{
fprintf(stdout, "Towers of Hanoi Solver\nProgrammed by Richard Marks <ccpsceo@gmail.com>\n\n");
ui layers;
switch(argc)
{
case 0x3:
{
std::string opt = argv[1];
if ("-b" == opt)
{
briefMode = true;
layers = atoi(argv[2]);
}
else
{
fprintf(stderr, "\nUsage: %s [-b] [layers]\n\n"
"Use -b to specify Brief Output Mode.\nlayers should be a "
"positive integer.\nBoth arguments are optional. "
"The puzzle defaults to three layers.\n\n", argv[0]);
return 1;
}
} break;

case 0x2:
{
layers = atoi(argv[1]);
} break;

default:
{
layers = 0x3;
} break;
}

if (briefMode)
{
SolveTowersOfHanoi(layers, 0x1, 0x3, 0x2);
fprintf(stdout, "%d step solution for %d layer puzzle: \"%s\"\n", steps, layers, solution.c_str());
}
else
{
fprintf(stdout, "Solving %d story tower puzzle...\n", layers);
SolveTowersOfHanoi(layers, 0x1, 0x3, 0x2);
fprintf(stdout, "Puzzle is Solved in %d steps!\n", steps);
}
return 0;
}

You're free to use this code as you wish, just keep my name and email address on it. 8)


Sorry, the copyright must be in the template.
Please notify this forum's administrator that this site is missing the copyright message for SMF so they can rectify the situation. Display of copyright is a legal requirement. For more information on this please visit the Simple Machines website.