CORE PRACTICAL IV
Semester IV ARTIFICIAL INTELLIGENCE LAB
COURSE OBJECTIVES:
To impart knowledge about the practical aspects in Artificial Intelligence
related problems To program different AI methods using a programming language
To know how the logical operations and reason based AI problems are used using
programming
1. Write a program to implement the Hill Climbing problem
2. Write a program to implement the Towers of Hanoi problem
3. Write a program to implement the Missionaries and Cannibals problem
4. Write a program to implement the 8 queens problem
5. Write a program to implement the A* Algorithm
6. Write a program to Implement the Breadth first algorithm
7. Write a program to implement the Depth first algorithm
8. Write a program to implement the predicate logic
COURSE OUTCOMES:
Upon successful completion of this course the students would be able:
• Solve various kinds of problems using AI techniques.
• Solve basic AI based problems using any programming language.
• Understand to implement the various kinds of AI based algorithms.
• Apply AI techniques to real-world problems to develop intelligent systems.
• To understand problems related to AI.
*****
1. Write a program to implement the Hill Climbing problem
import random
def objective_function(x):
return -(x**2 - 4*x + 4) # Example: f(x) = -(x^2 - 4x + 4)
def hill_climbing():
current_solution = random.uniform(-10, 10) # Random initial guess
current_value = objective_function(current_solution)
while True:
neighbors = [current_solution + 0.1, current_solution - 0.1] # Generate neighbors
next_solution = max(neighbors, key=lambda x: objective_function(x)) # Choose best
neighbor
next_value = objective_function(next_solution)
if next_value <= current_value: # If no improvement, stop
break
current_solution, current_value = next_solution, next_value
return current_solution, current_value
best_solution, best_value = hill_climbing()
print(f"Best Solution: {best_solution}, Value: {best_value}")
Output:
Best Solution: 1.9513126518605843, Value: -0.0023704578688485967
2. Write a program to implement the Towers of Hanoi problem
def towers_of_hanoi(n, source, auxiliary, destination):
# Base case: If only one disk, move it directly from source to destination
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
# Move n-1 disks from source to auxiliary, so they are out of the way
towers_of_hanoi(n - 1, source, destination, auxiliary)
# Move the nth disk from source to destination
print(f"Move disk {n} from {source} to {destination}")
# Move the n-1 disks from auxiliary to destination
towers_of_hanoi(n - 1, auxiliary, source, destination)
# Number of disks
n = 3 # Change this value to solve for different numbers of disks
# Call the function with source peg 'A', auxiliary peg 'B', and destination peg 'C'
towers_of_hanoi(n, 'A', 'B', 'C')
Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
3. Write a program to implement the Missionaries and Cannibals
problem
def is_valid(m_left, c_left, m_right, c_right):
# At no point, cannibals should outnumber missionaries on either side
if (m_left > 0 and m_left < c_left) or (m_right > 0 and m_right < c_right):
return False
if m_left < 0 or c_left < 0 or m_right < 0 or c_right < 0:
return False
if m_left > 3 or c_left > 3 or m_right > 3 or c_right > 3:
return False
return True
def print_state(m_left, c_left, m_right, c_right, boat):
print(f"Left side: {m_left} missionaries, {c_left} cannibals | Right side: {m_right} missionaries,
{c_right} cannibals | Boat: {boat}")
def move(m_left, c_left, m_right, c_right, boat, moves):
if m_left == 0 and c_left == 0:
# Base case: All missionaries and cannibals have been moved to the right side
print("\nSolution found!")
for move in moves:
print(move)
return True
if boat == 'left':
# Try all valid moves from the left side to the right side
for m in range(0, 3):
for c in range(0, 3):
if m + c >= 1 and m + c <= 2: # Boat can carry at most 2 people
new_m_left = m_left - m
new_c_left = c_left - c
new_m_right = m_right + m
new_c_right = c_right + c
if is_valid(new_m_left, new_c_left, new_m_right, new_c_right):
# Make the move
moves.append(f"Move {m} missionaries and {c} cannibals from left to right")
if move(new_m_left, new_c_left, new_m_right, new_c_right, 'right', moves):
return True
# Backtrack
moves.pop()
else:
# Try all valid moves from the right side to the left side
for m in range(0, 3):
for c in range(0, 3):
if m + c >= 1 and m + c <= 2: # Boat can carry at most 2 people
new_m_left = m_left + m
new_c_left = c_left + c
new_m_right = m_right - m
new_c_right = c_right - c
if is_valid(new_m_left, new_c_left, new_m_right, new_c_right):
# Make the move
moves.append(f"Move {m} missionaries and {c} cannibals from right to left")
if move(new_m_left, new_c_left, new_m_right, new_c_right, 'left', moves):
return True
# Backtrack
moves.pop()
return False
def missionaries_and_cannibals():
m_left, c_left = 3, 3 # 3 missionaries and 3 cannibals on the left side
m_right, c_right = 0, 0 # None on the right side
boat = 'left' # The boat starts on the left side
moves = [] # List to record the moves
# Start the recursive search for a solution
print_state(m_left, c_left, m_right, c_right, boat)
if not move(m_left, c_left, m_right, c_right, boat, moves):
print("No solution found")
# Run the problem
missionaries_and_cannibals()
Output:
Left side: 3 missionaries, 3 cannibals | Right side: 0 missionaries, 0 cannibals | Boat: left
Move 1 missionaries and 1 cannibals from left to right
Left side: 2 missionaries, 2 cannibals | Right side: 1 missionaries, 1 cannibals | Boat: right
Move 2 missionaries and 0 cannibals from right to left
Left side: 4 missionaries, 2 cannibals | Right side: 1 missionaries, 1 cannibals | Boat: left
Move and
4. Write a program to implement the 8 queens problem
# Function to check if the current position is safe for placing a queen
def is_safe(board, row, col, n):
# Check the column
for i in range(row):
if board[i] == col or \
board[i] - i == col - row or \
board[i] + i == col + row:
return False
return True
# Function to solve the 8 queens problem using backtracking
def solve_n_queens(board, row, n):
if row == n:
# All queens are placed successfully, print the board configuration
print_board(board, n)
return True
res = False
for col in range(n):
if is_safe(board, row, col, n):
# Place the queen on the board
board[row] = col
# Recur to place queens in the next rows
res = solve_n_queens(board, row + 1, n) or res
# Backtrack (not needed explicitly, as we overwrite the board[row])
return res
# Function to print the board
def print_board(board, n):
for i in range(n):
row = ['Q' if j == board[i] else '.' for j in range(n)]
print(' '.join(row))
print("\n")
# Main function to solve the 8 queens problem
def eight_queens(n=8):
# Initialize the board with -1 (meaning no queen is placed)
board = [-1] * n
if not solve_n_queens(board, 0, n):
print("No solution found.")
# Run the solution for 8 queens
eight_queens()
Output:
Q.......
....Q...
......Q.
.Q......
...Q....
.....Q..
..Q.....
.......Q
5. Write a program to implement the A* Algorithm
import heapq
# Define the 4 possible movements (up, down, left, right)
MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, Down, Left, Right
class Node:
def __init__(self, position, g, h):
self.position = position # Position in the grid (x, y)
self.g = g # Cost from start to this node
self.h = h # Heuristic estimate of cost to goal
self.f = g + h # Total cost (f = g + h)
self.parent = None # Parent node (used for path reconstruction)
def __lt__(self, other):
return self.f < other.f # For comparison in the priority queue (min-heap)
# Heuristic function (Manhattan Distance)
def heuristic(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
# A* algorithm to find the shortest path from start to goal
def astar(start, goal, grid):
open_list = [] # The priority queue (min-heap)
closed_list = set() # Set to track visited nodes
# Start node with g=0 and h as the heuristic from start to goal
start_node = Node(start, 0, heuristic(start, goal))
heapq.heappush(open_list, start_node) # Push the start node to the open list
while open_list:
# Get the node with the lowest f-value
current_node = heapq.heappop(open_list)
if current_node.position == goal:
# Goal reached, reconstruct the path
path = []
while current_node:
path.append(current_node.position)
current_node = current_node.parent
return path[::-1] # Return reversed path (start to goal)
closed_list.add(current_node.position) # Add current node to closed list
# Explore neighbors
for move in MOVES:
neighbor_pos = (current_node.position[0] + move[0], current_node.position[1] +
move[1])
# Skip out-of-bounds neighbors or blocked cells
if (0 <= neighbor_pos[0] < len(grid)) and (0 <= neighbor_pos[1] < len(grid[0])) and
grid[neighbor_pos[0]][neighbor_pos[1]] != 1:
if neighbor_pos in closed_list:
continue
# Calculate g, h, and f values for the neighbor
g = current_node.g + 1 # Assume cost between neighbors is always 1
h = heuristic(neighbor_pos, goal)
neighbor_node = Node(neighbor_pos, g, h)
# If the neighbor is not in the open list, or has a lower f-value, add it to the open
list
if not any(neighbor_node.position == node.position and neighbor_node.f >= node.f for
node in open_list):
neighbor_node.parent = current_node
heapq.heappush(open_list, neighbor_node)
return None # If no path is found
# Grid representation (0 = free space, 1 = blocked cell)
grid = [
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0]
# Define start and goal positions
start = (0, 0) # Start at top-left corner
goal = (5, 5) # Goal at bottom-right corner
# Run A* algorithm
path = astar(start, goal, grid)
if path:
print("Path found:")
print(path)
else:
print("No path found.")
Output:
Path found:
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]
6. Write a program to Implement the Breadth first algorithm
from collections import deque
# Function to perform BFS on a graph
def bfs(graph, start):
# Create a set to keep track of visited nodes
visited = set()
# Create a queue for BFS and enqueue the start node
queue = deque([start])
# Mark the start node as visited
visited.add(start)
# List to store the BFS traversal order
bfs_order = []
while queue:
# Dequeue a vertex from the queue
node = queue.popleft()
# Process the node (in this case, print it)
bfs_order.append(node)
# Get all the neighbors of the current node
for neighbor in graph[node]:
if neighbor not in visited:
# If the neighbor has not been visited, enqueue it and mark it as visited
queue.append(neighbor)
visited.add(neighbor)
return bfs_order
# Example graph represented as an adjacency list
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1],
4: [1, 2]
# Starting node for BFS
start_node = 0
# Perform BFS and print the result
bfs_traversal = bfs(graph, start_node)
print("BFS Traversal Order:", bfs_traversal)
Output:
Graph:
0 -- 1 -- 3
| |
2 -- 4
Start node: 0
BFS Traversal Order: [0, 1, 2, 3, 4]
7. Write a program to implement the Depth first algorithm
# Iterative Depth First Search (DFS) using stack
def dfs_iterative(graph, start):
visited = set() # Set to keep track of visited nodes
stack = [start] # Stack to store nodes to be explored
# List to store the DFS traversal order
dfs_order = []
while stack:
node = stack.pop() # Pop a node from the stack
if node not in visited:
visited.add(node) # Mark the node as visited
dfs_order.append(node) # Process the node (in this case, append to dfs_order)
# Add all unvisited neighbors to the stack
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return dfs_order
# Example graph represented as an adjacency list
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1],
4: [1, 2]
# Starting node for DFS
start_node = 0
# Perform DFS (iterative)
dfs_traversal = dfs_iterative(graph, start_node)
print("DFS Traversal (Iterative):", dfs_traversal)
# Recursive Depth First Search (DFS)
def dfs_recursive(graph, node, visited=None, dfs_order=None):
if visited is None:
visited = set() # Set to keep track of visited nodes
if dfs_order is None:
dfs_order = [] # List to store the DFS traversal order
# Mark the node as visited and process it
visited.add(node)
dfs_order.append(node)
# Recur for all the unvisited neighbors
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, dfs_order)
return dfs_order
# Perform DFS (recursive)
dfs_traversal_recursive = dfs_recursive(graph, start_node)
print("DFS Traversal (Recursive):", dfs_traversal_recursive)
Output:
Graph:
0 -- 1 -- 3
| |
2 -- 4
Start node: 0
DFS Traversal (Iterative): [0, 2, 4, 1, 3]
DFS Traversal (Recursive): [0, 1, 3, 4, 2]
8. Write a program to implement the predicate logic
# Define some facts (base predicates)
def is_sibling(x, y):
"""Predicate: x and y are siblings"""
siblings = {
("Alice", "Bob"),
("Bob", "Alice"),
("Charlie", "David"),
("David", "Charlie")
}
return (x, y) in siblings or (y, x) in siblings
def is_parent(x, y):
"""Predicate: x is a parent of y"""
parents = {
("Alice", "Charlie"),
("Alice", "David"),
("Bob", "Charlie"),
("Bob", "David")
return (x, y) in parents
def is_grandparent(x, y):
"""Predicate: x is a grandparent of y (if x is a parent of some z, and z is a parent of y)"""
# Check if x is a parent of someone who is a parent of y
for z in ["Alice", "Bob"]:
if is_parent(x, z) and is_parent(z, y):
return True
return False
# Query predicates
def main():
print("Is Alice a sibling of Bob?", is_sibling("Alice", "Bob"))
print("Is Alice a parent of Charlie?", is_parent("Alice", "Charlie"))
print("Is Alice a grandparent of Charlie?", is_grandparent("Alice", "Charlie"))
print("Is Alice a grandparent of David?", is_grandparent("Alice", "David"))
if __name__ == "__main__":
main()
Output
Is Alice a sibling of Bob? True
Is Alice a parent of Charlie? True
Is Alice a grandparent of Charlie? False
Is Alice a grandparent of David? False
