THE STAR PUZZLE : COMPUTATIONAL ASPECT

Abstract

The star puzzle is a variant of the Tower of Hanoi problem, where, in addition to the usual three
pegs, S, P and D, there is a fourth one such that all disc movements are either to or from the fourth
peg. Letting MS(n) be the minimum number of moves required to solve the star puzzle, MS(n)
satisfies the recurrence relation below
 
1 k n 1
MS(n) min 2MS(n k) 3 1 .
k
  
   
This paper studies the computational aspect of the star puzzle.