Description
1 Objectives
This assignment aims to assist you to expand your knowledge on informed search in the cases of A* and Iterative Deepening A* algorithms.
2 Problem Definition
In this assignment, you are going to solve a Tower of Hanoi puzzle given in any valid state by using A* and Iterative Deepening A* algorithm.
As computer scientist, we love this puzzle and use it everywhere! So, there is a great chance that you’ve seen Tower of Hanoi already as an example for recursion or time complexity etc. However, let’s remember the original definition again, to refresh your memory about the terms and rules of Tower of Hanoi puzzle.
Figure 1: Tower of Hanoi with 5 disks replaced to left-rod initially
Tower of Hanoi is a game consisting of a 3 rods with N disks with varying sizes. Initially, all disks are placed onto a rod in the ascending order of their sizes, so it looks like a neat, canonical shape (see Figure 1). The purpose of the game is moving whole stack of disks to another rod without violating the following rules:
• Only one disk can be moved at a time. • A disk can be moved only if it is on the top of its rod. • No larger disk can be placed of a smaller one at any time. In other words, the ascending order regarding the size of disks should not be disturbed on any rod during the entire game.
1
