Design a non recursive algorithm for the towers of hanoi puzzle?

Answer 1

public class TowersOfHanoi{

public static void main(String []args){

new TowersOfHanoi().start();

}

public void start(){

String []tOH=showSteps(4);//if there are 4 disks

System.out.println("Towers of Hanoi step by step!");

for(int k=0;k<tOH.length;k++){

System.out.println("Step "+(k+1)+": Move a disk from "+tOH[k].charAt(0)+" to "+tOH[k].charAt(1));

}

}

public String []changeString(String []array,char a, char b){

for(int i=0;i<array.length;i++){

for(int j=0;j<array[i].length();j++){

if(array[i].charAt(j)==b){

array[i]=array[i].substring(0,j)+a+array[i].substring(j+1);

} else if(array[i].charAt(j)==a){

array[i]=array[i].substring(0,j)+b+array[i].substring(j+1);

}

}

}

return array;

}

public String []showSteps(int n){//how many n disks are there?

String []data={"A","B","C"};

String []Array=new String[(int)(Math.pow(2,n))-1];

for(int i=1;i<=Array.length;i=i*2+1){

int middle=(i-1)/2;

Array[middle]="AC";

String []tempArray=new String[middle];

for(int left=0;left<middle;left++){

tempArray[left]=Array[left];

}

tempArray=changeString(tempArray,'C','B');

for(int o=0;o<middle;o++){

Array[o]=tempArray[o];

}

tempArray=changeString(tempArray,'B','A');

tempArray=changeString(tempArray,'A','C');

for(int o=middle+1;o<i;o++){

Array[o]=tempArray[o-middle-1];

}

}

return Array;

}

}

Answer 2

The following program is written in C++ but should be easy enough to adapt to any language.

The recursive algorithm can be found in the move() function.

#include<iostream>

#include<string>

#include<sstream>

#include<vector>

// Typedef: associates a character (label) with an array

using Peg=std::pair<char,std::vector<size_t>>;

// Globals:

Peg A, B, C;

size_t moves;

void print_peg (const Peg& peg)

{

std::cout<<peg.first<<": ";

for (auto disc:peg.second)

std::cout<<disc<<' ';

std::cout<<std::endl;

}

void print_all_pegs ()

{

print_peg (A);

print_peg (B);

print_peg (C);

std::cout<<std::endl;

}

// Moves n discs from peg X to peg Y using peg Z as spare.

void move (size_t n, Peg& X, Peg& Y, Peg& Z)

{

// Stop recursions when there's less than 1 disc to move.

if (n<1) return;

// Move n-1 discs from peg X to peg Z using peg Y as spare.

move (n-1, X, Z, Y);

// Store disc n.

const size_t disc {X.second.back()};

// Move disc n from peg X to peg Y.

X.second.pop_back();

Y.second.push_back (disc);

// Print the move.

std::cout

<< "#" << ++moves << ": "

<< "move disc " << disc << ' '

<< "from " << X.first << ' '

<< "to " << Y.first << std::endl;

print_all_pegs();

// Move n-1 discs from peg Z to peg Y using peg X as spare.

move (n-1, Z, Y, X);

}

size_t enter_discs ()

{

size_t discs {};

while (true)

{

std::string input {};

std::cout<<"How many discs would you like to play with? ";

std::cin>>input;

std::stringstream ss {};

ss<<input;

if (ss>>discs && 0<discs)

break;

std::cout<<"Invalid input."<<std::endl;

}

std::cout<<std::endl;

return discs;

}

bool play_again()

{

std::string valid {"YNyn"};

char input {};

while (valid.find(input)==valid.npos)

{

std::cout<<"Play again? ";

std::cin>>input;

}

return valid.find(input)%2==0;

}

int main()

{

// Label the pegs.

A.first='A';

B.first='B';

C.first='C';

while (true)

{

// Input no. of discs to play with.

size_t discs {enter_discs()};

// Initialise globals.

moves=0;

for (size_t disc{0}; disc<discs; ++disc)

A.second.push_back (discs-disc);

// Print the initial state of the pegs.

std::cout<<"Start:"<<std::endl;

print_all_pegs();

// Move all discs from peg A to peg C using peg B as spare.

move (discs, A, C, B);

if (!play_again()) break;

C.second.clear();

}

return 0;

}

Answer 3

recursive:

solve (int n, int i, int j, int k)

{

. if (n==1) printf ("Move one from %d to %d\n", i, j);

. else {

. . solve (n-1, i, k); /* 1st step */

. . solve (1, i, j); /* 2nd step */

. . solve (n-1, k, j); /* 3rd step */

. }

}

non-recursive:

solve (int n, int i, int j, int k)

{

. push (n, i, j, k);

. while (! empty) {

. . pop (&n, &i, &j, &k);

. . if (n==1) printf ("Move one from %d to %d\n", i, j);

. . else {

. . . push (n-1, k, j); /* 3rd step */

. . . push (1, i, j); /* 2nd step */

. . . push (n-1, i, k); /* 1st step */

. . }

. }

}

Answer 4

I don't want to spoil your fun, let it be sufficient to say that it is not trivial, but not that hard either. If you are to lazy to do it, consult wikipedia (attached link).