Scheme: Towers of Hanoi (recursion)

Question

I'd like to start off by saying this is homework; so I'm not asking for a solution, just some tips. I've been ruminating on this for about a week now. Every solution I come up with doesn't do it recursively, seeing as I can't manage to wrap my head around doing it recursively with the list as the only parameter. My professor said they were able to do it with about 6 helper functions.

As mentioned, I have to solve the problem taking taking the list as the only parameter. Here's an example of what I've got on my latest attempt.

(define (sumSublists lst)
  (if (= (length lst) 0)
      0
      (+ (length (car lst)) (sumSublists (cdr lst)))
  )
)

(define (hanoi towersNum)
  (sub1 (sumSublists towersNum))

    (if (= (sumSublists towersNum) 1)
        (print towersNum)
        (begin (if (= (sumSublists towersNum) 1)
                   (print towersNum)
                   (hanoi '((car towersNum) (cddr towersNum) (cadr towersNum)))
               )
               (if (= (sub1 (sumSublists towersNum)) 1)
                   (print towersNum)
                   (hanoi '((car towersNum) (cadr towersNum) (cddr towersNum)))
               )
               (if (= (sub1 (sumSublists towersNum)) 1)
                   (print towersNum)
                   (hanoi '((cddr towersNum) (cadr towersNum) (car towersNum))) 
               )
        )
    )
)

sumSublists returns how many disks there are in the game. I'm getting an infinite loop since every time it gets used it takes the same value, thus not ever reducing the value. My problem with that, is I'm so used to imperative and OOP with the use of variables that I'm not sure how I can do this when Hanoi only takes one parameter.

The code for Hanoi is my attempt to turn my project from C++ into Scheme.

Any help is appreciated. I'm using Dr. Racket as my IDE by the way.

Answer 1

Tower of Hanoi is an inherently recursive problem and it has an elegant recursive solution. I won't give you the solution outright, but I'll explain the intuition behind the solution. Consider:

        +---+                     |                       |
        | 1 |                     |                       |
    +-----------+                 |                       |
    |     2     |                 |                       |
+-------------------+             |                       |
|         3         |             |                       |
+-------------------+   +-------------------+   +-------------------+

          A                       B                       C

Given n discs, the smallest disc is labeled 1 and the largest disc is labeled n. Our job is to move all the discs from stack A to stack C while maintaining the invariant that a bigger disc may never be placed on top of a smaller disc. Without this invariant, the solution would be trivial.

Now, the only way we can move disc n from A to C is by first moving all the discs above it from A to B.

          |                       |                       |
          |                       |                       |
          |                     +---+                     |
          |                     | 1 |                     |
+-------------------+       +-----------+                 |
|         3         |       |     2     |                 |
+-------------------+   +-------------------+   +-------------------+

          A                       B                       C

Our solution is now simple. We can solve our problem in three simple steps. First, we move all the discs above disc n from A to B. Next, we move disc n from A to C. Finally, we move the remaining discs from B to C.

Our problem of moving all the discs from A to C has now been divided into two subproblems:

1. Move all the discs smaller than disc n from A to B.
2. Move all the discs smaller than disc n from B to C.

How do we solve these subproblems? We don't have to. By the principle of recursion, we have already solved these subproblems.

Now, we have three stacks labeled A, B and C. However, we want to talk about these stacks in terms of source, destination and auxiliary stacks. When solving the problem of moving disc n from A to C, we call A the source and C the destination. In addition, we need to make use of B which we call the auxiliary stack.

An important thing to notice is that the source, destination and auxiliary stacks keep on changing. For the problem “moving disc n from A to C” the source was A and the destination was C. However, for the problem “moving disc n - 1 from A to B” the source is A but the destination is B. The third stack (not source nor destination) is always the auxiliary stack.

This should give you enough insight to solve the Tower of Hanoi problem. When you do solve it you'll be surprised to find out how simple, elegant and straightforward the solution is compared to imperative code.

Answer 2

If you know how to solve it with the three arguments holding the three lists A, B and C, you already know how to solve it with the one argument holding the three lists in a list, (A B C).

The problem is counting, as you're not allowed to use a separate argument to hold the number in it. Never mind that, you can count by making a list, its length to serve as the number. And if a list's length is n, it is easy to make a list with length n-1 from it. So in the end all you need is null?.

This scheme would have you always move items from the first entry on the argument list to the second, using the head element as temporary, where you'd open and close new "levels" as needed. The three "poles" would have to be named, to be sorted back into the original order for the final return.

(cf. another answer of mine which discusses the actual recursive algorithm itself).