Tower of hanoi Iterative

[mattchin92]

Do you all got idea how to write the tower of hanoi in iterative ?

[JLBorges]

#include <iostream>
#include <cstdint>
#include <limits>

int main()
{
    constexpr std::size_t NPEGS = 3U ;
    const char peg[NPEGS] = { 'A', 'B', 'C' } ;
    constexpr std::size_t MAX = std::numeric_limits<std::uintmax_t>::digits ;

    std::size_t ndisks ;
    std::cout << "ndisks ( 1 - " << MAX << ")? " ;
    std::cin >> ndisks ;

   if( ndisks > 0 && ndisks < MAX )
   {
      const std::uintmax_t num_moves = ( 1U << ndisks ) - 1 ; // 2^n - 1
      std::cout << ndisks << " disks, " << num_moves << " moves\n" ;

      // see: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution
      for( std::uintmax_t nmove = 1 ; nmove <= num_moves ; ++nmove )
      {
          const auto from = ( nmove & (nmove-1) ) % NPEGS ;
          const auto to = ( ( nmove | (nmove-1) ) + 1 ) % NPEGS ;
          std::cout << nmove << ". from " << peg[from] << " to " << peg[to] << '\n' ;
      }
   }
}

http://ideone.com/3kDnZi

[mattchin92]

the solution is restrict for 3 disks only.If let say it contains 100 disks..this solution is not suitable. Do u have more idea?Means when i key in 4 disks,the output will be result to the second peg but not the last peg..

[JLBorges]

> If let say it contains 100 disks..this solution is not suitable.

Repeat: // see http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution
That meant: read the article if you need more information.

If you had bothered to read it, you would have got to:

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem.

http://en.wikipedia.org/wiki/Tower_of_Hanoi#With_four_pegs_and_beyond

[mattchin92]

But izit can use the even and odd number to solve this problem ?any idea of this?

[JLBorges]

The minimum number of moves required is 2^N - 1 where N is the number of disks. With 16 disks, we would need to print out 65,535 moves. Theoretically, a program can be written (using a large integer library) for any number of disks; in practice, assuming that one line can be printed in one nanosecond, printing out all the moves for 32 disks would take about 136 years.

> But izit can use the even and odd number to solve this problem ?any idea of this?

If you mean that, with three pegs, at the end we want all the disks to be on the last peg (peg C), yes. We have to take into account whether the number of disks is even or odd.

#include <iostream>
#include <cstdint>
#include <limits>
#include <utility>

int main()
{
    constexpr std::size_t NPEGS = 3U ;
    char peg[NPEGS] = { 'A', 'B', 'C' } ;
    constexpr std::size_t MAX = std::numeric_limits<std::uintmax_t>::digits ;

    std::size_t ndisks ;
    std::cout << "ndisks ( 1 - " << MAX << ")? " ;
    std::cin >> ndisks ;

   if( ndisks > 0 && ndisks < MAX )
   {
       // we want all disks to end up on peg C; so
       // if the number of disks is even, swap moves to peg B and peg C
       if( ndisks%2 == 0 ) std::swap( peg[1], peg[2] ) ;

      const std::uintmax_t num_moves = ( 1U << ndisks ) - 1 ; // 2^n - 1
      std::cout << ndisks << " disks, " << num_moves << " moves\n" ;

      // see: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution
      for( std::uintmax_t nmove = 1 ; nmove <= num_moves ; ++nmove )
      {
          const auto from = ( nmove & (nmove-1) ) % NPEGS ;
          const auto to = ( ( nmove | (nmove-1) ) + 1 ) % NPEGS ;
          std::cout << nmove << ". from " << peg[from] << " to " << peg[to] << '\n' ;
      }
   }
}