Indira Gandhi Delhi
University Technical
for Women
(Established by Govt. of Delhi vide Act 09 of 2012)
Kashmere Gate, Delhi – 110006
Practical File
Artificial Intelligence
(BAI-201)
Submitted By:
Divyanshi
05401172023
Submitted to
Dr. Rahul Sachdeva, Assistant Professor
Department of AI & DS
LIST OF PROGRAMS
S. No. Title
1 Write a program to implement Breadth First Search (for Tic-Tac-Toe
Problem).
2 Write a program to implement Depth First Search (for Water Jug
Problem).
3 Write a program to implement Best Fit Search (BFS).
4 Write a program to implement A* Search.
5 Write a program to Solve 8-puzzle problem using Best Fit Search.
6 Study of PROLOG Programming Language and its functions. Write
simple facts for the statements using PROLOG.
7 Build a mini project in a Group of 03 Students demonstrating the use
of AI in real life.
EXPERIMENT 1
PROBLEM TITLE
Depth First Search (DFS) for the Water Jug Problem
OBJECTIVE OF THE PROGRAM
To implement the Depth First Search (DFS) algorithm to solve the Water Jug
problem and determine whether a specific amount of water can be measured using
two jugs of fixed capacities.
DESCRIPTION
The Water Jug Problem is a classic example of problem-solving in Artificial
Intelligence, involving two jugs with fixed capacities. The task is to measure a
specific quantity of water using these jugs and basic operations such as filling,
emptying, or transferring water.
This problem is represented as a state-space graph, where:
Nodes represent the current water levels in the two jugs.
Edges represent transitions between states via valid operations.
The Depth First Search (DFS) algorithm explores each possible path as deeply as
possible before backtracking. This ensures all potential solutions are considered.
ALGORITHM
The algorithm follows a clear and systematic approach to solve the Tic-Tac-Toe
problem using BFS:
Define the Initial State:
Start with an empty 3x3 Tic-Tac-Toe board represented as a list of lists.
Represent the Board as a Graph:
Each board state is treated as a node in a graph, and valid moves (from one state to
another) form the edges between nodes.
Initialize the Queue:
The BFS algorithm uses a queue to store the states that need to be explored.
Initially, the queue contains only the starting state of the board.
Mark the Initial State as Visited:
The state of the board is added to a visited set to avoid re-processing the same state.
Process Each State:
While the queue is not empty, do the following:
Dequeue the Front State: Process the state at the front of the queue.
Check for Winning Conditions: If the current board is a winning state, terminate the
search and return the winning state.
Generate Valid Next States: Generate all possible states that can be reached from
the current state by placing a mark (1 for player 1 or 2 for player 2) in any empty
spot on the board.
Add Unvisited States to the Queue: If the new state has not been visited, add it to
the queue and mark it as visited.
Return the Solution:
If BFS completes and a winner is found, return the board configuration that leads to
the win. If no solution is found, return "No winner."
Termination:
If the queue becomes empty and no winning state is detected, return "No winner."
CODE
EXPECTED OUTPUT
The program will print the intermediate board states during BFS exploration. It will
also indicate whether a winner has been found or not. Here is a sample output:
If there is no winner, the output will be:
Exploring current board state:
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
Exploring current board state:
[1, 0, 0]
[0, 0, 0]
[0, 0, 0]
...
No winner found.
CONCLUSION
By using Breadth First Search, the program effectively explores all potential states
of a Tic-Tac-Toe game. BFS guarantees that all possible game configurations are
examined in a systematic manner. If a solution exists, it will be found. If no
winning state is found, the program concludes that there is no winner. This method
can be used for more complex games as well, where every move needs to be
considered before deciding the best outcome.
