Hanoi Puzzle With forbidden moves

Question

I am trying to solve the Hanoi Puzzle, with forbidden moves. I have 3 poles, a left pole, a middle pole and a right pole. On the left pole I have 2 plates (the smallest is on the top and the biggest on the bottom) and want to get them to the right pole. You can just move one plate at a time. But here's the catch: you can't stack a larger on a smaller plate and move a plate from the left pole to the middle pole and from the middle pole to the right pole.

I have the following algorithm:

type HanoiMovement = (Integer , Char , Char)

hanoi :: Integer -> [HanoiMovement] 
hanoi n = hanoi_gen 'l' 'r' 'm' n
    where
        hanoi_gen s z aux 0 = []
        hanoi_gen s z aux n = hanoi_gen s aux z (n-1) ++ [(n,s,z)] ++ hanoi_gen aux z s (n-1)

it does generate the solution on how to move the plates, but it ignores the forbidden moves [('l','m'), ('m','r')]. How do I implement them into the algorithm?

Thank you in advance

Answer 1

Well, your current solution to the "standard" Hanoi puzzle takes advantage of the fact that, say, moving 3 discs from left to right using middle (hanoi 'l' 'r' 'm' 3) can be recursively expressed as moving 2 discs from left to middle using right (hanoi 'l' 'm' 'r' 2), then moving the '3' disc from left to right, and then moving 2 discs from middle to right using left (hanoi 'm' 'r' 'l' 2).

In order to implement your modified Hanoi puzzle, you need to modify the recursion to take into account the forbidden moves. Because the forbidden moves break the symmetry of the poles, you won't be able to define a single recursive step that works for all values of s, z, and aux.

Instead, you'll need to work through each of the cases:

data Pole = L | M | R deriving (Show)

To move n discs from L to R without using the forbidden moves, you should move n-1 discs from L to M, then move disc n from L to R, and then move n-1 discs from M to R, as usual. In other words:

hanoi L R M n 
  = hanoi L M R (n-1) ++ [(n,L,R)] ++ hanoi M R L (n-1)

However, to move n discs from L to M without using forbidden moves, you can't use the same pattern, as it would use the forbidden move (n,L,M), instead you need to first move n-1 discs from L to M, then move disc n from L to R, which is allowed, then move n-1 discs from M to L, move disc n from R back to M (also allowed), and finally move n-1 discs from L to M. As code:

hanoi L M R n
  = hanoi L M R (n-1) ++ [(n,L,R)] ++ hanoi M L R (n-1) ++
    [(n,R,M)] ++ hanoi L M R (n-1)

If you define similar patterns for all permutations of the poles and use the usual base case. That should give you your solution.

SPOILERS FOLLOW....

.

.

.

.

The remaining patterns are:

hanoi R L M n
  = hanoi R M L (n-1) ++ [(n,R,L)] ++ hanoi M L R (n-1)
hanoi R M L n
  = hanoi R L M (n-1) ++ [(n,R,M)] ++ hanoi L M R (n-1)
hanoi M R L n
  = hanoi M R L (n-1) ++ [(n,M,L)] ++ hanoi R M L (n-1) ++
    [(n,L,R)] ++ hanoi M R L (n-1)
hanoi M L R n
  = hanoi M R L (n-1) ++ [(n,M,L)] ++ hanoi R L M (n-1)

If desired, these can be simplified somewhat with a helper, as follows, though it would be hard to see this pattern without writing them all out in detail first:

hanoi :: Pole -> Pole -> Pole -> Int -> [(Int,Pole,Pole)]
hanoi _ _ _ 0 = []
-- handle the "hard" cases with a helper:
hanoi L M R n = hanoi' L M R n
hanoi M R L n = hanoi' M R L n
-- the rest are straightforward
hanoi s z aux n = hanoi s aux z (n-1) ++ [(n,s,z)] ++ hanoi aux z s (n-1)

hanoi' s z aux n
  = hanoi s z aux (n-1) ++ [(n,s,aux)] ++ hanoi z s aux (n-1) ++
    [(n,aux,z)] ++ hanoi s z aux (n-1)

Full runnable example:

data Pole = L | M | R deriving (Show)

hanoi :: Pole -> Pole -> Pole -> Int -> [(Int,Pole,Pole)]
hanoi _ _ _ 0 = []
-- handle the "hard" cases with a helper:
hanoi L M R n = hanoi' L M R n
hanoi M R L n = hanoi' M R L n
-- the rest are straightforward
hanoi s z aux n = hanoi s aux z (n-1) ++ [(n,s,z)] ++ hanoi aux z s (n-1)

hanoi' s z aux n
  = hanoi s z aux (n-1) ++ [(n,s,aux)] ++ hanoi z s aux (n-1) ++
    [(n,aux,z)] ++ hanoi s z aux (n-1)

main = do
  print $ hanoi L R M 2
  print $ hanoi L R M 3

which gives solutions for 2 and 3 discs:

[(1,L,R),(1,R,M),(2,L,R),(1,M,L),(1,L,R)]
[(1,L,R),(1,R,M),(2,L,R),(1,M,L),(2,R,M),(1,L,R),(1,R,M),(3,L,R),
 (1,M,L),(1,L,R),(2,M,L),(1,R,M),(2,L,R),(1,M,L),(1,L,R)]

These appear to be correct.