Print('\n'.join(pegs_to_strings(pegs_dct))) def printHanoi(pegs):ĭisc = "-" * (0 if r>=len(peg) else peg) You can then feed your movements to that function.
Hanoi towers visualzier software#
Plugging in "from" = 0, "to" = 2 N % 3, "spare" = 2 N-1 % 3, we get (suppressing the %3's): hanoi(0, 2**N, 2**(N-1), N): visualizer has the functionality of a debugger as well as having two new software visualization tools. The original Hanoi algorithm is: hanoi(from, to, spare, N): This could be changed with not much work. Is a slight "cheat": they're moving the disks from peg 0 to peg 2 N % 3, rather than a fixed, This is also true for the last step of the algorithm, so we see that actually the authors' algorithm This leaves 2 (N-1) % 3 for the "spare" peg. Here goes:įirst note: at the middle step x = 2 N-1 of this algorithm, the "from" peg is 0, and the "to" peg is 2 N % 3. (X|(X-1))+1 is not necessarily deeply linked with the Hanoi problem or it doesn't need to be it's enough that it has the copying property and that it happens to produce the correct permutations in the correct order.Īntti.huima's solution is essentially correct, but I wanted something more rigorous, and it was too big to fit in a comment. This isn't an overtly difficult task because there are only 6 possible permutations of the three integers 0.2 and the permutations progress in a logical order in the algorithm. Now then of all the functions that have this property that they create copies of themselves around powers of two but with offsets, the authors have selected those that produce modulo 3 the correct permutations. This creates the "0,0,1" pattern for the from pegs which is visible with different permutations in the table above (check rows 2, 4 and 6 for 0,0,1 and rows 1, 2, 3 for 0,0,2, and rows 5, 6, 7 for 1,1,0, all permuted versions of the same pattern). Now by the recursion rule, at (2 ** (N-2)) you need to have movedisk(0, 1) and at (2 ** (N-1)) + 2 ** (N-2) movedisk (1, 2). the recursive solution to towers of Hanoi works so that if you want to move N disks from peg A to C, you first move N-1 from A to B, then you move the bottom one to C, and then you move again N-1 disks from B to C. The recursive solution starts with hanoi(0, 2, 1, N), so at the middle row (2 ** (N-1)) you must have movedisk(0, 2). I already have a recursive solution in Python, which prints the moves I should play to solve the problem, but I would like to visualize it and see the pieces moving. The expression (X | (X-1)) + 1 sets the lowest zero bit which has ones to its right, and clears these ones, so it has similar properties as expected: 1 -> 2Īs to why these sequences actually produce the correct peg numbers, let's consider the FROM column. I recently started learning more about recursion in Python and quickly got myself into the Tower of Hanoi problem. This implements the "copy" property, the addition of the middle row implements the permutation part. The trick is that because the middle row is always at an exact power of two and thus has exactly one bit set, the part after the middle row equals the part before it when you add the middle row value (4 in this case) to the rows (i.e. So the solution length grows in the sequence 1, 3, 7, 15.
In essence, hanoi(from, to, spare, N):Ĭlearly hanoi( _, _, _, 1) takes one move, and hanoi ( _, _, _, k) takes as many moves as 2 * hanoi( _, _, _, k-1) + 1. The recursive solution to towers of Hanoi works so that if you want to move N disks from peg A to C, you first move N-1 from A to B, then you move the bottom one to C, and then you move again N-1 disks from B to C.
0 kommentar(er)
