The tower of Hanoi is a famous puzzle where we have three rods and N disks. The objective of the puzzle is to move the entire stack to another rod. You are given the number of discs N. Initially, these discs are in the rod 1. You need to print all the steps of discs movement so that all the discs reach the 3^{rd} rod. Also, you need to find the total moves.
Note: The discs are arranged such that the top disc is numbered 1 and the bottom-most disc is numbered N. Also, all the discs have different sizes and a bigger disc cannot be put on the top of a smaller disc. Refer the provided link to get a better clarity about the puzzle.
Example 1:
Input:
N = 2
Output:
move disk 1 from rod 1 to rod 2
move disk 2 from rod 1 to rod 3
move disk 1 from rod 2 to rod 3
3
Explanation: For N=2 , steps will be
as follows in the example and total
3 steps will be taken.
Example 2:
Input:
N = 3
Output:
move disk 1 from rod 1 to rod 3
move disk 2 from rod 1 to rod 2
move disk 1 from rod 3 to rod 2
move disk 3 from rod 1 to rod 3
move disk 1 from rod 2 to rod 1
move disk 2 from rod 2 to rod 3
move disk 1 from rod 1 to rod 3
7
Explanation: For N=3 , steps will be
as follows in the example and total
7 steps will be taken.
Your Task:
You don't need to read input or print anything. You only need to complete the function toh() that takes following parameters: N (number of discs), from (The rod number from which we move the disc), to (The rod number to which we move the disc), aux (The rod that is used as an auxiliary rod) and prints the required moves inside function body (See the example for the format of the output) as well as return the count of total moves made. The total number of moves are printed by the driver code.
Please take care of the case of the letters.
Expected Time Complexity: O(2^{N}).
Expected Auxiliary Space: O(N).
Constraints:
0 <= N <= 16

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: # User function Template for python3



class Solution:

    def toh(self, N, fromm, to, aux):

        # Your code here

Solutions:
class Solution:

	def toh(self, N, fromm, to, aux):
		if N > 0:
			self.toh(N - 1, fromm, aux, to)
			print('move disk', N, 'from rod', fromm, 'to rod', to)
			self.toh(N - 1, aux, to, fromm)
		return 2 ** N - 1


class Solution:

	def toh(self, N, fromm, to, aux):
		if N == 1:
			print('move disk 1 from rod %s to rod %s' % (fromm, to))
			return 1
		if N == 2:
			print('move disk 1 from rod %s to rod %s' % (fromm, aux))
			print('move disk 2 from rod %s to rod %s' % (fromm, to))
			print('move disk 1 from rod %s to rod %s' % (aux, to))
			return 3
		cnt = self.toh(N - 1, fromm, aux, to)
		print('move disk %s from rod %s to rod %s' % (N, fromm, to))
		cnt += 1
		cnt += self.toh(N - 1, aux, to, fromm)
		return cnt


class Solution:

	def toh(self, N, fromm, to, aux):
		self.total = 0

		def h(n, a, b, c):
			if n > 0:
				h(n - 1, a, c, b)
				self.total += 1
				print('move disk %d from rod %s to rod %s' % (n, a, c))
				h(n - 1, b, a, c)
		h(N, '1', '2', '3')
		return self.total


class Solution:

	def toh(self, N, fromm, to, aux):
		source = fromm
		d = to
		h = aux
		count = 0
		if N == 1:
			print('move disk 1 from rod', source, 'to rod', d)
			return 1
		count += self.toh(N - 1, source, h, d)
		count += 1
		print('move disk', N, 'from rod', source, 'to rod', d)
		count += self.toh(N - 1, h, d, source)
		return count


class Solution:

	def toh(self, n, fromm, to, aux):
		cnt = 0
		if n == 1:
			print('move disk 1 from rod ' + str(fromm) + ' to rod ' + str(to))
			return 1
		cnt += self.toh(n - 1, fromm, aux, to)
		cnt += 1
		print('move disk ' + str(n) + ' from rod ' + str(fromm) + ' to rod ' + str(to))
		cnt += self.toh(n - 1, aux, to, fromm)
		return cnt


class Solution:

	def toh(self, N, src, dest, aux):
		count = 0
		if N == 1:
			print('move disk ' + str(N) + ' from rod ' + str(src) + ' to rod ' + str(dest) + '')
			return 1
		count += Solution.toh(self, N - 1, src, aux, dest)
		print('move disk ' + str(N) + ' from rod ' + str(src) + ' to rod ' + str(dest) + '')
		count += 1
		count += Solution.toh(self, N - 1, aux, dest, src)
		return count


class Solution:

	def toh(self, N, fromm, to, aux):
		return self.solve(N, fromm, to, aux)

	def solve(self, N, fromm, to, aux):
		if N == 1:
			print('move disk 1 from rod ' + str(fromm) + ' to rod ' + str(to) + '')
			return 1
		steps = self.solve(N - 1, fromm, aux, to)
		print('move disk ' + str(N) + ' from rod ' + str(fromm) + ' to rod ' + str(to) + '')
		self.solve(N - 1, aux, to, fromm)
		return 2 * steps + 1


class Solution:

	def toh(self, N, fromm, to, aux):
		count = [0]

		def fun(N, fromm, to, aux):
			if N == 0:
				return
			else:
				fun(N - 1, fromm, aux, to)
				count[0] += 1
				print('move disk ' + str(N) + ' from rod ' + str(fromm) + ' to rod ' + str(to))
				fun(N - 1, aux, to, fromm)
		fun(N, fromm, to, aux)
		return count[0]


class Solution:
	i = 0

	def toh(self, N, fromm, to, aux) -> int:
		self.i = 1
		if N == 0:
			return 0
		self.i += self.toh(N - 1, fromm, aux, to)
		print('move disk {} from rod {} to rod {}'.format(N, fromm, to))
		self.i += self.toh(N - 1, aux, to, fromm)
		return self.i


class Solution:

	def toh(self, N, a, b, c):
		count = 0
		if N == 1:
			count += 1
			print('move disk', N, 'from rod', a, 'to rod', b)
			return 1
		count += self.toh(N - 1, a, c, b)
		count += 1
		print('move disk', N, 'from rod', a, 'to rod', b)
		count += self.toh(N - 1, c, b, a)
		return count


class Solution:

	def toh(self, N, fromm, to, aux):
		total = 0
		if N > 0:
			s1 = self.toh(N - 1, fromm, aux, to)
			print('move disk {0} from rod {1} to rod {2}'.format(N, fromm, to))
			s2 = self.toh(N - 1, aux, to, fromm)
			total += 1 + s1 + s2
		return total


class Solution:

	def toh(self, N, fromm, to, aux):
		if N <= 0:
			return
		self.toh(N - 1, fromm, aux, to)
		print('move disk {n} from rod {f} to rod {t}'.format(n=N, f=fromm, t=to))
		self.toh(N - 1, aux, to, fromm)
		return 2 ** N - 1


class Solution:

	def solve(self, N, a, b, c, i):
		if N <= 0:
			return
		self.solve(N - 1, a, c, b, i)
		print('move disk {} from rod {} to rod {}'.format(N, a, c))
		i[0] += 1
		self.solve(N - 1, b, a, c, i)

	def toh(self, N, a, c, b):
		i = [0]
		self.solve(N, a, b, c, i)
		return i[0]


class Solution:

	def toh(self, N, fromm, to, aux):
		steps = solve(N, fromm, to, aux, [0])
		return steps[0]

def solve(n, s, d, h, count):
	count[0] = count[0] + 1
	if n == 1:
		print('move disk %s from rod %s to rod %s' % (n, s, d))
		return count
	solve(n - 1, s, h, d, count)
	print('move disk %s from rod %s to rod %s' % (n, s, d))
	solve(n - 1, h, d, s, count)
	return count


class Solution:

	def toh(self, n, from_rod, to_rod, aux_rod):
		if n == 0:
			return 0
		k = self.toh(n - 1, from_rod, aux_rod, to_rod)
		print('move disk', n, 'from rod', from_rod, 'to rod', to_rod)
		p = self.toh(n - 1, aux_rod, to_rod, from_rod)
		return 1 + k + p


class Solution:

	def toh1(self, N, fromm, to, aux):
		global ans
		if N == 0:
			return
		self.toh1(N - 1, fromm, aux, to)
		ans += 1
		print('move disk ' + str(N) + ' from rod ' + str(fromm) + ' to rod ' + str(to))
		self.toh1(N - 1, aux, to, fromm)

	def toh(self, N, fromm, to, aux):
		global ans
		ans = 0
		self.toh1(N, fromm, to, aux)
		return ans


class Solution:

	def toh(self, N, fromm, to, aux):
		a = fromm
		b = aux
		c = to
		n = N

		def tohh(n, a, b, c):
			if n == 1:
				print('move disk', n, 'from rod', a, 'to rod', c)
				return
			tohh(n - 1, a, c, b)
			print('move disk', n, 'from rod', a, 'to rod', c)
			tohh(n - 1, b, a, c)
		tohh(n, a, b, c)
		k = 2 ** n - 1
		return k


class Solution:

	def __init__(self):
		self.num = 0

	def toh(self, N, fromm, to, aux):
		if N == 0:
			return
		self.toh(N - 1, fromm, aux, to)
		print('move disk ' + str(N) + ' from rod ' + str(fromm) + ' to rod ' + str(to))
		self.num = self.num + 1
		self.toh(N - 1, aux, to, fromm)
		return self.num


class Solution:

	def toh(self, n, A, C, B):
		ans = []

		def rec(n, A, C, B):
			if n == 1:
				print('move disk', n, 'from rod', A, 'to rod', C)
				temp = [1, A, C]
				ans.append(temp)
				return
			rec(n - 1, A, B, C)
			temp = [n, A, C]
			print('move disk', n, 'from rod', A, 'to rod', C)
			ans.append(temp)
			rec(n - 1, B, C, A)
		rec(n, 1, 3, 2)
		return len(ans)


class Solution:

	def toh(self, N, A, C, B):
		count = 0
		if N == 0:
			return 0
		count += self.toh(N - 1, A, B, C)
		print('move disk', N, 'from rod', A, 'to rod', C)
		count += 1
		count += self.toh(N - 1, B, C, A)
		return count


class Solution:

	def toh(self, N, from_, to, aux):
		if N == 1:
			print('move disk 1 from rod {} to rod {}'.format(from_, to))
			return 1
		moves = self.toh(N - 1, from_, aux, to)
		print('move disk {} from rod {} to rod {}'.format(N, from_, to))
		moves += 1
		moves += self.toh(N - 1, aux, to, from_)
		return moves


class Solution:

	def __init__(self, count=0):
		self.count = count

	def TOHHelper(self, N, fromm, to, aux):
		if N == 1:
			print('move disk 1 from rod', fromm, 'to rod', to)
			self.count += 1
			return
		self.TOHHelper(N - 1, fromm, aux, to)
		print('move disk', N, 'from rod', fromm, 'to rod', to)
		self.count += 1
		self.TOHHelper(N - 1, aux, to, fromm)

	def toh(self, N, fromm, to, aux):
		self.TOHHelper(N, fromm, to, aux)
		return self.count


class Solution:

	def toh(self, N, A, C, B):
		self.N = N
		self.A = A
		self.B = B
		self.C = C
		if N == 1:
			print('move disk 1 from rod', str(A), 'to rod', str(C))
			return 1
		a = self.toh(N - 1, A, B, C)
		print('move disk ' + str(N) + ' from rod', str(A), 'to rod', str(C))
		a += 1
		a += self.toh(N - 1, B, C, A)
		return a


class Solution:
	count = 0

	def tohelper(self, N, fromm, to, aux):
		if N == 1:
			print('move disk {}'.format(N) + ' from rod {}'.format(fromm) + ' to rod {}'.format(to))
			self.count += 1
			return
		if N > 0:
			self.tohelper(N - 1, fromm, aux, to)
			print('move disk {}'.format(N) + ' from rod {}'.format(fromm) + ' to rod {}'.format(to))
			self.count += 1
			self.tohelper(N - 1, aux, to, fromm)

	def toh(self, N, fromm, to, aux):
		self.tohelper(N, fromm, to, aux)
		return self.count


class Solution:

	def toh(self, N, fr, to, aux):
		if N == 1:
			print('move disk ' + str(N) + ' from rod ' + str(fr) + ' to rod ' + str(to))
			return 1
		ret = self.toh(N - 1, fr, aux, to) + 1
		print('move disk ' + str(N) + ' from rod ' + str(fr) + ' to rod ' + str(to))
		ret += self.toh(N - 1, aux, to, fr)
		return ret


class Solution:

	def toh(self, N, fromm, to, aux):
		if N == 1:
			print('move disk ' + str(N) + ' from rod ' + str(fromm) + ' to rod ' + str(to))
			return 1
		x = self.toh(N - 1, fromm, aux, to)
		print('move disk ' + str(N) + ' from rod ' + str(fromm) + ' to rod ' + str(to))
		y = self.toh(N - 1, aux, to, fromm)
		return x + y + 1


class Solution:

	def toh(self, n, fromm, to, aux):
		if n == 1:
			print('move disk', n, 'from rod', fromm, 'to rod', to)
			return 1
		c = self.toh(n - 1, fromm, aux, to)
		print('move disk', n, 'from rod', fromm, 'to rod', to)
		c += self.toh(n - 1, aux, to, fromm)
		return c + 1


class Solution:

	def toh(self, N, fromm, to, aux):
		if N == 1:
			print('move disk 1 from rod', fromm, 'to rod', to)
			return 1
		l_count = self.toh(N - 1, fromm, aux, to)
		print('move disk', N, 'from rod', fromm, 'to rod', to)
		r_count = self.toh(N - 1, aux, to, fromm)
		return l_count + r_count + 1


class Solution:

	def hanoi(n, st, en, c):
		if n == 1:
			print('move disk', n, 'from rod', st, 'to rod', en)
			c = c + 1
			return c
		ot = 6 - (st + en)
		d = Solution.hanoi(n - 1, st, ot, c)
		print('move disk', n, 'from rod', st, 'to rod', en)
		d = d + 1
		m = Solution.hanoi(n - 1, ot, en, d)
		return m

	def toh(self, N, fromm, to, aux):
		x = Solution.hanoi(N, fromm, to, 0)
		return x


class Solution:

	def toh(self, N, fromm, to, aux):
		stack = []
		n = N
		count = 0
		while len(stack) > 0 or n > 0:
			if n > 0:
				stack.append((n, fromm, to, aux))
				(to, aux) = (aux, to)
				n -= 1
			else:
				(n, fromm, to, aux) = stack.pop()
				print('move disk {n} from rod {fromm} to rod {to}'.format(n=n, fromm=fromm, to=to))
				count += 1
				(fromm, aux) = (aux, fromm)
				n -= 1
		return count