Ai 8 puzzle problem

8 puzzle problem

1. Welcome to our Presentation

2. Project analysis slide 7 2 8 puzzle problem What is 8 puzzle Problem? The 8-puzzle problem is a  puzzle invented  and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square.

3. Project analysis slide 2 Rules for solving the puzzle Down Left Up Right 

4. Project analysis slide 5 Before we talk about the A* algorithm, we need to discuss Heuristic Search A Heuristic is a technique to solve a problem faster than classic methods, or to find an approximate solution when classic methods cannot. This is a kind of a shortcut as we often trade one of optimality, completeness, accuracy, or precision for speed.

5. Project analysis slide 5 How it works? 1. A* Algorithm maintains a tree of paths originating at the initial state. 2. It extends those paths one edge at a time. 3. It continues until final state is reached.

6. Project analysis slide 8 Example

7. Project analysis slide 8 Example

8. Project analysis slide 8 Example

9. Project analysis slide 8 Example

10. Project analysis slide 8 Example

11. Project analysis slide 3 Pros & Cons Pros:   It is complete and optimal.  It is the best one from other techniques. It is used to solve very complex problems. It is optimally efficient, i.e. there is no other optimal algorithm guaranteed to expand fewer nodes than A*.   Cons :   This algorithm is complete if the branching factor is finite and every action has fixed cost. The speed execution of A* search is highly dependent on the accuracy of the heuristic algorithm that is used to compute h (n).  It has complexity problems.

12. Project analysis slide 3 Important Note A* Algorithm is one of the best path finding algorithms . . But it does not produce the shortest path always. This is because it heavily depends on heuristics .

13. Thank You