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