curriculum/challenges/english/blocks/lab-tower-of-hanoi/68773ee26f332a80bc0295db.md
In this lab, you will solve the mathematical puzzle known as the Tower of Hanoi. The puzzle consists of three rods and a number of disks of different diameters.
The puzzle starts with the disks piled up on the first rod, in decreasing size, with the smallest disk on top and the largest disk on the bottom.
The goal of the Tower of Hanoi puzzle is moving all the disks to the last rod. To do that, you must follow three simple rules:
Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.
User Stories:
hanoi_solver that takes an integer representing the total number of disks of the puzzle as the argument.hanoi_solver function should solve the puzzle following the given rules in 2<sup>n</sup> - 1 moves, where n is the total number of disks.hanoi_solver function should return a string with all the moves taken to solve the puzzle, including the starting arrangement, with each move on a new line. Rods should be represented as lists of integers, (the smallest disk is represented by the number 1) with each rod separated by a space. For example, hanoi_solver(3) should return the following:[3, 2, 1] [] []
[3, 2] [] [1]
[3] [2] [1]
[3] [2, 1] []
[] [2, 1] [3]
[1] [2] [3]
[1] [] [3, 2]
[] [] [3, 2, 1]
You should have a function named hanoi_solver.
({ test: () => assert(runPython(`_Node(_code).has_function('hanoi_solver')`)) })
Your hanoi_solver function should take a single argument.
({ test: () => runPython(`
import inspect
sig = inspect.signature(hanoi_solver)
assert len(sig.parameters) == 1
`) })
Your hanoi_solver function should return a string.
({ test: () => runPython(`
assert isinstance(hanoi_solver(2), str)
assert isinstance(hanoi_solver(6), str)
assert isinstance(hanoi_solver(11), str)
`) })
hanoi_solver(2) should return [2, 1] [] []\n[2] [1] []\n[] [1] [2]\n[] [] [2, 1].
({ test: () => runPython(`
expected = """[2, 1] [] []
[2] [1] []
[] [1] [2]
[] [] [2, 1]"""
assert hanoi_solver(2) == expected
`) })
hanoi_solver(3) should return [3, 2, 1] [] []\n[3, 2] [] [1]\n[3] [2] [1]\n[3] [2, 1] []\n[] [2, 1] [3]\n[1] [2] [3]\n[1] [] [3, 2]\n[] [] [3, 2, 1].
({ test: () => runPython(`
expected = """[3, 2, 1] [] []
[3, 2] [] [1]
[3] [2] [1]
[3] [2, 1] []
[] [2, 1] [3]
[1] [2] [3]
[1] [] [3, 2]
[] [] [3, 2, 1]"""
assert hanoi_solver(3) == expected
`) })
hanoi_solver(4) should return [4, 3, 2, 1] [] []\n[4, 3, 2] [1] []\n[4, 3] [1] [2]\n[4, 3] [] [2, 1]\n[4] [3] [2, 1]\n[4, 1] [3] [2]\n[4, 1] [3, 2] []\n[4] [3, 2, 1] []\n[] [3, 2, 1] [4]\n[] [3, 2] [4, 1]\n[2] [3] [4, 1]\n[2, 1] [3] [4]\n[2, 1] [] [4, 3]\n[2] [1] [4, 3]\n[] [1] [4, 3, 2]\n[] [] [4, 3, 2, 1].
({ test: () => runPython(`
expected = """[4, 3, 2, 1] [] []
[4, 3, 2] [1] []
[4, 3] [1] [2]
[4, 3] [] [2, 1]
[4] [3] [2, 1]
[4, 1] [3] [2]
[4, 1] [3, 2] []
[4] [3, 2, 1] []
[] [3, 2, 1] [4]
[] [3, 2] [4, 1]
[2] [3] [4, 1]
[2, 1] [3] [4]
[2, 1] [] [4, 3]
[2] [1] [4, 3]
[] [1] [4, 3, 2]
[] [] [4, 3, 2, 1]"""
assert hanoi_solver(4) == expected
`) })
hanoi_solver(5) should return [5, 4, 3, 2, 1] [] []\n[5, 4, 3, 2] [] [1]\n[5, 4, 3] [2] [1]\n[5, 4, 3] [2, 1] []\n[5, 4] [2, 1] [3]\n[5, 4, 1] [2] [3]\n[5, 4, 1] [] [3, 2]\n[5, 4] [] [3, 2, 1]\n[5] [4] [3, 2, 1]\n[5] [4, 1] [3, 2]\n[5, 2] [4, 1] [3]\n[5, 2, 1] [4] [3]\n[5, 2, 1] [4, 3] []\n[5, 2] [4, 3] [1]\n[5] [4, 3, 2] [1]\n[5] [4, 3, 2, 1] []\n[] [4, 3, 2, 1] [5]\n[1] [4, 3, 2] [5]\n[1] [4, 3] [5, 2]\n[] [4, 3] [5, 2, 1]\n[3] [4] [5, 2, 1]\n[3] [4, 1] [5, 2]\n[3, 2] [4, 1] [5]\n[3, 2, 1] [4] [5]\n[3, 2, 1] [] [5, 4]\n[3, 2] [] [5, 4, 1]\n[3] [2] [5, 4, 1]\n[3] [2, 1] [5, 4]\n[] [2, 1] [5, 4, 3]\n[1] [2] [5, 4, 3]\n[1] [] [5, 4, 3, 2]\n[] [] [5, 4, 3, 2, 1].
({ test: () => runPython(`
expected = """[5, 4, 3, 2, 1] [] []
[5, 4, 3, 2] [] [1]
[5, 4, 3] [2] [1]
[5, 4, 3] [2, 1] []
[5, 4] [2, 1] [3]
[5, 4, 1] [2] [3]
[5, 4, 1] [] [3, 2]
[5, 4] [] [3, 2, 1]
[5] [4] [3, 2, 1]
[5] [4, 1] [3, 2]
[5, 2] [4, 1] [3]
[5, 2, 1] [4] [3]
[5, 2, 1] [4, 3] []
[5, 2] [4, 3] [1]
[5] [4, 3, 2] [1]
[5] [4, 3, 2, 1] []
[] [4, 3, 2, 1] [5]
[1] [4, 3, 2] [5]
[1] [4, 3] [5, 2]
[] [4, 3] [5, 2, 1]
[3] [4] [5, 2, 1]
[3] [4, 1] [5, 2]
[3, 2] [4, 1] [5]
[3, 2, 1] [4] [5]
[3, 2, 1] [] [5, 4]
[3, 2] [] [5, 4, 1]
[3] [2] [5, 4, 1]
[3] [2, 1] [5, 4]
[] [2, 1] [5, 4, 3]
[1] [2] [5, 4, 3]
[1] [] [5, 4, 3, 2]
[] [] [5, 4, 3, 2, 1]"""
assert hanoi_solver(5) == expected
`) })
hanoi_solver(n) should solve the tower of Hanoi puzzle for any positive value of n.
({ test: () => runPython(`
expected = """[6, 5, 4, 3, 2, 1] [] []
[6, 5, 4, 3, 2] [1] []
[6, 5, 4, 3] [1] [2]
[6, 5, 4, 3] [] [2, 1]
[6, 5, 4] [3] [2, 1]
[6, 5, 4, 1] [3] [2]
[6, 5, 4, 1] [3, 2] []
[6, 5, 4] [3, 2, 1] []
[6, 5] [3, 2, 1] [4]
[6, 5] [3, 2] [4, 1]
[6, 5, 2] [3] [4, 1]
[6, 5, 2, 1] [3] [4]
[6, 5, 2, 1] [] [4, 3]
[6, 5, 2] [1] [4, 3]
[6, 5] [1] [4, 3, 2]
[6, 5] [] [4, 3, 2, 1]
[6] [5] [4, 3, 2, 1]
[6, 1] [5] [4, 3, 2]
[6, 1] [5, 2] [4, 3]
[6] [5, 2, 1] [4, 3]
[6, 3] [5, 2, 1] [4]
[6, 3] [5, 2] [4, 1]
[6, 3, 2] [5] [4, 1]
[6, 3, 2, 1] [5] [4]
[6, 3, 2, 1] [5, 4] []
[6, 3, 2] [5, 4, 1] []
[6, 3] [5, 4, 1] [2]
[6, 3] [5, 4] [2, 1]
[6] [5, 4, 3] [2, 1]
[6, 1] [5, 4, 3] [2]
[6, 1] [5, 4, 3, 2] []
[6] [5, 4, 3, 2, 1] []
[] [5, 4, 3, 2, 1] [6]
[] [5, 4, 3, 2] [6, 1]
[2] [5, 4, 3] [6, 1]
[2, 1] [5, 4, 3] [6]
[2, 1] [5, 4] [6, 3]
[2] [5, 4, 1] [6, 3]
[] [5, 4, 1] [6, 3, 2]
[] [5, 4] [6, 3, 2, 1]
[4] [5] [6, 3, 2, 1]
[4, 1] [5] [6, 3, 2]
[4, 1] [5, 2] [6, 3]
[4] [5, 2, 1] [6, 3]
[4, 3] [5, 2, 1] [6]
[4, 3] [5, 2] [6, 1]
[4, 3, 2] [5] [6, 1]
[4, 3, 2, 1] [5] [6]
[4, 3, 2, 1] [] [6, 5]
[4, 3, 2] [1] [6, 5]
[4, 3] [1] [6, 5, 2]
[4, 3] [] [6, 5, 2, 1]
[4] [3] [6, 5, 2, 1]
[4, 1] [3] [6, 5, 2]
[4, 1] [3, 2] [6, 5]
[4] [3, 2, 1] [6, 5]
[] [3, 2, 1] [6, 5, 4]
[] [3, 2] [6, 5, 4, 1]
[2] [3] [6, 5, 4, 1]
[2, 1] [3] [6, 5, 4]
[2, 1] [] [6, 5, 4, 3]
[2] [1] [6, 5, 4, 3]
[] [1] [6, 5, 4, 3, 2]
[] [] [6, 5, 4, 3, 2, 1]"""
assert hanoi_solver(6) == expected
expected = """[7, 6, 5, 4, 3, 2, 1] [] []
[7, 6, 5, 4, 3, 2] [] [1]
[7, 6, 5, 4, 3] [2] [1]
[7, 6, 5, 4, 3] [2, 1] []
[7, 6, 5, 4] [2, 1] [3]
[7, 6, 5, 4, 1] [2] [3]
[7, 6, 5, 4, 1] [] [3, 2]
[7, 6, 5, 4] [] [3, 2, 1]
[7, 6, 5] [4] [3, 2, 1]
[7, 6, 5] [4, 1] [3, 2]
[7, 6, 5, 2] [4, 1] [3]
[7, 6, 5, 2, 1] [4] [3]
[7, 6, 5, 2, 1] [4, 3] []
[7, 6, 5, 2] [4, 3] [1]
[7, 6, 5] [4, 3, 2] [1]
[7, 6, 5] [4, 3, 2, 1] []
[7, 6] [4, 3, 2, 1] [5]
[7, 6, 1] [4, 3, 2] [5]
[7, 6, 1] [4, 3] [5, 2]
[7, 6] [4, 3] [5, 2, 1]
[7, 6, 3] [4] [5, 2, 1]
[7, 6, 3] [4, 1] [5, 2]
[7, 6, 3, 2] [4, 1] [5]
[7, 6, 3, 2, 1] [4] [5]
[7, 6, 3, 2, 1] [] [5, 4]
[7, 6, 3, 2] [] [5, 4, 1]
[7, 6, 3] [2] [5, 4, 1]
[7, 6, 3] [2, 1] [5, 4]
[7, 6] [2, 1] [5, 4, 3]
[7, 6, 1] [2] [5, 4, 3]
[7, 6, 1] [] [5, 4, 3, 2]
[7, 6] [] [5, 4, 3, 2, 1]
[7] [6] [5, 4, 3, 2, 1]
[7] [6, 1] [5, 4, 3, 2]
[7, 2] [6, 1] [5, 4, 3]
[7, 2, 1] [6] [5, 4, 3]
[7, 2, 1] [6, 3] [5, 4]
[7, 2] [6, 3] [5, 4, 1]
[7] [6, 3, 2] [5, 4, 1]
[7] [6, 3, 2, 1] [5, 4]
[7, 4] [6, 3, 2, 1] [5]
[7, 4, 1] [6, 3, 2] [5]
[7, 4, 1] [6, 3] [5, 2]
[7, 4] [6, 3] [5, 2, 1]
[7, 4, 3] [6] [5, 2, 1]
[7, 4, 3] [6, 1] [5, 2]
[7, 4, 3, 2] [6, 1] [5]
[7, 4, 3, 2, 1] [6] [5]
[7, 4, 3, 2, 1] [6, 5] []
[7, 4, 3, 2] [6, 5] [1]
[7, 4, 3] [6, 5, 2] [1]
[7, 4, 3] [6, 5, 2, 1] []
[7, 4] [6, 5, 2, 1] [3]
[7, 4, 1] [6, 5, 2] [3]
[7, 4, 1] [6, 5] [3, 2]
[7, 4] [6, 5] [3, 2, 1]
[7] [6, 5, 4] [3, 2, 1]
[7] [6, 5, 4, 1] [3, 2]
[7, 2] [6, 5, 4, 1] [3]
[7, 2, 1] [6, 5, 4] [3]
[7, 2, 1] [6, 5, 4, 3] []
[7, 2] [6, 5, 4, 3] [1]
[7] [6, 5, 4, 3, 2] [1]
[7] [6, 5, 4, 3, 2, 1] []
[] [6, 5, 4, 3, 2, 1] [7]
[1] [6, 5, 4, 3, 2] [7]
[1] [6, 5, 4, 3] [7, 2]
[] [6, 5, 4, 3] [7, 2, 1]
[3] [6, 5, 4] [7, 2, 1]
[3] [6, 5, 4, 1] [7, 2]
[3, 2] [6, 5, 4, 1] [7]
[3, 2, 1] [6, 5, 4] [7]
[3, 2, 1] [6, 5] [7, 4]
[3, 2] [6, 5] [7, 4, 1]
[3] [6, 5, 2] [7, 4, 1]
[3] [6, 5, 2, 1] [7, 4]
[] [6, 5, 2, 1] [7, 4, 3]
[1] [6, 5, 2] [7, 4, 3]
[1] [6, 5] [7, 4, 3, 2]
[] [6, 5] [7, 4, 3, 2, 1]
[5] [6] [7, 4, 3, 2, 1]
[5] [6, 1] [7, 4, 3, 2]
[5, 2] [6, 1] [7, 4, 3]
[5, 2, 1] [6] [7, 4, 3]
[5, 2, 1] [6, 3] [7, 4]
[5, 2] [6, 3] [7, 4, 1]
[5] [6, 3, 2] [7, 4, 1]
[5] [6, 3, 2, 1] [7, 4]
[5, 4] [6, 3, 2, 1] [7]
[5, 4, 1] [6, 3, 2] [7]
[5, 4, 1] [6, 3] [7, 2]
[5, 4] [6, 3] [7, 2, 1]
[5, 4, 3] [6] [7, 2, 1]
[5, 4, 3] [6, 1] [7, 2]
[5, 4, 3, 2] [6, 1] [7]
[5, 4, 3, 2, 1] [6] [7]
[5, 4, 3, 2, 1] [] [7, 6]
[5, 4, 3, 2] [] [7, 6, 1]
[5, 4, 3] [2] [7, 6, 1]
[5, 4, 3] [2, 1] [7, 6]
[5, 4] [2, 1] [7, 6, 3]
[5, 4, 1] [2] [7, 6, 3]
[5, 4, 1] [] [7, 6, 3, 2]
[5, 4] [] [7, 6, 3, 2, 1]
[5] [4] [7, 6, 3, 2, 1]
[5] [4, 1] [7, 6, 3, 2]
[5, 2] [4, 1] [7, 6, 3]
[5, 2, 1] [4] [7, 6, 3]
[5, 2, 1] [4, 3] [7, 6]
[5, 2] [4, 3] [7, 6, 1]
[5] [4, 3, 2] [7, 6, 1]
[5] [4, 3, 2, 1] [7, 6]
[] [4, 3, 2, 1] [7, 6, 5]
[1] [4, 3, 2] [7, 6, 5]
[1] [4, 3] [7, 6, 5, 2]
[] [4, 3] [7, 6, 5, 2, 1]
[3] [4] [7, 6, 5, 2, 1]
[3] [4, 1] [7, 6, 5, 2]
[3, 2] [4, 1] [7, 6, 5]
[3, 2, 1] [4] [7, 6, 5]
[3, 2, 1] [] [7, 6, 5, 4]
[3, 2] [] [7, 6, 5, 4, 1]
[3] [2] [7, 6, 5, 4, 1]
[3] [2, 1] [7, 6, 5, 4]
[] [2, 1] [7, 6, 5, 4, 3]
[1] [2] [7, 6, 5, 4, 3]
[1] [] [7, 6, 5, 4, 3, 2]
[] [] [7, 6, 5, 4, 3, 2, 1]"""
assert hanoi_solver(7) == expected
expected = """[8, 7, 6, 5, 4, 3, 2, 1] [] []
[8, 7, 6, 5, 4, 3, 2] [1] []
[8, 7, 6, 5, 4, 3] [1] [2]
[8, 7, 6, 5, 4, 3] [] [2, 1]
[8, 7, 6, 5, 4] [3] [2, 1]
[8, 7, 6, 5, 4, 1] [3] [2]
[8, 7, 6, 5, 4, 1] [3, 2] []
[8, 7, 6, 5, 4] [3, 2, 1] []
[8, 7, 6, 5] [3, 2, 1] [4]
[8, 7, 6, 5] [3, 2] [4, 1]
[8, 7, 6, 5, 2] [3] [4, 1]
[8, 7, 6, 5, 2, 1] [3] [4]
[8, 7, 6, 5, 2, 1] [] [4, 3]
[8, 7, 6, 5, 2] [1] [4, 3]
[8, 7, 6, 5] [1] [4, 3, 2]
[8, 7, 6, 5] [] [4, 3, 2, 1]
[8, 7, 6] [5] [4, 3, 2, 1]
[8, 7, 6, 1] [5] [4, 3, 2]
[8, 7, 6, 1] [5, 2] [4, 3]
[8, 7, 6] [5, 2, 1] [4, 3]
[8, 7, 6, 3] [5, 2, 1] [4]
[8, 7, 6, 3] [5, 2] [4, 1]
[8, 7, 6, 3, 2] [5] [4, 1]
[8, 7, 6, 3, 2, 1] [5] [4]
[8, 7, 6, 3, 2, 1] [5, 4] []
[8, 7, 6, 3, 2] [5, 4, 1] []
[8, 7, 6, 3] [5, 4, 1] [2]
[8, 7, 6, 3] [5, 4] [2, 1]
[8, 7, 6] [5, 4, 3] [2, 1]
[8, 7, 6, 1] [5, 4, 3] [2]
[8, 7, 6, 1] [5, 4, 3, 2] []
[8, 7, 6] [5, 4, 3, 2, 1] []
[8, 7] [5, 4, 3, 2, 1] [6]
[8, 7] [5, 4, 3, 2] [6, 1]
[8, 7, 2] [5, 4, 3] [6, 1]
[8, 7, 2, 1] [5, 4, 3] [6]
[8, 7, 2, 1] [5, 4] [6, 3]
[8, 7, 2] [5, 4, 1] [6, 3]
[8, 7] [5, 4, 1] [6, 3, 2]
[8, 7] [5, 4] [6, 3, 2, 1]
[8, 7, 4] [5] [6, 3, 2, 1]
[8, 7, 4, 1] [5] [6, 3, 2]
[8, 7, 4, 1] [5, 2] [6, 3]
[8, 7, 4] [5, 2, 1] [6, 3]
[8, 7, 4, 3] [5, 2, 1] [6]
[8, 7, 4, 3] [5, 2] [6, 1]
[8, 7, 4, 3, 2] [5] [6, 1]
[8, 7, 4, 3, 2, 1] [5] [6]
[8, 7, 4, 3, 2, 1] [] [6, 5]
[8, 7, 4, 3, 2] [1] [6, 5]
[8, 7, 4, 3] [1] [6, 5, 2]
[8, 7, 4, 3] [] [6, 5, 2, 1]
[8, 7, 4] [3] [6, 5, 2, 1]
[8, 7, 4, 1] [3] [6, 5, 2]
[8, 7, 4, 1] [3, 2] [6, 5]
[8, 7, 4] [3, 2, 1] [6, 5]
[8, 7] [3, 2, 1] [6, 5, 4]
[8, 7] [3, 2] [6, 5, 4, 1]
[8, 7, 2] [3] [6, 5, 4, 1]
[8, 7, 2, 1] [3] [6, 5, 4]
[8, 7, 2, 1] [] [6, 5, 4, 3]
[8, 7, 2] [1] [6, 5, 4, 3]
[8, 7] [1] [6, 5, 4, 3, 2]
[8, 7] [] [6, 5, 4, 3, 2, 1]
[8] [7] [6, 5, 4, 3, 2, 1]
[8, 1] [7] [6, 5, 4, 3, 2]
[8, 1] [7, 2] [6, 5, 4, 3]
[8] [7, 2, 1] [6, 5, 4, 3]
[8, 3] [7, 2, 1] [6, 5, 4]
[8, 3] [7, 2] [6, 5, 4, 1]
[8, 3, 2] [7] [6, 5, 4, 1]
[8, 3, 2, 1] [7] [6, 5, 4]
[8, 3, 2, 1] [7, 4] [6, 5]
[8, 3, 2] [7, 4, 1] [6, 5]
[8, 3] [7, 4, 1] [6, 5, 2]
[8, 3] [7, 4] [6, 5, 2, 1]
[8] [7, 4, 3] [6, 5, 2, 1]
[8, 1] [7, 4, 3] [6, 5, 2]
[8, 1] [7, 4, 3, 2] [6, 5]
[8] [7, 4, 3, 2, 1] [6, 5]
[8, 5] [7, 4, 3, 2, 1] [6]
[8, 5] [7, 4, 3, 2] [6, 1]
[8, 5, 2] [7, 4, 3] [6, 1]
[8, 5, 2, 1] [7, 4, 3] [6]
[8, 5, 2, 1] [7, 4] [6, 3]
[8, 5, 2] [7, 4, 1] [6, 3]
[8, 5] [7, 4, 1] [6, 3, 2]
[8, 5] [7, 4] [6, 3, 2, 1]
[8, 5, 4] [7] [6, 3, 2, 1]
[8, 5, 4, 1] [7] [6, 3, 2]
[8, 5, 4, 1] [7, 2] [6, 3]
[8, 5, 4] [7, 2, 1] [6, 3]
[8, 5, 4, 3] [7, 2, 1] [6]
[8, 5, 4, 3] [7, 2] [6, 1]
[8, 5, 4, 3, 2] [7] [6, 1]
[8, 5, 4, 3, 2, 1] [7] [6]
[8, 5, 4, 3, 2, 1] [7, 6] []
[8, 5, 4, 3, 2] [7, 6, 1] []
[8, 5, 4, 3] [7, 6, 1] [2]
[8, 5, 4, 3] [7, 6] [2, 1]
[8, 5, 4] [7, 6, 3] [2, 1]
[8, 5, 4, 1] [7, 6, 3] [2]
[8, 5, 4, 1] [7, 6, 3, 2] []
[8, 5, 4] [7, 6, 3, 2, 1] []
[8, 5] [7, 6, 3, 2, 1] [4]
[8, 5] [7, 6, 3, 2] [4, 1]
[8, 5, 2] [7, 6, 3] [4, 1]
[8, 5, 2, 1] [7, 6, 3] [4]
[8, 5, 2, 1] [7, 6] [4, 3]
[8, 5, 2] [7, 6, 1] [4, 3]
[8, 5] [7, 6, 1] [4, 3, 2]
[8, 5] [7, 6] [4, 3, 2, 1]
[8] [7, 6, 5] [4, 3, 2, 1]
[8, 1] [7, 6, 5] [4, 3, 2]
[8, 1] [7, 6, 5, 2] [4, 3]
[8] [7, 6, 5, 2, 1] [4, 3]
[8, 3] [7, 6, 5, 2, 1] [4]
[8, 3] [7, 6, 5, 2] [4, 1]
[8, 3, 2] [7, 6, 5] [4, 1]
[8, 3, 2, 1] [7, 6, 5] [4]
[8, 3, 2, 1] [7, 6, 5, 4] []
[8, 3, 2] [7, 6, 5, 4, 1] []
[8, 3] [7, 6, 5, 4, 1] [2]
[8, 3] [7, 6, 5, 4] [2, 1]
[8] [7, 6, 5, 4, 3] [2, 1]
[8, 1] [7, 6, 5, 4, 3] [2]
[8, 1] [7, 6, 5, 4, 3, 2] []
[8] [7, 6, 5, 4, 3, 2, 1] []
[] [7, 6, 5, 4, 3, 2, 1] [8]
[] [7, 6, 5, 4, 3, 2] [8, 1]
[2] [7, 6, 5, 4, 3] [8, 1]
[2, 1] [7, 6, 5, 4, 3] [8]
[2, 1] [7, 6, 5, 4] [8, 3]
[2] [7, 6, 5, 4, 1] [8, 3]
[] [7, 6, 5, 4, 1] [8, 3, 2]
[] [7, 6, 5, 4] [8, 3, 2, 1]
[4] [7, 6, 5] [8, 3, 2, 1]
[4, 1] [7, 6, 5] [8, 3, 2]
[4, 1] [7, 6, 5, 2] [8, 3]
[4] [7, 6, 5, 2, 1] [8, 3]
[4, 3] [7, 6, 5, 2, 1] [8]
[4, 3] [7, 6, 5, 2] [8, 1]
[4, 3, 2] [7, 6, 5] [8, 1]
[4, 3, 2, 1] [7, 6, 5] [8]
[4, 3, 2, 1] [7, 6] [8, 5]
[4, 3, 2] [7, 6, 1] [8, 5]
[4, 3] [7, 6, 1] [8, 5, 2]
[4, 3] [7, 6] [8, 5, 2, 1]
[4] [7, 6, 3] [8, 5, 2, 1]
[4, 1] [7, 6, 3] [8, 5, 2]
[4, 1] [7, 6, 3, 2] [8, 5]
[4] [7, 6, 3, 2, 1] [8, 5]
[] [7, 6, 3, 2, 1] [8, 5, 4]
[] [7, 6, 3, 2] [8, 5, 4, 1]
[2] [7, 6, 3] [8, 5, 4, 1]
[2, 1] [7, 6, 3] [8, 5, 4]
[2, 1] [7, 6] [8, 5, 4, 3]
[2] [7, 6, 1] [8, 5, 4, 3]
[] [7, 6, 1] [8, 5, 4, 3, 2]
[] [7, 6] [8, 5, 4, 3, 2, 1]
[6] [7] [8, 5, 4, 3, 2, 1]
[6, 1] [7] [8, 5, 4, 3, 2]
[6, 1] [7, 2] [8, 5, 4, 3]
[6] [7, 2, 1] [8, 5, 4, 3]
[6, 3] [7, 2, 1] [8, 5, 4]
[6, 3] [7, 2] [8, 5, 4, 1]
[6, 3, 2] [7] [8, 5, 4, 1]
[6, 3, 2, 1] [7] [8, 5, 4]
[6, 3, 2, 1] [7, 4] [8, 5]
[6, 3, 2] [7, 4, 1] [8, 5]
[6, 3] [7, 4, 1] [8, 5, 2]
[6, 3] [7, 4] [8, 5, 2, 1]
[6] [7, 4, 3] [8, 5, 2, 1]
[6, 1] [7, 4, 3] [8, 5, 2]
[6, 1] [7, 4, 3, 2] [8, 5]
[6] [7, 4, 3, 2, 1] [8, 5]
[6, 5] [7, 4, 3, 2, 1] [8]
[6, 5] [7, 4, 3, 2] [8, 1]
[6, 5, 2] [7, 4, 3] [8, 1]
[6, 5, 2, 1] [7, 4, 3] [8]
[6, 5, 2, 1] [7, 4] [8, 3]
[6, 5, 2] [7, 4, 1] [8, 3]
[6, 5] [7, 4, 1] [8, 3, 2]
[6, 5] [7, 4] [8, 3, 2, 1]
[6, 5, 4] [7] [8, 3, 2, 1]
[6, 5, 4, 1] [7] [8, 3, 2]
[6, 5, 4, 1] [7, 2] [8, 3]
[6, 5, 4] [7, 2, 1] [8, 3]
[6, 5, 4, 3] [7, 2, 1] [8]
[6, 5, 4, 3] [7, 2] [8, 1]
[6, 5, 4, 3, 2] [7] [8, 1]
[6, 5, 4, 3, 2, 1] [7] [8]
[6, 5, 4, 3, 2, 1] [] [8, 7]
[6, 5, 4, 3, 2] [1] [8, 7]
[6, 5, 4, 3] [1] [8, 7, 2]
[6, 5, 4, 3] [] [8, 7, 2, 1]
[6, 5, 4] [3] [8, 7, 2, 1]
[6, 5, 4, 1] [3] [8, 7, 2]
[6, 5, 4, 1] [3, 2] [8, 7]
[6, 5, 4] [3, 2, 1] [8, 7]
[6, 5] [3, 2, 1] [8, 7, 4]
[6, 5] [3, 2] [8, 7, 4, 1]
[6, 5, 2] [3] [8, 7, 4, 1]
[6, 5, 2, 1] [3] [8, 7, 4]
[6, 5, 2, 1] [] [8, 7, 4, 3]
[6, 5, 2] [1] [8, 7, 4, 3]
[6, 5] [1] [8, 7, 4, 3, 2]
[6, 5] [] [8, 7, 4, 3, 2, 1]
[6] [5] [8, 7, 4, 3, 2, 1]
[6, 1] [5] [8, 7, 4, 3, 2]
[6, 1] [5, 2] [8, 7, 4, 3]
[6] [5, 2, 1] [8, 7, 4, 3]
[6, 3] [5, 2, 1] [8, 7, 4]
[6, 3] [5, 2] [8, 7, 4, 1]
[6, 3, 2] [5] [8, 7, 4, 1]
[6, 3, 2, 1] [5] [8, 7, 4]
[6, 3, 2, 1] [5, 4] [8, 7]
[6, 3, 2] [5, 4, 1] [8, 7]
[6, 3] [5, 4, 1] [8, 7, 2]
[6, 3] [5, 4] [8, 7, 2, 1]
[6] [5, 4, 3] [8, 7, 2, 1]
[6, 1] [5, 4, 3] [8, 7, 2]
[6, 1] [5, 4, 3, 2] [8, 7]
[6] [5, 4, 3, 2, 1] [8, 7]
[] [5, 4, 3, 2, 1] [8, 7, 6]
[] [5, 4, 3, 2] [8, 7, 6, 1]
[2] [5, 4, 3] [8, 7, 6, 1]
[2, 1] [5, 4, 3] [8, 7, 6]
[2, 1] [5, 4] [8, 7, 6, 3]
[2] [5, 4, 1] [8, 7, 6, 3]
[] [5, 4, 1] [8, 7, 6, 3, 2]
[] [5, 4] [8, 7, 6, 3, 2, 1]
[4] [5] [8, 7, 6, 3, 2, 1]
[4, 1] [5] [8, 7, 6, 3, 2]
[4, 1] [5, 2] [8, 7, 6, 3]
[4] [5, 2, 1] [8, 7, 6, 3]
[4, 3] [5, 2, 1] [8, 7, 6]
[4, 3] [5, 2] [8, 7, 6, 1]
[4, 3, 2] [5] [8, 7, 6, 1]
[4, 3, 2, 1] [5] [8, 7, 6]
[4, 3, 2, 1] [] [8, 7, 6, 5]
[4, 3, 2] [1] [8, 7, 6, 5]
[4, 3] [1] [8, 7, 6, 5, 2]
[4, 3] [] [8, 7, 6, 5, 2, 1]
[4] [3] [8, 7, 6, 5, 2, 1]
[4, 1] [3] [8, 7, 6, 5, 2]
[4, 1] [3, 2] [8, 7, 6, 5]
[4] [3, 2, 1] [8, 7, 6, 5]
[] [3, 2, 1] [8, 7, 6, 5, 4]
[] [3, 2] [8, 7, 6, 5, 4, 1]
[2] [3] [8, 7, 6, 5, 4, 1]
[2, 1] [3] [8, 7, 6, 5, 4]
[2, 1] [] [8, 7, 6, 5, 4, 3]
[2] [1] [8, 7, 6, 5, 4, 3]
[] [1] [8, 7, 6, 5, 4, 3, 2]
[] [] [8, 7, 6, 5, 4, 3, 2, 1]"""
assert hanoi_solver(8) == expected
expected = """[9, 8, 7, 6, 5, 4, 3, 2, 1] [] []
[9, 8, 7, 6, 5, 4, 3, 2] [] [1]
[9, 8, 7, 6, 5, 4, 3] [2] [1]
[9, 8, 7, 6, 5, 4, 3] [2, 1] []
[9, 8, 7, 6, 5, 4] [2, 1] [3]
[9, 8, 7, 6, 5, 4, 1] [2] [3]
[9, 8, 7, 6, 5, 4, 1] [] [3, 2]
[9, 8, 7, 6, 5, 4] [] [3, 2, 1]
[9, 8, 7, 6, 5] [4] [3, 2, 1]
[9, 8, 7, 6, 5] [4, 1] [3, 2]
[9, 8, 7, 6, 5, 2] [4, 1] [3]
[9, 8, 7, 6, 5, 2, 1] [4] [3]
[9, 8, 7, 6, 5, 2, 1] [4, 3] []
[9, 8, 7, 6, 5, 2] [4, 3] [1]
[9, 8, 7, 6, 5] [4, 3, 2] [1]
[9, 8, 7, 6, 5] [4, 3, 2, 1] []
[9, 8, 7, 6] [4, 3, 2, 1] [5]
[9, 8, 7, 6, 1] [4, 3, 2] [5]
[9, 8, 7, 6, 1] [4, 3] [5, 2]
[9, 8, 7, 6] [4, 3] [5, 2, 1]
[9, 8, 7, 6, 3] [4] [5, 2, 1]
[9, 8, 7, 6, 3] [4, 1] [5, 2]
[9, 8, 7, 6, 3, 2] [4, 1] [5]
[9, 8, 7, 6, 3, 2, 1] [4] [5]
[9, 8, 7, 6, 3, 2, 1] [] [5, 4]
[9, 8, 7, 6, 3, 2] [] [5, 4, 1]
[9, 8, 7, 6, 3] [2] [5, 4, 1]
[9, 8, 7, 6, 3] [2, 1] [5, 4]
[9, 8, 7, 6] [2, 1] [5, 4, 3]
[9, 8, 7, 6, 1] [2] [5, 4, 3]
[9, 8, 7, 6, 1] [] [5, 4, 3, 2]
[9, 8, 7, 6] [] [5, 4, 3, 2, 1]
[9, 8, 7] [6] [5, 4, 3, 2, 1]
[9, 8, 7] [6, 1] [5, 4, 3, 2]
[9, 8, 7, 2] [6, 1] [5, 4, 3]
[9, 8, 7, 2, 1] [6] [5, 4, 3]
[9, 8, 7, 2, 1] [6, 3] [5, 4]
[9, 8, 7, 2] [6, 3] [5, 4, 1]
[9, 8, 7] [6, 3, 2] [5, 4, 1]
[9, 8, 7] [6, 3, 2, 1] [5, 4]
[9, 8, 7, 4] [6, 3, 2, 1] [5]
[9, 8, 7, 4, 1] [6, 3, 2] [5]
[9, 8, 7, 4, 1] [6, 3] [5, 2]
[9, 8, 7, 4] [6, 3] [5, 2, 1]
[9, 8, 7, 4, 3] [6] [5, 2, 1]
[9, 8, 7, 4, 3] [6, 1] [5, 2]
[9, 8, 7, 4, 3, 2] [6, 1] [5]
[9, 8, 7, 4, 3, 2, 1] [6] [5]
[9, 8, 7, 4, 3, 2, 1] [6, 5] []
[9, 8, 7, 4, 3, 2] [6, 5] [1]
[9, 8, 7, 4, 3] [6, 5, 2] [1]
[9, 8, 7, 4, 3] [6, 5, 2, 1] []
[9, 8, 7, 4] [6, 5, 2, 1] [3]
[9, 8, 7, 4, 1] [6, 5, 2] [3]
[9, 8, 7, 4, 1] [6, 5] [3, 2]
[9, 8, 7, 4] [6, 5] [3, 2, 1]
[9, 8, 7] [6, 5, 4] [3, 2, 1]
[9, 8, 7] [6, 5, 4, 1] [3, 2]
[9, 8, 7, 2] [6, 5, 4, 1] [3]
[9, 8, 7, 2, 1] [6, 5, 4] [3]
[9, 8, 7, 2, 1] [6, 5, 4, 3] []
[9, 8, 7, 2] [6, 5, 4, 3] [1]
[9, 8, 7] [6, 5, 4, 3, 2] [1]
[9, 8, 7] [6, 5, 4, 3, 2, 1] []
[9, 8] [6, 5, 4, 3, 2, 1] [7]
[9, 8, 1] [6, 5, 4, 3, 2] [7]
[9, 8, 1] [6, 5, 4, 3] [7, 2]
[9, 8] [6, 5, 4, 3] [7, 2, 1]
[9, 8, 3] [6, 5, 4] [7, 2, 1]
[9, 8, 3] [6, 5, 4, 1] [7, 2]
[9, 8, 3, 2] [6, 5, 4, 1] [7]
[9, 8, 3, 2, 1] [6, 5, 4] [7]
[9, 8, 3, 2, 1] [6, 5] [7, 4]
[9, 8, 3, 2] [6, 5] [7, 4, 1]
[9, 8, 3] [6, 5, 2] [7, 4, 1]
[9, 8, 3] [6, 5, 2, 1] [7, 4]
[9, 8] [6, 5, 2, 1] [7, 4, 3]
[9, 8, 1] [6, 5, 2] [7, 4, 3]
[9, 8, 1] [6, 5] [7, 4, 3, 2]
[9, 8] [6, 5] [7, 4, 3, 2, 1]
[9, 8, 5] [6] [7, 4, 3, 2, 1]
[9, 8, 5] [6, 1] [7, 4, 3, 2]
[9, 8, 5, 2] [6, 1] [7, 4, 3]
[9, 8, 5, 2, 1] [6] [7, 4, 3]
[9, 8, 5, 2, 1] [6, 3] [7, 4]
[9, 8, 5, 2] [6, 3] [7, 4, 1]
[9, 8, 5] [6, 3, 2] [7, 4, 1]
[9, 8, 5] [6, 3, 2, 1] [7, 4]
[9, 8, 5, 4] [6, 3, 2, 1] [7]
[9, 8, 5, 4, 1] [6, 3, 2] [7]
[9, 8, 5, 4, 1] [6, 3] [7, 2]
[9, 8, 5, 4] [6, 3] [7, 2, 1]
[9, 8, 5, 4, 3] [6] [7, 2, 1]
[9, 8, 5, 4, 3] [6, 1] [7, 2]
[9, 8, 5, 4, 3, 2] [6, 1] [7]
[9, 8, 5, 4, 3, 2, 1] [6] [7]
[9, 8, 5, 4, 3, 2, 1] [] [7, 6]
[9, 8, 5, 4, 3, 2] [] [7, 6, 1]
[9, 8, 5, 4, 3] [2] [7, 6, 1]
[9, 8, 5, 4, 3] [2, 1] [7, 6]
[9, 8, 5, 4] [2, 1] [7, 6, 3]
[9, 8, 5, 4, 1] [2] [7, 6, 3]
[9, 8, 5, 4, 1] [] [7, 6, 3, 2]
[9, 8, 5, 4] [] [7, 6, 3, 2, 1]
[9, 8, 5] [4] [7, 6, 3, 2, 1]
[9, 8, 5] [4, 1] [7, 6, 3, 2]
[9, 8, 5, 2] [4, 1] [7, 6, 3]
[9, 8, 5, 2, 1] [4] [7, 6, 3]
[9, 8, 5, 2, 1] [4, 3] [7, 6]
[9, 8, 5, 2] [4, 3] [7, 6, 1]
[9, 8, 5] [4, 3, 2] [7, 6, 1]
[9, 8, 5] [4, 3, 2, 1] [7, 6]
[9, 8] [4, 3, 2, 1] [7, 6, 5]
[9, 8, 1] [4, 3, 2] [7, 6, 5]
[9, 8, 1] [4, 3] [7, 6, 5, 2]
[9, 8] [4, 3] [7, 6, 5, 2, 1]
[9, 8, 3] [4] [7, 6, 5, 2, 1]
[9, 8, 3] [4, 1] [7, 6, 5, 2]
[9, 8, 3, 2] [4, 1] [7, 6, 5]
[9, 8, 3, 2, 1] [4] [7, 6, 5]
[9, 8, 3, 2, 1] [] [7, 6, 5, 4]
[9, 8, 3, 2] [] [7, 6, 5, 4, 1]
[9, 8, 3] [2] [7, 6, 5, 4, 1]
[9, 8, 3] [2, 1] [7, 6, 5, 4]
[9, 8] [2, 1] [7, 6, 5, 4, 3]
[9, 8, 1] [2] [7, 6, 5, 4, 3]
[9, 8, 1] [] [7, 6, 5, 4, 3, 2]
[9, 8] [] [7, 6, 5, 4, 3, 2, 1]
[9] [8] [7, 6, 5, 4, 3, 2, 1]
[9] [8, 1] [7, 6, 5, 4, 3, 2]
[9, 2] [8, 1] [7, 6, 5, 4, 3]
[9, 2, 1] [8] [7, 6, 5, 4, 3]
[9, 2, 1] [8, 3] [7, 6, 5, 4]
[9, 2] [8, 3] [7, 6, 5, 4, 1]
[9] [8, 3, 2] [7, 6, 5, 4, 1]
[9] [8, 3, 2, 1] [7, 6, 5, 4]
[9, 4] [8, 3, 2, 1] [7, 6, 5]
[9, 4, 1] [8, 3, 2] [7, 6, 5]
[9, 4, 1] [8, 3] [7, 6, 5, 2]
[9, 4] [8, 3] [7, 6, 5, 2, 1]
[9, 4, 3] [8] [7, 6, 5, 2, 1]
[9, 4, 3] [8, 1] [7, 6, 5, 2]
[9, 4, 3, 2] [8, 1] [7, 6, 5]
[9, 4, 3, 2, 1] [8] [7, 6, 5]
[9, 4, 3, 2, 1] [8, 5] [7, 6]
[9, 4, 3, 2] [8, 5] [7, 6, 1]
[9, 4, 3] [8, 5, 2] [7, 6, 1]
[9, 4, 3] [8, 5, 2, 1] [7, 6]
[9, 4] [8, 5, 2, 1] [7, 6, 3]
[9, 4, 1] [8, 5, 2] [7, 6, 3]
[9, 4, 1] [8, 5] [7, 6, 3, 2]
[9, 4] [8, 5] [7, 6, 3, 2, 1]
[9] [8, 5, 4] [7, 6, 3, 2, 1]
[9] [8, 5, 4, 1] [7, 6, 3, 2]
[9, 2] [8, 5, 4, 1] [7, 6, 3]
[9, 2, 1] [8, 5, 4] [7, 6, 3]
[9, 2, 1] [8, 5, 4, 3] [7, 6]
[9, 2] [8, 5, 4, 3] [7, 6, 1]
[9] [8, 5, 4, 3, 2] [7, 6, 1]
[9] [8, 5, 4, 3, 2, 1] [7, 6]
[9, 6] [8, 5, 4, 3, 2, 1] [7]
[9, 6, 1] [8, 5, 4, 3, 2] [7]
[9, 6, 1] [8, 5, 4, 3] [7, 2]
[9, 6] [8, 5, 4, 3] [7, 2, 1]
[9, 6, 3] [8, 5, 4] [7, 2, 1]
[9, 6, 3] [8, 5, 4, 1] [7, 2]
[9, 6, 3, 2] [8, 5, 4, 1] [7]
[9, 6, 3, 2, 1] [8, 5, 4] [7]
[9, 6, 3, 2, 1] [8, 5] [7, 4]
[9, 6, 3, 2] [8, 5] [7, 4, 1]
[9, 6, 3] [8, 5, 2] [7, 4, 1]
[9, 6, 3] [8, 5, 2, 1] [7, 4]
[9, 6] [8, 5, 2, 1] [7, 4, 3]
[9, 6, 1] [8, 5, 2] [7, 4, 3]
[9, 6, 1] [8, 5] [7, 4, 3, 2]
[9, 6] [8, 5] [7, 4, 3, 2, 1]
[9, 6, 5] [8] [7, 4, 3, 2, 1]
[9, 6, 5] [8, 1] [7, 4, 3, 2]
[9, 6, 5, 2] [8, 1] [7, 4, 3]
[9, 6, 5, 2, 1] [8] [7, 4, 3]
[9, 6, 5, 2, 1] [8, 3] [7, 4]
[9, 6, 5, 2] [8, 3] [7, 4, 1]
[9, 6, 5] [8, 3, 2] [7, 4, 1]
[9, 6, 5] [8, 3, 2, 1] [7, 4]
[9, 6, 5, 4] [8, 3, 2, 1] [7]
[9, 6, 5, 4, 1] [8, 3, 2] [7]
[9, 6, 5, 4, 1] [8, 3] [7, 2]
[9, 6, 5, 4] [8, 3] [7, 2, 1]
[9, 6, 5, 4, 3] [8] [7, 2, 1]
[9, 6, 5, 4, 3] [8, 1] [7, 2]
[9, 6, 5, 4, 3, 2] [8, 1] [7]
[9, 6, 5, 4, 3, 2, 1] [8] [7]
[9, 6, 5, 4, 3, 2, 1] [8, 7] []
[9, 6, 5, 4, 3, 2] [8, 7] [1]
[9, 6, 5, 4, 3] [8, 7, 2] [1]
[9, 6, 5, 4, 3] [8, 7, 2, 1] []
[9, 6, 5, 4] [8, 7, 2, 1] [3]
[9, 6, 5, 4, 1] [8, 7, 2] [3]
[9, 6, 5, 4, 1] [8, 7] [3, 2]
[9, 6, 5, 4] [8, 7] [3, 2, 1]
[9, 6, 5] [8, 7, 4] [3, 2, 1]
[9, 6, 5] [8, 7, 4, 1] [3, 2]
[9, 6, 5, 2] [8, 7, 4, 1] [3]
[9, 6, 5, 2, 1] [8, 7, 4] [3]
[9, 6, 5, 2, 1] [8, 7, 4, 3] []
[9, 6, 5, 2] [8, 7, 4, 3] [1]
[9, 6, 5] [8, 7, 4, 3, 2] [1]
[9, 6, 5] [8, 7, 4, 3, 2, 1] []
[9, 6] [8, 7, 4, 3, 2, 1] [5]
[9, 6, 1] [8, 7, 4, 3, 2] [5]
[9, 6, 1] [8, 7, 4, 3] [5, 2]
[9, 6] [8, 7, 4, 3] [5, 2, 1]
[9, 6, 3] [8, 7, 4] [5, 2, 1]
[9, 6, 3] [8, 7, 4, 1] [5, 2]
[9, 6, 3, 2] [8, 7, 4, 1] [5]
[9, 6, 3, 2, 1] [8, 7, 4] [5]
[9, 6, 3, 2, 1] [8, 7] [5, 4]
[9, 6, 3, 2] [8, 7] [5, 4, 1]
[9, 6, 3] [8, 7, 2] [5, 4, 1]
[9, 6, 3] [8, 7, 2, 1] [5, 4]
[9, 6] [8, 7, 2, 1] [5, 4, 3]
[9, 6, 1] [8, 7, 2] [5, 4, 3]
[9, 6, 1] [8, 7] [5, 4, 3, 2]
[9, 6] [8, 7] [5, 4, 3, 2, 1]
[9] [8, 7, 6] [5, 4, 3, 2, 1]
[9] [8, 7, 6, 1] [5, 4, 3, 2]
[9, 2] [8, 7, 6, 1] [5, 4, 3]
[9, 2, 1] [8, 7, 6] [5, 4, 3]
[9, 2, 1] [8, 7, 6, 3] [5, 4]
[9, 2] [8, 7, 6, 3] [5, 4, 1]
[9] [8, 7, 6, 3, 2] [5, 4, 1]
[9] [8, 7, 6, 3, 2, 1] [5, 4]
[9, 4] [8, 7, 6, 3, 2, 1] [5]
[9, 4, 1] [8, 7, 6, 3, 2] [5]
[9, 4, 1] [8, 7, 6, 3] [5, 2]
[9, 4] [8, 7, 6, 3] [5, 2, 1]
[9, 4, 3] [8, 7, 6] [5, 2, 1]
[9, 4, 3] [8, 7, 6, 1] [5, 2]
[9, 4, 3, 2] [8, 7, 6, 1] [5]
[9, 4, 3, 2, 1] [8, 7, 6] [5]
[9, 4, 3, 2, 1] [8, 7, 6, 5] []
[9, 4, 3, 2] [8, 7, 6, 5] [1]
[9, 4, 3] [8, 7, 6, 5, 2] [1]
[9, 4, 3] [8, 7, 6, 5, 2, 1] []
[9, 4] [8, 7, 6, 5, 2, 1] [3]
[9, 4, 1] [8, 7, 6, 5, 2] [3]
[9, 4, 1] [8, 7, 6, 5] [3, 2]
[9, 4] [8, 7, 6, 5] [3, 2, 1]
[9] [8, 7, 6, 5, 4] [3, 2, 1]
[9] [8, 7, 6, 5, 4, 1] [3, 2]
[9, 2] [8, 7, 6, 5, 4, 1] [3]
[9, 2, 1] [8, 7, 6, 5, 4] [3]
[9, 2, 1] [8, 7, 6, 5, 4, 3] []
[9, 2] [8, 7, 6, 5, 4, 3] [1]
[9] [8, 7, 6, 5, 4, 3, 2] [1]
[9] [8, 7, 6, 5, 4, 3, 2, 1] []
[] [8, 7, 6, 5, 4, 3, 2, 1] [9]
[1] [8, 7, 6, 5, 4, 3, 2] [9]
[1] [8, 7, 6, 5, 4, 3] [9, 2]
[] [8, 7, 6, 5, 4, 3] [9, 2, 1]
[3] [8, 7, 6, 5, 4] [9, 2, 1]
[3] [8, 7, 6, 5, 4, 1] [9, 2]
[3, 2] [8, 7, 6, 5, 4, 1] [9]
[3, 2, 1] [8, 7, 6, 5, 4] [9]
[3, 2, 1] [8, 7, 6, 5] [9, 4]
[3, 2] [8, 7, 6, 5] [9, 4, 1]
[3] [8, 7, 6, 5, 2] [9, 4, 1]
[3] [8, 7, 6, 5, 2, 1] [9, 4]
[] [8, 7, 6, 5, 2, 1] [9, 4, 3]
[1] [8, 7, 6, 5, 2] [9, 4, 3]
[1] [8, 7, 6, 5] [9, 4, 3, 2]
[] [8, 7, 6, 5] [9, 4, 3, 2, 1]
[5] [8, 7, 6] [9, 4, 3, 2, 1]
[5] [8, 7, 6, 1] [9, 4, 3, 2]
[5, 2] [8, 7, 6, 1] [9, 4, 3]
[5, 2, 1] [8, 7, 6] [9, 4, 3]
[5, 2, 1] [8, 7, 6, 3] [9, 4]
[5, 2] [8, 7, 6, 3] [9, 4, 1]
[5] [8, 7, 6, 3, 2] [9, 4, 1]
[5] [8, 7, 6, 3, 2, 1] [9, 4]
[5, 4] [8, 7, 6, 3, 2, 1] [9]
[5, 4, 1] [8, 7, 6, 3, 2] [9]
[5, 4, 1] [8, 7, 6, 3] [9, 2]
[5, 4] [8, 7, 6, 3] [9, 2, 1]
[5, 4, 3] [8, 7, 6] [9, 2, 1]
[5, 4, 3] [8, 7, 6, 1] [9, 2]
[5, 4, 3, 2] [8, 7, 6, 1] [9]
[5, 4, 3, 2, 1] [8, 7, 6] [9]
[5, 4, 3, 2, 1] [8, 7] [9, 6]
[5, 4, 3, 2] [8, 7] [9, 6, 1]
[5, 4, 3] [8, 7, 2] [9, 6, 1]
[5, 4, 3] [8, 7, 2, 1] [9, 6]
[5, 4] [8, 7, 2, 1] [9, 6, 3]
[5, 4, 1] [8, 7, 2] [9, 6, 3]
[5, 4, 1] [8, 7] [9, 6, 3, 2]
[5, 4] [8, 7] [9, 6, 3, 2, 1]
[5] [8, 7, 4] [9, 6, 3, 2, 1]
[5] [8, 7, 4, 1] [9, 6, 3, 2]
[5, 2] [8, 7, 4, 1] [9, 6, 3]
[5, 2, 1] [8, 7, 4] [9, 6, 3]
[5, 2, 1] [8, 7, 4, 3] [9, 6]
[5, 2] [8, 7, 4, 3] [9, 6, 1]
[5] [8, 7, 4, 3, 2] [9, 6, 1]
[5] [8, 7, 4, 3, 2, 1] [9, 6]
[] [8, 7, 4, 3, 2, 1] [9, 6, 5]
[1] [8, 7, 4, 3, 2] [9, 6, 5]
[1] [8, 7, 4, 3] [9, 6, 5, 2]
[] [8, 7, 4, 3] [9, 6, 5, 2, 1]
[3] [8, 7, 4] [9, 6, 5, 2, 1]
[3] [8, 7, 4, 1] [9, 6, 5, 2]
[3, 2] [8, 7, 4, 1] [9, 6, 5]
[3, 2, 1] [8, 7, 4] [9, 6, 5]
[3, 2, 1] [8, 7] [9, 6, 5, 4]
[3, 2] [8, 7] [9, 6, 5, 4, 1]
[3] [8, 7, 2] [9, 6, 5, 4, 1]
[3] [8, 7, 2, 1] [9, 6, 5, 4]
[] [8, 7, 2, 1] [9, 6, 5, 4, 3]
[1] [8, 7, 2] [9, 6, 5, 4, 3]
[1] [8, 7] [9, 6, 5, 4, 3, 2]
[] [8, 7] [9, 6, 5, 4, 3, 2, 1]
[7] [8] [9, 6, 5, 4, 3, 2, 1]
[7] [8, 1] [9, 6, 5, 4, 3, 2]
[7, 2] [8, 1] [9, 6, 5, 4, 3]
[7, 2, 1] [8] [9, 6, 5, 4, 3]
[7, 2, 1] [8, 3] [9, 6, 5, 4]
[7, 2] [8, 3] [9, 6, 5, 4, 1]
[7] [8, 3, 2] [9, 6, 5, 4, 1]
[7] [8, 3, 2, 1] [9, 6, 5, 4]
[7, 4] [8, 3, 2, 1] [9, 6, 5]
[7, 4, 1] [8, 3, 2] [9, 6, 5]
[7, 4, 1] [8, 3] [9, 6, 5, 2]
[7, 4] [8, 3] [9, 6, 5, 2, 1]
[7, 4, 3] [8] [9, 6, 5, 2, 1]
[7, 4, 3] [8, 1] [9, 6, 5, 2]
[7, 4, 3, 2] [8, 1] [9, 6, 5]
[7, 4, 3, 2, 1] [8] [9, 6, 5]
[7, 4, 3, 2, 1] [8, 5] [9, 6]
[7, 4, 3, 2] [8, 5] [9, 6, 1]
[7, 4, 3] [8, 5, 2] [9, 6, 1]
[7, 4, 3] [8, 5, 2, 1] [9, 6]
[7, 4] [8, 5, 2, 1] [9, 6, 3]
[7, 4, 1] [8, 5, 2] [9, 6, 3]
[7, 4, 1] [8, 5] [9, 6, 3, 2]
[7, 4] [8, 5] [9, 6, 3, 2, 1]
[7] [8, 5, 4] [9, 6, 3, 2, 1]
[7] [8, 5, 4, 1] [9, 6, 3, 2]
[7, 2] [8, 5, 4, 1] [9, 6, 3]
[7, 2, 1] [8, 5, 4] [9, 6, 3]
[7, 2, 1] [8, 5, 4, 3] [9, 6]
[7, 2] [8, 5, 4, 3] [9, 6, 1]
[7] [8, 5, 4, 3, 2] [9, 6, 1]
[7] [8, 5, 4, 3, 2, 1] [9, 6]
[7, 6] [8, 5, 4, 3, 2, 1] [9]
[7, 6, 1] [8, 5, 4, 3, 2] [9]
[7, 6, 1] [8, 5, 4, 3] [9, 2]
[7, 6] [8, 5, 4, 3] [9, 2, 1]
[7, 6, 3] [8, 5, 4] [9, 2, 1]
[7, 6, 3] [8, 5, 4, 1] [9, 2]
[7, 6, 3, 2] [8, 5, 4, 1] [9]
[7, 6, 3, 2, 1] [8, 5, 4] [9]
[7, 6, 3, 2, 1] [8, 5] [9, 4]
[7, 6, 3, 2] [8, 5] [9, 4, 1]
[7, 6, 3] [8, 5, 2] [9, 4, 1]
[7, 6, 3] [8, 5, 2, 1] [9, 4]
[7, 6] [8, 5, 2, 1] [9, 4, 3]
[7, 6, 1] [8, 5, 2] [9, 4, 3]
[7, 6, 1] [8, 5] [9, 4, 3, 2]
[7, 6] [8, 5] [9, 4, 3, 2, 1]
[7, 6, 5] [8] [9, 4, 3, 2, 1]
[7, 6, 5] [8, 1] [9, 4, 3, 2]
[7, 6, 5, 2] [8, 1] [9, 4, 3]
[7, 6, 5, 2, 1] [8] [9, 4, 3]
[7, 6, 5, 2, 1] [8, 3] [9, 4]
[7, 6, 5, 2] [8, 3] [9, 4, 1]
[7, 6, 5] [8, 3, 2] [9, 4, 1]
[7, 6, 5] [8, 3, 2, 1] [9, 4]
[7, 6, 5, 4] [8, 3, 2, 1] [9]
[7, 6, 5, 4, 1] [8, 3, 2] [9]
[7, 6, 5, 4, 1] [8, 3] [9, 2]
[7, 6, 5, 4] [8, 3] [9, 2, 1]
[7, 6, 5, 4, 3] [8] [9, 2, 1]
[7, 6, 5, 4, 3] [8, 1] [9, 2]
[7, 6, 5, 4, 3, 2] [8, 1] [9]
[7, 6, 5, 4, 3, 2, 1] [8] [9]
[7, 6, 5, 4, 3, 2, 1] [] [9, 8]
[7, 6, 5, 4, 3, 2] [] [9, 8, 1]
[7, 6, 5, 4, 3] [2] [9, 8, 1]
[7, 6, 5, 4, 3] [2, 1] [9, 8]
[7, 6, 5, 4] [2, 1] [9, 8, 3]
[7, 6, 5, 4, 1] [2] [9, 8, 3]
[7, 6, 5, 4, 1] [] [9, 8, 3, 2]
[7, 6, 5, 4] [] [9, 8, 3, 2, 1]
[7, 6, 5] [4] [9, 8, 3, 2, 1]
[7, 6, 5] [4, 1] [9, 8, 3, 2]
[7, 6, 5, 2] [4, 1] [9, 8, 3]
[7, 6, 5, 2, 1] [4] [9, 8, 3]
[7, 6, 5, 2, 1] [4, 3] [9, 8]
[7, 6, 5, 2] [4, 3] [9, 8, 1]
[7, 6, 5] [4, 3, 2] [9, 8, 1]
[7, 6, 5] [4, 3, 2, 1] [9, 8]
[7, 6] [4, 3, 2, 1] [9, 8, 5]
[7, 6, 1] [4, 3, 2] [9, 8, 5]
[7, 6, 1] [4, 3] [9, 8, 5, 2]
[7, 6] [4, 3] [9, 8, 5, 2, 1]
[7, 6, 3] [4] [9, 8, 5, 2, 1]
[7, 6, 3] [4, 1] [9, 8, 5, 2]
[7, 6, 3, 2] [4, 1] [9, 8, 5]
[7, 6, 3, 2, 1] [4] [9, 8, 5]
[7, 6, 3, 2, 1] [] [9, 8, 5, 4]
[7, 6, 3, 2] [] [9, 8, 5, 4, 1]
[7, 6, 3] [2] [9, 8, 5, 4, 1]
[7, 6, 3] [2, 1] [9, 8, 5, 4]
[7, 6] [2, 1] [9, 8, 5, 4, 3]
[7, 6, 1] [2] [9, 8, 5, 4, 3]
[7, 6, 1] [] [9, 8, 5, 4, 3, 2]
[7, 6] [] [9, 8, 5, 4, 3, 2, 1]
[7] [6] [9, 8, 5, 4, 3, 2, 1]
[7] [6, 1] [9, 8, 5, 4, 3, 2]
[7, 2] [6, 1] [9, 8, 5, 4, 3]
[7, 2, 1] [6] [9, 8, 5, 4, 3]
[7, 2, 1] [6, 3] [9, 8, 5, 4]
[7, 2] [6, 3] [9, 8, 5, 4, 1]
[7] [6, 3, 2] [9, 8, 5, 4, 1]
[7] [6, 3, 2, 1] [9, 8, 5, 4]
[7, 4] [6, 3, 2, 1] [9, 8, 5]
[7, 4, 1] [6, 3, 2] [9, 8, 5]
[7, 4, 1] [6, 3] [9, 8, 5, 2]
[7, 4] [6, 3] [9, 8, 5, 2, 1]
[7, 4, 3] [6] [9, 8, 5, 2, 1]
[7, 4, 3] [6, 1] [9, 8, 5, 2]
[7, 4, 3, 2] [6, 1] [9, 8, 5]
[7, 4, 3, 2, 1] [6] [9, 8, 5]
[7, 4, 3, 2, 1] [6, 5] [9, 8]
[7, 4, 3, 2] [6, 5] [9, 8, 1]
[7, 4, 3] [6, 5, 2] [9, 8, 1]
[7, 4, 3] [6, 5, 2, 1] [9, 8]
[7, 4] [6, 5, 2, 1] [9, 8, 3]
[7, 4, 1] [6, 5, 2] [9, 8, 3]
[7, 4, 1] [6, 5] [9, 8, 3, 2]
[7, 4] [6, 5] [9, 8, 3, 2, 1]
[7] [6, 5, 4] [9, 8, 3, 2, 1]
[7] [6, 5, 4, 1] [9, 8, 3, 2]
[7, 2] [6, 5, 4, 1] [9, 8, 3]
[7, 2, 1] [6, 5, 4] [9, 8, 3]
[7, 2, 1] [6, 5, 4, 3] [9, 8]
[7, 2] [6, 5, 4, 3] [9, 8, 1]
[7] [6, 5, 4, 3, 2] [9, 8, 1]
[7] [6, 5, 4, 3, 2, 1] [9, 8]
[] [6, 5, 4, 3, 2, 1] [9, 8, 7]
[1] [6, 5, 4, 3, 2] [9, 8, 7]
[1] [6, 5, 4, 3] [9, 8, 7, 2]
[] [6, 5, 4, 3] [9, 8, 7, 2, 1]
[3] [6, 5, 4] [9, 8, 7, 2, 1]
[3] [6, 5, 4, 1] [9, 8, 7, 2]
[3, 2] [6, 5, 4, 1] [9, 8, 7]
[3, 2, 1] [6, 5, 4] [9, 8, 7]
[3, 2, 1] [6, 5] [9, 8, 7, 4]
[3, 2] [6, 5] [9, 8, 7, 4, 1]
[3] [6, 5, 2] [9, 8, 7, 4, 1]
[3] [6, 5, 2, 1] [9, 8, 7, 4]
[] [6, 5, 2, 1] [9, 8, 7, 4, 3]
[1] [6, 5, 2] [9, 8, 7, 4, 3]
[1] [6, 5] [9, 8, 7, 4, 3, 2]
[] [6, 5] [9, 8, 7, 4, 3, 2, 1]
[5] [6] [9, 8, 7, 4, 3, 2, 1]
[5] [6, 1] [9, 8, 7, 4, 3, 2]
[5, 2] [6, 1] [9, 8, 7, 4, 3]
[5, 2, 1] [6] [9, 8, 7, 4, 3]
[5, 2, 1] [6, 3] [9, 8, 7, 4]
[5, 2] [6, 3] [9, 8, 7, 4, 1]
[5] [6, 3, 2] [9, 8, 7, 4, 1]
[5] [6, 3, 2, 1] [9, 8, 7, 4]
[5, 4] [6, 3, 2, 1] [9, 8, 7]
[5, 4, 1] [6, 3, 2] [9, 8, 7]
[5, 4, 1] [6, 3] [9, 8, 7, 2]
[5, 4] [6, 3] [9, 8, 7, 2, 1]
[5, 4, 3] [6] [9, 8, 7, 2, 1]
[5, 4, 3] [6, 1] [9, 8, 7, 2]
[5, 4, 3, 2] [6, 1] [9, 8, 7]
[5, 4, 3, 2, 1] [6] [9, 8, 7]
[5, 4, 3, 2, 1] [] [9, 8, 7, 6]
[5, 4, 3, 2] [] [9, 8, 7, 6, 1]
[5, 4, 3] [2] [9, 8, 7, 6, 1]
[5, 4, 3] [2, 1] [9, 8, 7, 6]
[5, 4] [2, 1] [9, 8, 7, 6, 3]
[5, 4, 1] [2] [9, 8, 7, 6, 3]
[5, 4, 1] [] [9, 8, 7, 6, 3, 2]
[5, 4] [] [9, 8, 7, 6, 3, 2, 1]
[5] [4] [9, 8, 7, 6, 3, 2, 1]
[5] [4, 1] [9, 8, 7, 6, 3, 2]
[5, 2] [4, 1] [9, 8, 7, 6, 3]
[5, 2, 1] [4] [9, 8, 7, 6, 3]
[5, 2, 1] [4, 3] [9, 8, 7, 6]
[5, 2] [4, 3] [9, 8, 7, 6, 1]
[5] [4, 3, 2] [9, 8, 7, 6, 1]
[5] [4, 3, 2, 1] [9, 8, 7, 6]
[] [4, 3, 2, 1] [9, 8, 7, 6, 5]
[1] [4, 3, 2] [9, 8, 7, 6, 5]
[1] [4, 3] [9, 8, 7, 6, 5, 2]
[] [4, 3] [9, 8, 7, 6, 5, 2, 1]
[3] [4] [9, 8, 7, 6, 5, 2, 1]
[3] [4, 1] [9, 8, 7, 6, 5, 2]
[3, 2] [4, 1] [9, 8, 7, 6, 5]
[3, 2, 1] [4] [9, 8, 7, 6, 5]
[3, 2, 1] [] [9, 8, 7, 6, 5, 4]
[3, 2] [] [9, 8, 7, 6, 5, 4, 1]
[3] [2] [9, 8, 7, 6, 5, 4, 1]
[3] [2, 1] [9, 8, 7, 6, 5, 4]
[] [2, 1] [9, 8, 7, 6, 5, 4, 3]
[1] [2] [9, 8, 7, 6, 5, 4, 3]
[1] [] [9, 8, 7, 6, 5, 4, 3, 2]
[] [] [9, 8, 7, 6, 5, 4, 3, 2, 1]"""
assert hanoi_solver(9) == expected
`) })
def hanoi_solver(n):
# Initialize the three rods
A = list(range(n, 0, -1))
B = []
C = []
# List to store all moves as strings
moves = [f"{A} {B} {C}"]
def move(num_disks, source, auxiliary, target):
if num_disks <= 0:
return
# Move n-1 disks from source to auxiliary, so they are out of the way
move(num_disks - 1, source, target, auxiliary)
# Move the nth disk from source to target
target.append(source.pop())
# Record the move
moves.append(f"{A} {B} {C}")
# Move the n-1 disks that we left on auxiliary onto target
move(num_disks - 1, auxiliary, source, target)
# Start the recursive process
move(n, A, B, C)
return '\n'.join(moves)