Solving Tower of Hanoi with General Problem Solver
A walkthrough of solving Tower of Hanoi using the approach of one of the earliest AI systems.
This post is part of the series A Primer on Artificial Intelligence.
Want to get notified about new posts? Join the mailing list.
Tower of Hanoi is a puzzle. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following three rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
- No larger disk may be placed on top of a smaller disk.
The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. He was inspired by a legend that tells of a Hindu temple where the puzzle was presented to young priests. At the beginning of time, the priests were given three poles and a stack of 64 gold disks, each disk a little smaller than the one beneath it. Their assignment was to transfer all 64 disks from one of the three poles to another, subject to the rules above. The priests worked very efficiently, day and night, moving one disk every second. When they finished their work, the legend said, the temple would crumble into dust and the world would vanish.
Although the legend is interesting, you need not worry about the world ending any time soon. The number of moves required to correctly move a tower of 64 disks is 18,446,744,073,709,551,615. At a rate of one move per second, that is 584,942,417,355 years! Clearly there is more to this puzzle than meets the eye.
Below is a walkthrough of solving Tower of Hanoi using the approach of one of the earliest AI systems, General Problem Solver.
General Problem Solver
The main idea of General Problem Solver is that finding the solution to a problem often amounts to finding the correct sequence of actions to achieve some result.
In Towers of Hanoi, each action involves taking a disk off some tower and placing it on another tower. There is some sequence of these actions that will transfer all the disks on the leftmost tower to the rightmost tower.
If we can find a clever way to search through all the possible action sequences, then we can check each result and stop once we’ve found the action sequence that gives us the desired result.
Tower Configurations as Lists
Before we get too far into the trenches, we need to figure out how to represent tower configurations in a way that we can operate on via code. Let’s work this out for the case of 3 towers.
One option is to use a list where each entry represents a tower:
config = [tower_1, tower_2, tower_3]
Each tower itself can be a list of disks, where the first entry is the top disk. Since tower_1 initially contains all the disks, we have
tower_1 = [small_disk, medium_disk, large_disk]
tower_2 = []
tower_3 = []
However, how should the computer know the differences in sizes of disks, based on their names? The word “small” means something to us, but not to the computer.
Instead of labeling disk size by the adjectives “small”, “medium”, and “large”, let’s label disk size by numbers. The smallest disk will be indicated by 1, the medium tower by 2, and the large disk by 3. Then we have:
tower_1 = [1,2,3]
tower_2 = []
tower_3 = []
We can even forget about the tower names altogether, and put the tower lists as entries of the configuration list itself. Then we have a nice setup in which the configuration is condensed to a single line:
config = [[1,2,3], [], []]
Exercise 1
What would the initial configuration be for the case of 4 towers?
config = [[1,2,3],[],[]] # change this to the configuration in the case of 4 towers
# NOTE: The code below checks your answer while in a way that prevents you from easily
# identifying the correct answer.
if ''.join([''.join([str(n*3+7) for n in x]+['5']) for x in config])=='101316195555':
print('Correct!')
else:
print('Incorrect; try again.')
Exercise 2
Starting with the initial configuration for 3 towers (which is [[1,2,3], [], []]), move the smallest disk off of the first tower and put it on the second tower. What is the resulting configuration?
config = [[1,2,3],[],[]] # change this to the configuration that results from moving the smallest disk
# off the first tower and putting it on the third tower
if ''.join([''.join([str(n*3+7) for n in x]+['5']) for x in config])=='131651055':
print('Correct!')
else:
print('Incorrect; try again.')
Actions as Functions
Now that we have a way to represent tower/disk configurations, we need to come up with a way to operate on those configurations. We know how to do the operations by hand, but we will need to come up with a way to have the computer do the operations on its own.
Hence, we will create a function that tells the computer to move the top disk off of one tower and put it on another tower.
Exercise 3
Complete the function below, which moves the top disk off of one tower and puts it on another tower.
def move(i, j, config):
new_config = config.copy() # creates a copy of config that we will modify and output
###
#
# your code here - remove top disk from tower i and put it on tower j
#
###
return new_config
Some test cases are provided below to help you check your function. You can run all the tests by executing the code below.
move(1, 3, [[1,2,3],[], []])should output[[2,3], [], [1]]move(3, 2, [[3], [2], [1]])should output[[3], [1,2], []]
if move(1,3,[[1,2,3], [], []]) == [[2,3], [], [1]]:
print('Test 1 - SUCCEEDED')
else:
print('Test 1 - FAILED')
if move(3, 2, [[3], [2], [1]]) == [[3], [1,2], []]:
print('Test 2 - SUCCEEDED')
else:
print('Test 2 - FAILED')
Enumerating Actions
We will be repeatedly applying our move function to check all possible moves, until we find a result where all the disks are stacked on the last tower.
As such, we first need to create a function that lists all the possible configurations that could result from a move on some initial configuration.
Exercise 4
Complete the function below, which lists all the possible configurations that could result from a move on some initial configuration.
- Make sure there are no duplicates in the output list.
- Make sure the moves follow the rules of the game: only one disk may be moved off the top of one tower and placed onto another tower whose top disk is larger.
def possibilities(config):
output_list = []
###
#
# your code here
#
###
return output_list
Some test cases are provided below to help you check your function. You can run all the tests by executing the code below.
possibilities([[1,2,3], [], []])should output[[[2, 3], [1], []], [[2, 3], [], [1]]](in any order)possibilities([[3], [1], [2]])should output[[[1, 3], [], [2]], [[3], [], [1, 2]], [[2, 3], [1], []]](in any order)
import collections
def counts(inList):
return collections.Counter([str(x) for x in inList])
result1 = possibilities([[1,2,3], [], []])
desired1 = [[[2, 3], [1], []], [[2, 3], [], [1]]]
if counts(result1) == counts(desired1):
print('Test 1 - SUCCEEDED')
else:
print('Test 1 - FAILED')
result2 = possibilities([[3],[1],[2]])
desired2 = [[[1, 3], [], [2]], [[3], [], [1, 2]], [[2, 3], [1], []]]
if counts(result2) == counts(desired2):
print('Test 2 - SUCCEEDED')
else:
print('Test 2 - FAILED')
Action Sequences
With our possibilities() function, we will surely be able to keep generating possibilities until we solve the puzzle.
However, once we solve the puzzle, how will we know what sequence of moves we took to get there? We need to keep track of the moves as we generate possibilities.
To do this, let’s keep track of configurations and action sequences together in dictionaries.
For example, the initial configuration would have an empty move sequence, so we would represent it as
{'config': [[1,2,3], [], []], 'moves': []}
Say we moved the top disk from the first tower to the third tower. Then we would have the following:
{'config': [[2,3], [], [1]], 'moves': [(1,3)]}
If we continued and moved the next top disk on the first tower to the second tower, we would have
{'config': [[3], [2], [1]], 'moves': [(1,3),(1,2)]}
And if we put the disk from the third tower onto the second tower, we would have
{'config': [[3], [1,2], []], 'moves': [(1,3),(1,2),(3,2)]}
Exercise 5
Modify the possibilities() function so that it keeps track of configurations and moves together in dictionaries.
def possibilities(configMoves):
output_list = []
###
#
# your code here
#
###
return output_list
Some test cases are provided below to help you check your function. You can run all the tests by executing the code below.
possibilities({'config': [[1,2,3], [], []], 'moves': []})should output
(in any order).[{'config': [[2, 3], [1], []], 'moves': [(1,2)]}, {'config': [[2, 3], [], [1]], 'moves': [(1,3)]}]possibilities({'config': [[3], [1], [2]], 'moves':[(1,2),(1,3)]})should output
(in any order).[{'config': [[1, 3], [], [2]], 'moves': [(1,2),(1,3),(2,1)]}, {'config': [[3], [], [1, 2]], 'moves': [(1,2),(1,3),(2,3)]}, {'config': [[2, 3], [1], []], 'moves': [(1,2),(1,3),(3,1)]}]
import collections
def counts(dlist):
stringList = [str(d['config'])+str(d['moves']) for d in dlist]
return collections.Counter([str(x) for x in stringList])
result1 = possibilities({'config': [[1,2,3], [], []], 'moves': []})
desired1 = [
{'config': [[2, 3], [1], []], 'moves': [(1, 2)]},
{'config': [[2, 3], [], [1]], 'moves': [(1, 3)]}
]
if counts(result1) == counts(desired1):
print('Test 1 - SUCCEEDED')
else:
print('Test 1 - FAILED')
result2 = possibilities({'config': [[3], [1], [2]], 'moves':[(1,2),(1,3)]})
desired2 = [
{'config': [[1, 3], [], [2]], 'moves': [(1, 2), (1, 3), (2, 1)]},
{'config': [[3], [], [1, 2]], 'moves': [(1, 2), (1, 3), (2, 3)]},
{'config': [[2, 3], [1], []], 'moves': [(1, 2), (1, 3), (3, 1)]}
]
if counts(result2) == counts(desired2)
print('Test 2 - SUCCEEDED')
else:
print('Test 2 - FAILED')
Searching for the Solution
Now that we have a function in place to generate all possibilities of moves and keep track of the sequences of moves as we go, we can search for the solution.
We can do this with a while loop – we will start with a list of configurations containing just the initial state, and while this list does not contain the final configuration, we will generate all possibilities arising from configurations in this list. We will add any new configurations to the list, and the process will be repeated until the final configuration appears in the list.
Exercise 6
Complete the while loop in the code below. In each loop, you should use the possibilities() function to find all the possible moves starting from any configuration in config_list, and update config_list with any new configurations. (You should update configMoves_list as well.)
def solution(N, iteration_limit=1000000):
initial_config = [list(range(1,N+1)),[],[]]
final_config = [[],[],list(range(1,N+1))]
configMoves_list = [{'config':initial_config, 'moves':[]}]
config_list = [initial_config]
counter = 0
while final_config not in config_list:
###
#
# your code here -- update config_list and configMoves_list
#
###
counter += 1
if counter > iteration_limit: # limit the while loop to a million executions
print('reached iteration limit')
break
move_sequence = []
for configMoves in configMoves_list:
if configMoves['config'] == final_config:
move_sequence = configMoves['moves']
return move_sequence
You can check your solution for several cases of N by running the code below.
def check(N):
config = [list(range(1,N+1)),[],[]]
for (i,j) in solution(N):
config = move(i,j,config)
if config == [[],[],list(range(1,N+1))]:
print('Case of N='+str(N)+' disks -- SUCCEEDED')
else:
print('Case of N='+str(N)+' disks -- FAILED')
for N in range(2,7):
check(N)
Exercises
Exercise 1
config = [[1,2,3,4],[],[],[]]
Exercise 2
config = [[2,3],[1],[]]
Exercise 3
def move(i, j, config):
new_config = config.copy() # creates a copy of config that we will modify and output
new_config[j-1] = [new_config[i-1][0]] + new_config[j-1] # put top disk on j
new_config[i-1] = new_config[i-1][1:] # remove top disk from i
return new_config
Exercise 4
def possibilities(config):
output_list = []
N = len(config)
for i in [1,2,3]:
if config[i-1] != []: # can't move any disks from an empty tower
for j in [1,2,3]:
if config[j-1] == []:
output_list += [move(i,j,config)]
elif config[j-1][0] > config[i-1][0]: # top disk on tower j must be smaller than disk from tower
output_list += [move(i,j,config)]
return output_list
Exercise 5
def possibilities(configMoves):
output_list = []
config = configMoves['config']
moves = configMoves['moves']
N = len(config)
for i in [1,2,3]:
if config[i-1] != []: # can't move any disks from an empty tower
for j in [1,2,3]:
if config[j-1] == []:
output_list += [{'config':move(i,j,config),'moves':moves+[(i,j)]}]
elif config[j-1][0] > config[i-1][0]: # top disk on tower j must be smaller than disk from tower
output_list += [{'config':move(i,j,config),'moves':moves+[(i,j)]}]
return output_list
Exercise 6
def solution(N, iteration_limit=1000):
initial_config = [list(range(1,N+1)),[],[]]
final_config = [[],[],list(range(1,N+1))]
configMoves_list = [{'config':initial_config, 'moves':[]}]
config_list = [initial_config]
counter = 0
while final_config not in config_list:
new_configMoves_list = []
new_config_list = []
for configMoves in configMoves_list:
for new_configMoves in possibilities(configMoves):
new_config = new_configMoves['config']
new_moves = new_configMoves['moves']
if new_config not in config_list:
new_config_list += [new_config]
new_configMoves_list += [new_configMoves]
configMoves_list += new_configMoves_list
config_list += new_config_list
counter += 1
if counter > iteration_limit:
print('reached iteration limit')
print(config_list)
break
move_sequence = []
for configMoves in configMoves_list:
if configMoves['config'] == final_config:
move_sequence = configMoves['moves']
return move_sequence
This post is part of the series A Primer on Artificial Intelligence.
Want to get notified about new posts? Join the mailing list.