Iterative Implementation of Towers of Hanoi Here is an implementation of Towers of Hanoi based on few observed patterns1 from the easier recursive solution:

function [] = myTowersOfHanoi(N, from, to, alt)
  % Accepts three integers: N - number of disks  
  % from - number of start tower, to - number of end tower, alt - free tower. 
  % Returs string outputs with succesive moves to complete the task of solving
  % the Towers of Hanoi with N disks moved from tower with number stored
  % in the second argument to one with number in third arg.

  totalNumberOfMoves = (2 ^ N) - 1;

  M = generateDiskMoves(totalNumberOfMoves);

  % These are the paths of disks if N is odd.
  path1 = [from, alt, to];  % Path of disk with odd number: from-&gt;alt-&gt;to 
  path2 = [from, to, alt];  % Path of disk with even number.

  currentPositions = ones(1, N); % index-disk number, value-number of moves

  len = numel(path1);

  % If N (numer of disks) is even the paths are swapped.
  if mod(N, 2) == 0
    [path2, path1] = swapArrays(path1, path2);  
  end  

  % Solve
  for i = M 
    from = -1;
    to = -1;

    if mod(i, 2) == 0  % if number of disk, i is even
      j = currentPositions(i); % j - number of moves for i-th disk

      % In C++ indexes: [0, size - 1] in Octave: [1, size] 
      % so: mod(j - 1, len) + 1, to avoid index = 0.
      from = path1( mod(j - 1, len) + 1); % Cycle over 1-&gt;2-&gt;3 

      j = j + 1; 

      to =  path1( mod(j - 1, len) + 1); 

      currentPositions(i) = j; % update moves of i-th disk

    else
      k = currentPositions(i);

      from = path2( mod(k - 1, len) + 1); 
      k = k + 1;  
      to =  path2( mod(k - 1, len) + 1); 

      currentPositions(i) = k;
    end  
      disp(sprintf('Move disk %d from %d to %d.', i, from, to))
  end  

end  

function [a2, a1] = swapArrays (a1, a2)
  [a2, a1] = deal(a1, a2);  
end  

% From: http://mathworld.wolfram.com/BinaryCarrySequence.html
function [M] = generateDiskMoves(N)
  % Accepts integer: N - total number of moves.
  % Returns a 1xN integer array with the first N consecutive disk moves
  % in Tower of Hanoi where the index is the move number 
  % and the value is the disk number. m - is discarded.

  [m, M] = Omega2(N); % Generate the first N terms of: "Binary Carry Sequence".

  M = M .+ 1;         % Add one and get moves of disk in Tower of Hanoi.

  if N &lt; 2            % Get only the first move.
    M = M(1);       
  end    
end  

% From : https://oeis.org/A007814
function [m, M] = Omega2(n)
  % Accepts an integer: n.
  % Returns m: max power of 2 such that 2^m divides n, and
  % M: 1-by-K matrix where M(i) is the max power of 2 such 
  % that 2^M(i) divides n.

  M = NaN * zeros(1, n);

  M(1) = 0; 
  M(2) = 1;

  for k = 3 : n
    if M(k - 2) ~= 0
      M(k) = M(k - k / 2) + 1;
    else
      M(k) = 0;
    end
  end

  m = M(end);
end 


Input: Move 4 disks from 1st to 3rd peg, 2nd is free.

myTowersOfHanoi(4, 1, 3, 2)


Output:

Move disk 1 from 1 to 2.
Move disk 2 from 1 to 3.
Move disk 1 from 2 to 3.
Move disk 3 from 1 to 2.
Move disk 1 from 3 to 1.
Move disk 2 from 3 to 2.
Move disk 1 from 1 to 2.
Move disk 4 from 1 to 3.
Move disk 1 from 2 to 3.
Move disk 2 from 2 to 1.
Move disk 1 from 3 to 1.
Move disk 3 from 2 to 3.
Move disk 1 from 1 to 2.
Move disk 2 from 1 to 3.
Move disk 1 from 2 to 3.


I would appreciate your opinion and suggestions related to:


MATLAB / Octave coding style and readability.
thoughts on / possible improvements of the algorithm.


1. The observations were that firstly: the sequence of transitions could be  described by a slightly modified formula: "Binary Carry Sequence" and secondly: individual disk transitions are following only two different cyclic paths which were based on the parity of the total number of the disks, N, and the parity of the number of the currently moving disk, i.e:
Wow. Some legible matlab code. I'm impressed. Too often matlab seems to be a "write only" language, in the sense that perl regex line noise or Iverson's APL can be write only.

No biggie, but I wouldn't mind seeing consistent comment formatting where (N, from, to, alt) appear in the left margin in each of four separate lines. Kudos for telling us about the args, anyway. In the matlab ecosystem this is maybe redundant, but speaking for myself I wouldn't mind seeing a reminder that there's no zero-origin going on here, by mentioning from &gt; 0 or something. Saying it once would suffice - to &amp; alt would clearly use the same convention. I see that later you spell this out in the "avoid index = 0" comment.

typo: Returs

Kudos on helpfully explaining that 2^N-1 is totalNumberOfMoves.

Your figure was helpful. The "from -> alt -> to" comment is on the redundant side.

Would you do the Gentle Reader a small favor, please, and bump the currentPositions and len assignments down slightly? Just a few lines. That way we have a full-line comment on the "odd" case, setting up dramatic tension for "what about even?", and the swapArrays immediately shows the even case.

Switching from j to k for the path2 case was maybe a little odd. Wouldn't hurt to stick with j, as we always assign it a value at top of loop. Switching to k made me wonder if variable value needs to survive until some subsequent iteration.

Renaming deal to swapArrays made sense, thank you.

Comment for generateDiskMoves is very nice. Except I'd delete that "m is discarded" remark, as that's not part of the public API.

Personally I view the comment for M .+ 1 as "% Convert to one-origin moves."

The "Get only the first move" comment is accurate and helpful, but consider something stronger: "% The trivial case requires just one move."

Omega2 accepts lowercase n. Consider using lowercase in the other functions. I had been thinking of upper as matrix and lower as scalar.

I wouldn't mind seeing a comment that spells out whether disk 1 is smallest or biggest disk.

As far as the algorithm goes, if results of a parity function were available, could you verify, or synthesize, the Omega2 results? Perhaps with less looping?