Robson » Little Red Book » Towers of Hanoi

Chapter 9 - Question 2

Three pegs are fixed in a line. On one of the pegs is placed a set of pierced discs. All the discs are of different diameter and the pile of discs on the peg is arranged in decreasing size as it rises up the peg.

The problem is to devise a sequence of moves that transfers the discs from their starting peg to one of the other pegs, using the third peg as a temporary store. A move transfers just one disc and is always subject to the constraint that only the top disc on a peg can be moved and it must not be placed on top of a smaller disc.

Solution 1

My current solution would benefit from some optimisation to reduce the number of moves it takes, but it works well enough for now.

PHP:

<pre><?
 
   // 4 discs
   //     1500 tests at an average of 691 moves
 
/*
   function showpegs()
   {
       global $pegs;
       for ($a = count($pegs[0]); $a >= 0; $a--)
           echo '<br/>' . $pegs[0][$a] . $pegs[1][$a] . $pegs[2][$a];
   }
*/
   function move_disc()
   {
       global $pegs;
       $a = mt_rand(0, count($pegs)-1);
       $b = mt_rand(0, count($pegs)-1);
       $valid = true;
       if ($a <> $b)
       {
           for ($c = count($pegs[0]); $c >= 0; $c--)
           {
               if ($pegs[$a][$c])
               {
                   if ($a == 2 && $pegs[$a][$c] == count($pegs[0])-$c)
                       $valid = false;
                   else
                   {
                       for ($d = count($pegs[0]); $d >= 0; $d--)
                       {
                           if ($pegs[$b][$d] > 0)
                           {
                               if ($d == count($pegs[0]))
                                   $valid = false;
                               else
                               {
                                   if ($pegs[$b][$d] > $pegs[$a][$c])
                                   {
                                       $pegs[$b][$d+1] = $pegs[$a][$c];
                                       $pegs[$a][$c] = 0;
                                       $valid = false;
                                       $modified = true;
                                   }
                                   else
                                       $valid = false;
                               }
                           }
                           if (!$valid)
                               break;
                       }
                       if ($valid)
                       {
                           $pegs[$b][0] = $pegs[$a][$c];
                           $pegs[$a][$c] = 0;
                           $modified = true;
                       }
                       $valid = false;
                   }
               }
               if (!$valid)
                   break;
           }
       }
       return $modified;
   }
   function check_win()
   {
       global $pegs;
       for ($a = 1; $a <= count($pegs); $a++)
           if ($pegs[$a] == array(4, 3, 2, 1))
               return true;
   }
 
   //for ($k = 0; $k < 500; $k++)
   //{
   
   $pegs[0] = array(4, 3, 2, 1);
   $pegs[1] = array(0, 0, 0, 0);
   $pegs[2] = array(0, 0, 0, 0);
       
   do
   {
       move_disc();
       $f++;
   } while (!check_win());
   
   //}
   
   echo 'Completed a sequence of 4 discs in ' . $f . ' moves.';
 
?>

Which produces:

Completed a sequence of 4 discs in 820 moves.

Log

© 2004-17 robson | cc unless stated