search

jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

Chapter 1 Exercise 1b Page 44 Error #106

Closed benkha closed 5 years ago

benkha commented 5 years ago

In Exercise 1b) of Chapter 1, it says

"For the first move ,move disk 1 to peg 1 if n is even and to peg 2 if n is odd. Then repeatedly make the only legal move that does not undo the previous move. If no such move exists, the puzzle is solved."

I think there is a problem with "make the only legal move that does not undo the previous move", since it's possible for there to be more than one legal move that does not undo the previous move.

Consider n = 2. After the first step We have moved disk 1 to peg 1. There are two possible legal moves that doesn't undo the first move:

  1. Move disk 2 to peg 2.
  2. Move disk 1 to peg 2.
echuber2 commented 5 years ago

Perhaps instead: "the only legal move that does not move the same disk that was just moved." At any rate, moving the same disk twice in a row could be construed as undoing the first move.

jeffgerickson commented 5 years ago

Already changed to "Then repeatedly make the only legal move that involves a different disk from the previous move."