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->alt->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->2->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 < 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)
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: