Tower of Hanoi is a mathematical game consisting of three pegs (P1, P2 and P3) and...

  

Transcribed Image Text:

Tower of Hanoi is a mathematical game consisting of three pegs (P1, P2 and P3) and a stack of disks of different diameters. Disks can slide onto any peg. The game starts with all disks stacked on P1 and ends at the point where all disks stacked on P3. The game player is required to move all disks from P1 to P3 using P2 as a buffer. Three rules must be followed when playing the game (1) Only one disk may be moved at a time. (2) Each move involves taking a disk on the top of a peg and place it on the top of another peg. (3) A disk of a larger diameter should never be placed on top of a disk of a smaller diameter. The diagrams below demonstrate the starting state and goal state of the game with 5 disks. P1 P2 P3 P1 P2 P3 AN Starting state Goal state Requirements In this assignment, students are required to solve the Tower of Hanoi (with five disks) using state space search algorithms implemented in Python. Two state space search algorithms: (1) a blind search (depth-first search with depth limit) and (2) a heuristic (A*) search algorithms must be included to complete the assignment. The completion of the assignment consists of two steps as listed below. Step 1 Problem Analysis and Design Before writing the python code, students are required to perform an analysis in order to determine the best design to solve the problem. This includes (1) The representation of the state (2) The representation of the state space (3) The design of the heuristic evaluation function in the A* algorithm The problem analysis and design should be documented in the analysis and design document. Step 2 Coding Write the Python program to implement the design created in Step 1 The program must implement both Depth-First Search and A* Search algorithms. When running the program, it should output (1) The state space with each unsafe state marked and made a dead end. (2) The action plan (the path from the initial state to the goal state) generated by the Depth-first search algorithm. (3) The action plan generated by the A* algorithm. Tower of Hanoi is a mathematical game consisting of three pegs (P1, P2 and P3) and a stack of disks of different diameters. Disks can slide onto any peg. The game starts with all disks stacked on P1 and ends at the point where all disks stacked on P3. The game player is required to move all disks from P1 to P3 using P2 as a buffer. Three rules must be followed when playing the game (1) Only one disk may be moved at a time. (2) Each move involves taking a disk on the top of a peg and place it on the top of another peg. (3) A disk of a larger diameter should never be placed on top of a disk of a smaller diameter. The diagrams below demonstrate the starting state and goal state of the game with 5 disks. P1 P2 P3 P1 P2 P3 AN Starting state Goal state Requirements In this assignment, students are required to solve the Tower of Hanoi (with five disks) using state space search algorithms implemented in Python. Two state space search algorithms: (1) a blind search (depth-first search with depth limit) and (2) a heuristic (A*) search algorithms must be included to complete the assignment. The completion of the assignment consists of two steps as listed below. Step 1 Problem Analysis and Design Before writing the python code, students are required to perform an analysis in order to determine the best design to solve the problem. This includes (1) The representation of the state (2) The representation of the state space (3) The design of the heuristic evaluation function in the A* algorithm The problem analysis and design should be documented in the analysis and design document. Step 2 Coding Write the Python program to implement the design created in Step 1 The program must implement both Depth-First Search and A* Search algorithms. When running the program, it should output (1) The state space with each unsafe state marked and made a dead end. (2) The action plan (the path from the initial state to the goal state) generated by the Depth-first search algorithm. (3) The action plan generated by the A* algorithm.