Scribd
Upload
20 views14 pages

8-Puzzle Problem in AI: Strategies & Solutions

Uploaded by

princebj420
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
20 views14 pages

8-Puzzle Problem in AI: Strategies & Solutions

Uploaded by

princebj420
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

8 Puzzel Problem

Introduction to Game Playing in AI


• The 8-Puzzle Problem is a classic problem in Artificial Intelligence.
• Consists of a 3x3 board with 8 numbered tiles and 1 blank space.
• Objective: Arrange tiles in goal state from initial state by sliding tiles.
Problem Statement
• State: Current configuration of tiles.
• Initial State: Any random arrangement of tiles.
• Goal State: Usually

• Operators (Actions): Move blank tile → Up, Down, Left, Right.


Problem Formulation
• State Space:
• All possible configurations (9! = 362,880 states).
• Transition Model:
• Result of applying an operator (sliding blank).
• Path Cost:
• Each move = cost of 1.
• Solution:
• Sequence of moves to reach goal state.
Search Strategies
• Uninformed (Blind Search):
• Breadth-First Search (BFS) → finds shortest solution.
• Depth-First Search (DFS) → may not be optimal.
• Heuristic Search
8 Puzzle Problem using BFS
8 Puzzle Problem using Heuristic Search (A*)
• Find the most cost effective path to reach to the final state from initial
state using A* Algorithm
• F(n) = G(n) + H(n)
• G(n) = Depth of the node
• H(n) = number of misplaced tiles

You might also like