project 2

Backgrounds

The puzzle was invented by Noyes Palmer Chapman. There is an initial state and goal state of this puzzle. Different types of search strategies are used. These strategies are evaluated based on completeness, Admissibility, Time complexity, and Space complexity. To understand the problem and the solving techniques some background pieces of knowledge are described below:

• Completeness: An algorithm is complete if it can find the solution when a solution exists.
• Admissibility: If a solution is found, it is guaranteed to be optimal.
• Time Complexity: It calculates the worst or average case. Usually measured by the number of nodes expanded.
• Space Complexity: Usually measured by the maximum size of graph/tree during the search