In this blog post, you will find solutions for the **Artificial Intelligence Lab Component (BAD402)** course work for the IV semester of **VTU** university. To follow along, you will need to have up a machine running any flavour of **GNULinux** OS. We recommend using the **Anaconda** Python Distribution for this lab. The solutions have been tested on **Ubuntu 22.04 **OS. You can find the lab syllabus on the university’s website or here below.

All these solutions have been maintained at the following git repository shown below. If you want to contribute send me a PR.

To get your Python development environment up and running setup Anaconda Distribution on your system. You can find the detailed procedure here.

### Setting up Anaconda Distribution on Ubuntu.

### Setting up Anaconda Distribution on Windows.

After getting the necessary development environment setup, Now lets focus on the solutions.

## Question 1

## Solving Water Jug Problem using DFS

**Implement and Demonstrate Depth First Search Algorithm on Water Jug Problem.**

The Water Jug Problem is a classic puzzle in which you are given two jugs with specific capacities and a target volume that you need to measure using these jugs. The goal is to determine a sequence of pouring operations that allows you to measure out exactly the desired amount of water using the given jugs. The operations typically involve filling a jug, emptying a jug, or pouring water from one jug into another until you achieve the desired volume.

Let’s explain the Water Jug Problem using an example:

**Problem Setup:** Suppose you have two jugs:

- Jug 1 has a capacity of 4 liters (
`jug1_capacity = 4`

). - Jug 2 has a capacity of 3 liters (
`jug2_capacity = 3`

).

You want to measure exactly 2 liters of water (`target_volume = 2`

) using these jugs.

**Operations Allowed:** You can perform the following operations:

**Fill a Jug:**Fill either jug to its maximum capacity from a water source.**Empty a Jug:**Empty either jug completely.**Pour Water:**Pour water from one jug to another until the pouring jug is either empty or the receiving jug is full.

**Objective:** Find a sequence of operations that allows you to measure out exactly 2 liters of water using the jugs.

**DFS Exploration:**

- Start from
`(0, 0)`

(both jugs empty). - Try all possible operations recursively, marking visited states to avoid loops:
- Fill Jug 1 →
`(4, 0)`

- Pour Jug 1 to Jug 2 →
`(1, 3)`

- Empty Jug 2 →
`(1, 0)`

- Pour Jug 1 to Jug 2 →
`(0, 1)`

- Fill Jug 1 →
`(4, 1)`

- Pour Jug 1 to Jug 2 →
`(2, 3)`

- Fill Jug 1 →

The DFS algorithm will eventually find a sequence of operations that leads to one of the states having 2 liters in either jug, achieving the target volume.

### Python Code

```
class WaterJugState:
def __init__(self, jug1, jug2):
self.jug1 = jug1
self.jug2 = jug2
def __eq__(self, other):
return self.jug1 == other.jug1 and self.jug2 == other.jug2
def __hash__(self):
return hash((self.jug1, self.jug2))
def dfs(current_state, visited, jug1_capacity, jug2_capacity, target_volume):
if current_state.jug1 == target_volume or current_state.jug2 == target_volume:
if current_state.jug1 == target_volume :
print("Jug 1 now has", target_volume, "liters.")
else:
print("Jug 2 now has", target_volume, "liters.")
return True
visited.add(current_state)
# Define all possible operations: (action, from_jug, to_jug)
operations = [
('Fill Jug 1', jug1_capacity, current_state.jug2),
('Fill Jug 2', current_state.jug1, jug2_capacity),
('Empty Jug 1', 0, current_state.jug2),
('Empty Jug 2', current_state.jug1, 0),
('Pour Jug 1 to Jug 2',
max(0, current_state.jug1 + current_state.jug2 - jug2_capacity),
min(jug2_capacity, current_state.jug1 + current_state.jug2)),
('Pour Jug 2 to Jug 1',
min(jug1_capacity, current_state.jug1 + current_state.jug2),
max(0, current_state.jug1 + current_state.jug2 - jug1_capacity))
]
for operation in operations:
action, new_jug1, new_jug2 = operation
new_state = WaterJugState(new_jug1, new_jug2)
if new_state not in visited:
print(f"Trying: {action} => ({new_jug1}, {new_jug2})")
if dfs(new_state, visited, jug1_capacity, jug2_capacity, target_volume):
return True
# print(new_jug1, new_jug2)
return False
def solve_water_jug_problem(jug1_capacity, jug2_capacity, target_volume):
initial_state = WaterJugState(0, 0)
visited = set()
if dfs(initial_state, visited, jug1_capacity, jug2_capacity, target_volume):
print("Solution found!")
# print(jug1_capacity, jug2_capacity)
else:
print("Solution not possible.")
# Example usage:
jug1_capacity = int(input("Enter Jug 1 capacity : "))
jug2_capacity = int(input("Enter Jug 1 capacity : "))
target_volume = int(input("Enter Target Volume : "))
print(f"Solving Water Jug Problem with capacities ({jug1_capacity}, {jug2_capacity}) to measure {target_volume} liters.")
solve_water_jug_problem(jug1_capacity, jug2_capacity, target_volume)
```

### Output

```
$ python 01_DFS_WJP.py
Enter Jug 1 capacity : 5
Enter Jug 1 capacity : 4
Enter Target Volume : 3
Solving Water Jug Problem with capacities (5, 4) to measure 3 liters.
Trying: Fill Jug 1 => (5, 0)
Trying: Fill Jug 2 => (5, 4)
Trying: Empty Jug 1 => (0, 4)
Trying: Pour Jug 2 to Jug 1 => (4, 0)
Trying: Fill Jug 2 => (4, 4)
Trying: Pour Jug 2 to Jug 1 => (5, 3)
Jug 2 now has 3 liters.
Solution found!
$ python 01_DFS_WJP.py
Enter Jug 1 capacity : 2
Enter Jug 1 capacity : 2
Enter Target Volume : 6
Solving Water Jug Problem with capacities (2, 2) to measure 6 liters.
Trying: Fill Jug 1 => (2, 0)
Trying: Fill Jug 2 => (2, 2)
Trying: Empty Jug 1 => (0, 2)
Solution not possible.
```

## Question 2

## Solving Missionaries-Cannibals Problem using BFS

**Implement and Demonstrate Best First Search Algorithm on Missionaries-Cannibals Problems using Python**

The Missionaries and Cannibals Problem is a classic river crossing puzzle that involves transporting missionaries and cannibals from one side of a river to the other using a boat, under certain constraints to ensure the safety of the missionaries.

**Problem Description:**

**Initial State:**- Three missionaries (
`M`

) and three cannibals (`C`

) are located on one side of a river. - The boat is also on this side of the river.
- The other side of the river is empty.

- Three missionaries (
**Goal State:**- All missionaries and cannibals successfully transported to the other side of the river.
- No missionary is left in the presence of cannibals on either side of the river at any time (to avoid missionaries being eaten).

**Constraints:**- The boat can carry a maximum of two people (either two missionaries, two cannibals, or one of each).
- At no point should there be more cannibals than missionaries on either side of the river (to prevent cannibals from outnumbering and eating the missionaries).

**Objective:** Devise a sequence of boat trips to move all missionaries and cannibals from one side of the river to the other, adhering to the above constraints and reaching the goal state.

### Python Code

```
from queue import PriorityQueue
# Define the state class for the Missionaries and Cannibals Problem
class State:
def __init__(self, left_m, left_c, boat, right_m, right_c):
self.left_m = left_m # Number of missionaries on the left bank
self.left_c = left_c # Number of cannibals on the left bank
self.boat = boat # 1 if boat is on the left bank, 0 if on the right bank
self.right_m = right_m # Number of missionaries on the right bank
self.right_c = right_c # Number of cannibals on the right bank
def is_valid(self):
# Check if the state is valid (no missionaries eaten on either bank)
if self.left_m < 0 or self.left_c < 0 or self.right_m < 0 or self.right_c < 0:
return False
if self.left_m > 0 and self.left_c > self.left_m:
return False
if self.right_m > 0 and self.right_c > self.right_m:
return False
return True
def is_goal(self):
# Check if the state is the goal state (all missionaries and cannibals on the right bank)
return self.left_m == 0 and self.left_c == 0
def __lt__(self, other):
# Define less-than operator for PriorityQueue comparison (used in Best-First Search)
return False
def __eq__(self, other):
# Define equality operator for comparing states
return self.left_m == other.left_m and self.left_c == other.left_c \
and self.boat == other.boat and self.right_m == other.right_m \
and self.right_c == other.right_c
def __hash__(self):
# Define hash function for storing states in a set
return hash((self.left_m, self.left_c, self.boat, self.right_m, self.right_c))
def successors(state):
# Generate all valid successor states from the current state
succ_states = []
if state.boat == 1: # Boat is on the left bank
for m in range(3):
for c in range(3):
if 1 <= m + c <= 2: # Boat capacity is 2
new_state = State(state.left_m - m, state.left_c - c, 0,
state.right_m + m, state.right_c + c)
if new_state.is_valid():
succ_states.append(new_state)
else: # Boat is on the right bank
for m in range(3):
for c in range(3):
if 1 <= m + c <= 2: # Boat capacity is 2
new_state = State(state.left_m + m, state.left_c + c, 1,
state.right_m - m, state.right_c - c)
if new_state.is_valid():
succ_states.append(new_state)
return succ_states
def best_first_search():
start_state = State(3, 3, 1, 0, 0)
goal_state = State(0, 0, 0, 3, 3)
frontier = PriorityQueue()
frontier.put((0, start_state)) # Priority queue with (cost, state)
came_from = {}
cost_so_far = {}
came_from[start_state] = None
cost_so_far[start_state] = 0
while not frontier.empty():
current_cost, current_state = frontier.get()
if current_state == goal_state:
# Reconstruct the path from start_state to goal_state
path = []
while current_state is not None:
path.append(current_state)
current_state = came_from[current_state]
path.reverse()
return path
for next_state in successors(current_state):
new_cost = cost_so_far[current_state] + 1 # Uniform cost of 1 for each move
if next_state not in cost_so_far or new_cost < cost_so_far[next_state]:
cost_so_far[next_state] = new_cost
priority = new_cost # Best-First Search uses cost as priority
frontier.put((priority, next_state))
came_from[next_state] = current_state
return None # No path found
def print_solution(path):
if path is None:
print("No solution found.")
else:
print("Solution found!")
for i, state in enumerate(path):
print(f"Step {i}:")
print(f"Left Bank: {state.left_m} missionaries, {state.left_c} cannibals")
print(f"Boat is {'on the left' if state.boat == 1 else 'on the right'} bank")
print(f"Right Bank: {state.right_m} missionaries, {state.right_c} cannibals")
print("------------")
# Main function to run the Best-First Search and print the solution
if __name__ == "__main__":
solution_path = best_first_search()
print_solution(solution_path)
```

### Output

```
Solution found!
Step 0:
Left Bank: 3 missionaries, 3 cannibals
Boat is on the left bank
Right Bank: 0 missionaries, 0 cannibals
------------
Step 1:
Left Bank: 3 missionaries, 1 cannibals
Boat is on the right bank
Right Bank: 0 missionaries, 2 cannibals
------------
Step 2:
Left Bank: 3 missionaries, 2 cannibals
Boat is on the left bank
Right Bank: 0 missionaries, 1 cannibals
------------
Step 3:
Left Bank: 3 missionaries, 0 cannibals
Boat is on the right bank
Right Bank: 0 missionaries, 3 cannibals
------------
Step 4:
Left Bank: 3 missionaries, 1 cannibals
Boat is on the left bank
Right Bank: 0 missionaries, 2 cannibals
------------
Step 5:
Left Bank: 1 missionaries, 1 cannibals
Boat is on the right bank
Right Bank: 2 missionaries, 2 cannibals
------------
Step 6:
Left Bank: 2 missionaries, 2 cannibals
Boat is on the left bank
Right Bank: 1 missionaries, 1 cannibals
------------
Step 7:
Left Bank: 0 missionaries, 2 cannibals
Boat is on the right bank
Right Bank: 3 missionaries, 1 cannibals
------------
Step 8:
Left Bank: 0 missionaries, 3 cannibals
Boat is on the left bank
Right Bank: 3 missionaries, 0 cannibals
------------
Step 9:
Left Bank: 0 missionaries, 1 cannibals
Boat is on the right bank
Right Bank: 3 missionaries, 2 cannibals
------------
Step 10:
Left Bank: 0 missionaries, 2 cannibals
Boat is on the left bank
Right Bank: 3 missionaries, 1 cannibals
------------
Step 11:
Left Bank: 0 missionaries, 0 cannibals
Boat is on the right bank
Right Bank: 3 missionaries, 3 cannibals
------------
```

## Question 3

## A* Search algorithm

**Implement A* Search algorithm**

Here’s a general approach to applying A* search to graphs with more than 4 vertices:

### State Representation:

- Define a meaningful representation for the state of the problem. This could be a tuple, a custom class, or any data structure that encapsulates the current state of the problem.

### Goal Test:

- Implement a function (
`goal_test(state)`

) that checks whether a given state is the goal state. This function will vary based on the problem you are trying to solve.

### Successors Function:

- Define a function (
`successors(state)`

) that generates valid successor states from a given state. Each successor state should be associated with the action taken to reach it and the cost (or distance) associated with that action.

### Heuristic Function:

- Implement a heuristic function (
`heuristic(state)`

) that estimates the cost from a given state to the goal state. This function is crucial for guiding the search efficiently towards the goal and can greatly impact the performance of A* search.

### Applying A* Search:

**Initialize Priority Queue:**Use a priority queue (e.g.,`heapq`

) to manage the frontier of nodes to explore. Nodes are prioritized based on their estimated cost (`f = g + h`

), where`g`

is the actual cost from the start node and`h`

is the heuristic estimate from the node to the goal.**Explore Nodes:**Continuously expand nodes from the frontier based on the lowest estimated cost (`f`

). Update the cost and heuristic values for each node as necessary.**Goal Check:**When expanding a node, check if it represents the goal state (`goal_test`

). If so, reconstruct and return the path from the start node to the goal node.**Generate Successors:**For each expanded node, generate its successor nodes using the`successors`

function. Calculate the total cost to reach each successor and update their heuristic values.

### Python Code

```
import heapq
class Node:
def __init__(self, state, parent=None, action=None, cost=0, heuristic=0):
self.state = state # Current state in the search space
self.parent = parent # Parent node
self.action = action # Action that led to this node from the parent node
self.cost = cost # Cost to reach this node from the start node
self.heuristic = heuristic # Heuristic estimate of the cost to reach the goal
def __lt__(self, other):
return (self.cost + self.heuristic) < (other.cost + other.heuristic)
def parse_graph_input():
graph = {}
num_edges = int(input("Enter the number of edges: "))
for _ in range(num_edges):
u, v, cost = input("Enter an edge (format: u v cost): ").split()
cost = int(cost)
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append((v, cost))
graph[v].append((u, cost))
return graph
def astar_search(start_state, goal_test, successors, heuristic):
# Priority queue to store nodes ordered by f = g + h
frontier = []
heapq.heappush(frontier, Node(start_state, None, None, 0, heuristic(start_state)))
explored = set()
while frontier:
current_node = heapq.heappop(frontier)
current_state = current_node.state
if goal_test(current_state):
# Reconstruct the path from the goal node to the start node
path = []
while current_node.parent is not None:
path.append((current_node.action, current_node.state))
current_node = current_node.parent
path.reverse()
return path
explored.add(current_state)
# Generate successors for the current state using the `successors` function
for action, successor_state, step_cost in successors(current_state):
if successor_state not in explored:
new_cost = current_node.cost + step_cost
new_node = Node(successor_state, current_node, action, new_cost, heuristic(successor_state))
heapq.heappush(frontier, new_node)
return None # No path found
if __name__ == "__main__":
# Get user input to define the graph
print("Define the graph:")
graph = parse_graph_input()
start_state = input("Enter the start state: ")
goal_state = input("Enter the goal state: ")
def goal_test(state):
return state == goal_state
def successors(state):
# Generate successor states from the current state based on the graph
successors_list = []
for neighbor, cost in graph.get(state, []):
action = f"Move to {neighbor}" # Default action (e.g., "Move to B")
successor_state = neighbor
step_cost = cost
successors_list.append((action, successor_state, step_cost))
return successors_list
def heuristic(state):
# Define a simple heuristic function (e.g., straight-line distance)
heuristic_values = {key: abs(ord(key) - ord(goal_state)) for key in graph.keys()}
return heuristic_values.get(state, float('inf')) # Default to infinity if state not found
# Perform A* search using custom successors function
path = astar_search(start_state, goal_test, successors, heuristic)
# Print the resulting path found by A* search
if path:
print("Path found:")
for action, state in path:
print(f"Action: {action}, State: {state}")
else:
print("No path found.")
```

### Output

```
$ python 03Astar_search.py
Define the graph:
Enter the number of edges: 7
Enter an edge (format: u v cost): A B 1
Enter an edge (format: u v cost): A C 3
Enter an edge (format: u v cost): B C 1
Enter an edge (format: u v cost): B D 2
Enter an edge (format: u v cost): C D 1
Enter an edge (format: u v cost): D E 4
Enter an edge (format: u v cost): E G 3
Enter the start state: A
Enter the goal state: G
Path found:
Action: Move to B, State: B
Action: Move to D, State: D
Action: Move to E, State: E
Action: Move to G, State: G
```

## Question 4

## AO* Search algorithm

**Implement AO* Search algorithm**

### Python Code

```
import heapq
class Node:
def __init__(self, state, parent=None, action=None, cost=0, heuristic=0):
self.state = state # Current state in the search space
self.parent = parent # Parent node
self.action = action # Action that led to this node from the parent node
self.cost = cost # Cost to reach this node from the start node
self.heuristic = heuristic # Heuristic estimate of the cost to reach the goal
def __lt__(self, other):
return (self.cost + self.heuristic) < (other.cost + other.heuristic)
def parse_graph_input():
graph = {}
num_edges = int(input("Enter the number of edges: "))
for _ in range(num_edges):
u, v, cost = input("Enter an edge (format: u v cost): ").split()
cost = float(cost)
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append((v, cost))
return graph
def ao_star_search(start_state, goal_state, graph):
frontier = []
heapq.heappush(frontier, Node(start_state, None, None, 0, heuristic(start_state, goal_state)))
explored = {}
while frontier:
current_node = heapq.heappop(frontier)
current_state = current_node.state
if current_state == goal_state:
# Reconstruct the path from the goal node to the start node
path = []
while current_node.parent is not None:
path.append((current_node.action, current_node.state))
current_node = current_node.parent
path.reverse()
return path
if current_state not in explored or current_node.cost < explored[current_state]:
explored[current_state] = current_node.cost
for neighbor, step_cost in graph.get(current_state, []):
new_cost = current_node.cost + step_cost
new_node = Node(neighbor, current_node, f"Move to {neighbor}", new_cost, heuristic(neighbor, goal_state))
heapq.heappush(frontier, new_node)
return None # No path found
def heuristic(state, goal_state):
# Simple heuristic function (e.g., straight-line distance)
heuristic_values = {'A': 5, 'B': 3, 'C': 2, 'D': 1, 'E': 2, 'G': 0} # Custom heuristic values based on problem domain
return heuristic_values.get(state, float('inf')) # Default to infinity if state not found
if __name__ == "__main__":
# Get user input to define the graph
print("Define the graph:")
graph = parse_graph_input()
start_state = input("Enter the start state: ")
goal_state = input("Enter the goal state: ")
# Perform AO* search using the defined graph, start state, and goal state
path = ao_star_search(start_state, goal_state, graph)
# Print the resulting path found by AO* search
if path:
print("Path found:")
for action, state in path:
print(f"Action: {action}, State: {state}")
else:
print("No path found.")
```

### Output

```
$ python 04AOstar_search.py
Define the graph:
Enter the number of edges: 8
Enter an edge (format: u v cost): S A 3
Enter an edge (format: u v cost): S B 2
Enter an edge (format: u v cost): A C 4
Enter an edge (format: u v cost): A D 2
Enter an edge (format: u v cost): B E 3
Enter an edge (format: u v cost): C G 2
Enter an edge (format: u v cost): D G 5
Enter an edge (format: u v cost): E G 4
Enter the start state: S
Enter the goal state: G
Path found:
Action: Move to B, State: B
Action: Move to E, State: E
Action: Move to G, State: G
```

## Question 5

**8-Queens Problem**

**Solve 8-Queens Problem with suitable assumptions**

### Python Code for first solution

```
def is_safe(board, row, col):
""" Check if it's safe to place a queen at board[row][col] """
# Check column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper diagonal on left side
i, j = row, col
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
# Check upper diagonal on right side
i, j = row, col
while i >= 0 and j < len(board):
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve_queens(board, row):
""" Recursively solve the 8-Queens Problem using backtracking """
n = len(board)
# Base case: If all queens are placed, return True
if row >= n:
return True
for col in range(n):
if is_safe(board, row, col):
board[row][col] = 1 # Place the queen
# Recur to place the rest of the queens
if solve_queens(board, row + 1):
return True
# If placing queen at board[row][col] doesn't lead to a solution, backtrack
board[row][col] = 0 # Backtrack
return False
def print_board(board):
""" Print the board configuration """
n = len(board)
for i in range(n):
for j in range(n):
print(board[i][j], end=" ")
print()
def solve_8queens():
""" Solve the 8-Queens Problem and print the solution """
n = 8 # Size of the chessboard (8x8)
board = [[0] * n for _ in range(n)] # Initialize empty board
if solve_queens(board, 0):
print("Solution found:")
print_board(board)
else:
print("No solution exists.")
# Call the function to solve the 8-Queens Problem
solve_8queens()
```

### Output

```
$ python 05NQueens.py
Solution found:
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
```

### Python Code for all solution

```
def is_safe(board, row, col):
""" Check if it's safe to place a queen at board[row][col] """
n = len(board)
# Check column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper diagonal on left side
i, j = row, col
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
# Check upper diagonal on right side
i, j = row, col
while i >= 0 and j < n:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve_queens(board, row, solutions):
""" Recursively solve the 8-Queens Problem using backtracking """
n = len(board)
# Base case: If all queens are placed, add the solution to the list
if row >= n:
solutions.append([row[:] for row in board])
return
for col in range(n):
if is_safe(board, row, col):
board[row][col] = 1 # Place the queen
solve_queens(board, row + 1, solutions)
board[row][col] = 0 # Backtrack
def print_board(board):
""" Print the board configuration """
n = len(board)
for i in range(n):
for j in range(n):
print(board[i][j], end=" ")
print()
print()
def print_all_solutions():
""" Solve the 8-Queens Problem and print all distinct solutions """
n = 8 # Size of the chessboard (8x8)
board = [[0] * n for _ in range(n)] # Initialize empty board
solutions = []
solve_queens(board, 0, solutions)
# Print all solutions found
num_solutions = len(solutions)
if num_solutions == 0:
print("No solutions found.")
else:
print(f"Total solutions found: {num_solutions}")
for idx, solution in enumerate(solutions, start=1):
print(f"Solution {idx}:")
print_board(solution)
# Call the function to print all solutions to the 8-Queens Problem
print_all_solutions()
```

### Explanation:

- The
`solve_queens`

function is modified to collect all valid board configurations (`solutions`

) when a complete arrangement of queens is found (`row >= n`

). Each solution is stored as a list of lists (`board`

configuration). - The
`print_all_solutions`

function initializes the chessboard (`board`

) and an empty list (`solutions`

) to store all found solutions. It then invokes`solve_queens`

to recursively find all valid queen placements on the chessboard. - After collecting all solutions, the function prints the total number of solutions found and iteratively prints each solution board configuration using the
`print_board`

function.

## Question 6

**TSP using heuristic approach**

**Implementation of TSP using heuristic approach**

### Python Code

```
import sys
def nearest_neighbor_tsp(distances):
num_cities = len(distances)
# Start from the first city (arbitrary choice)
tour = [0] # Store the tour as a list of city indices
visited = set([0]) # Track visited cities
current_city = 0
total_distance = 0
while len(visited) < num_cities:
nearest_city = None
min_distance = sys.maxsize
# Find the nearest unvisited city
for next_city in range(num_cities):
if next_city not in visited and distances[current_city][next_city] < min_distance:
nearest_city = next_city
min_distance = distances[current_city][next_city]
# Move to the nearest city
tour.append(nearest_city)
visited.add(nearest_city)
total_distance += min_distance
current_city = nearest_city
# Complete the tour by returning to the starting city
tour.append(0)
total_distance += distances[current_city][0]
return tour, total_distance
# Example usage:
if __name__ == "__main__":
# Example distance matrix (symmetric, square matrix)
# distances = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
distances = [[ 0, 4, 8, 9, 12], [ 4, 0, 6, 8, 9], [ 8, 6, 0, 10, 11], [ 9, 8, 10, 0, 7], [12, 9, 11, 7, 0]]
# Run nearest neighbor TSP algorithm
tour, total_distance = nearest_neighbor_tsp(distances)
# Print the tour and total distance
print("Nearest Neighbor TSP Tour:", tour)
print("Total Distance:", total_distance)
```

### Output

```
$ python 06_TSP_heuristics.py
Nearest Neighbor TSP Tour: [0, 1, 2, 3, 4, 0]
Total Distance: 39
```

## Question 6

**TSP using heuristic approach**

**Implementation of TSP using heuristic approach**

### Python Code

```
import sys
def nearest_neighbor_tsp(distances):
num_cities = len(distances)
# Start from the first city (arbitrary choice)
tour = [0] # Store the tour as a list of city indices
visited = set([0]) # Track visited cities
current_city = 0
total_distance = 0
while len(visited) < num_cities:
nearest_city = None
min_distance = sys.maxsize
# Find the nearest unvisited city
for next_city in range(num_cities):
if next_city not in visited and distances[current_city][next_city] < min_distance:
nearest_city = next_city
min_distance = distances[current_city][next_city]
# Move to the nearest city
tour.append(nearest_city)
visited.add(nearest_city)
total_distance += min_distance
current_city = nearest_city
# Complete the tour by returning to the starting city
tour.append(0)
total_distance += distances[current_city][0]
return tour, total_distance
# Example usage:
if __name__ == "__main__":
# Example distance matrix (symmetric, square matrix)
# distances = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
distances = [[ 0, 4, 8, 9, 12], [ 4, 0, 6, 8, 9], [ 8, 6, 0, 10, 11], [ 9, 8, 10, 0, 7], [12, 9, 11, 7, 0]]
# Run nearest neighbor TSP algorithm
tour, total_distance = nearest_neighbor_tsp(distances)
# Print the tour and total distance
print("Nearest Neighbor TSP Tour:", tour)
print("Total Distance:", total_distance)
```

### Explanation:

- The
`nearest_neighbor_tsp`

function implements the Nearest Neighbor heuristic for the Traveling Salesman Problem. It takes a distance matrix (`distances`

) as input, where`distances[i][j]`

represents the distance between city`i`

and city`j`

. - The algorithm starts from an arbitrary city (e.g., city 0) and iteratively selects the nearest unvisited city to extend the tour until all cities are visited.
- In each iteration, the algorithm finds the nearest unvisited city to the current city by scanning through the distances. It selects the city with the shortest distance that has not been visited yet.
- The tour is represented as a list of city indices (
`tour`

), and the total tour distance is accumulated (`total_distance`

) by summing up the distances between consecutive cities in the tour. - The tour is completed by returning to the starting city (closing the loop), and the final tour and total distance are returned as the output.

### Output

```
$ python 06_TSP_heuristics.py
Nearest Neighbor TSP Tour: [0, 1, 2, 3, 4, 0]
Total Distance: 39
```

## Question 7

**Forward Chaining and Backward** **Chaining**.

**Forward Chaining and Backward**

**Chaining**.

**Implementation of the problem solving strategies: either using Forward Chaining or Backward** **Chaining**.

To demonstrate problem-solving strategies like Forward Chaining or Backward Chaining, we can use a simple example involving logical rules and a goal to be proven or derived. These strategies are commonly used in expert systems and knowledge-based systems for reasoning and inference.

Let’s implement both Forward Chaining and Backward Chaining with a specific example to illustrate how these strategies work.

### Example Scenario:

Consider a simple knowledge base containing logical rules and facts related to animal classification. We want to use either Forward Chaining or Backward Chaining to determine whether a given animal is classified as a mammal or bird based on the provided rules.

#### Knowledge Base:

- Rule: If an animal has hair and gives birth to live young, then it is a mammal.
- Rule: If an animal has feathers and can fly, then it is a bird.
- Fact: A cat has hair.
- Fact: A cat gives birth to live young.

#### Goal:

Determine whether a cat is classified as a mammal.

### Forward Chaining:

- In Forward Chaining, we start with known facts (
`facts`

) and repeatedly apply logical rules (`rules`

) to infer new facts until we reach the desired goal (`goal`

). - The
`forward_chaining`

function iterates through the rules and checks if all conditions of a rule are satisfied based on the inferred facts (`inferred_facts`

). If so, it adds the result of the rule to the inferred facts. - The process continues until no new facts can be inferred (
`new_facts`

is`False`

) or the goal is reached (`result == goal`

).

### Backward Chaining:

- In Backward Chaining, we start with a goal (
`goal`

) and recursively verify if it can be proven true by checking facts (`facts`

) and applying rules (`rules`

) in reverse. - The
`backward_chaining`

function uses a nested`ask`

function to recursively verify if a goal can be derived by checking its conditions against known facts and recursively asking for its dependencies. - If the goal can be proven (
`ask(goal)`

returns`True`

), then the conclusion is reached; otherwise, it’s not.

### Python Code

```
def forward_chaining(rules, facts, goal):
inferred_facts = set(facts)
new_facts = True
while new_facts:
new_facts = False
for rule in rules:
condition, result = rule
if all(cond in inferred_facts for cond in condition) and result not in inferred_facts:
inferred_facts.add(result)
new_facts = True
if result == goal:
return True
return False
def backward_chaining(rules, facts, goal):
def ask(query):
if query in facts:
return True
for rule in rules:
condition, result = rule
if result == query and all(ask(cond) for cond in condition):
return True
return False
return ask(goal)
# Define the rules and facts for the animal classification problem
rules = [
(['hair', 'live young'], 'mammal'),
(['feathers', 'fly'], 'bird')
]
facts = ['hair', 'live young']
goal = 'mammal'
# Use forward chaining to determine if a cat is classified as a mammal
is_mammal = forward_chaining(rules, facts, goal)
if is_mammal:
print("The cat is classified as a mammal.")
else:
print("The cat is not classified as a mammal.")
facts = ['feathers', 'fly']
goal = 'bird'
# Use backward chaining to determine if a pigeon is classified as a bird
is_bird = backward_chaining(rules, facts, goal)
if is_bird:
print("The pigeon is classified as a bird.")
else:
print("The pigeon is not classified as a bird.")
```

### Output

```
$ python 07_Fwd_Bwd_chaining.py
Using forward chaining the cat is classified as a mammal.
Using backward chaining the pigeon is classified as a bird.
```

Both Forward Chaining and Backward Chaining are fundamental strategies in AI and expert systems for reasoning and inference, each suitable for different problem contexts and domains. Experiment with different rules, facts, and goals to explore the capabilities and limitations of these approaches in solving logical reasoning tasks.

## Question 8

**Resolution principle on First-Order Predicate Logic**

**Resolution principle on First-Order Predicate Logic**

**Implement resolution principle on FOPL related problems**

The resolution principle is a fundamental method used in automated theorem proving for first-order predicate logic (FOPL). It involves resolving two clauses to derive a new clause, aiming to prove or disprove a given statement or query. Here’s an implementation of the resolution principle in Python for resolving clauses and demonstrating its application on FOPL-related problems.

### Python Code

```
def negate_literal(literal):
""" Negate a literal by adding or removing the negation symbol '~' """
if literal.startswith('~'):
return literal[1:] # Remove negation
else:
return '~' + literal # Add negation
def resolve(clause1, clause2):
""" Resolve two clauses to derive a new clause """
new_clause = []
resolved = False
# Copy literals from both clauses
for literal in clause1:
if negate_literal(literal) in clause2:
resolved = True
else:
new_clause.append(literal)
for literal in clause2:
if negate_literal(literal) not in clause1:
new_clause.append(literal)
if resolved:
return new_clause
else:
return None # No resolution possible
def resolution(propositional_kb, query):
""" Use resolution to prove or disprove a query using propositional logic """
kb = propositional_kb[:]
kb.append(negate_literal(query)) # Add negated query to knowledge base
while True:
new_clauses = []
n = len(kb)
resolved_pairs = set() # Track resolved pairs to avoid redundant resolutions
for i in range(n):
for j in range(i + 1, n):
clause1 = kb[i]
clause2 = kb[j]
if (clause1, clause2) not in resolved_pairs:
resolved_pairs.add((clause1, clause2))
resolvent = resolve(clause1, clause2)
if resolvent is None:
continue # No resolution possible for these clauses
if len(resolvent) == 0:
return True # Empty clause (contradiction), query is proved
if resolvent not in new_clauses:
new_clauses.append(resolvent)
if all(clause in kb for clause in new_clauses):
return False # No new clauses added, query cannot be proven
kb.extend(new_clauses) # Add new clauses to the knowledge base
# Example usage:
if __name__ == "__main__":
# Example propositional knowledge base (list of clauses)
propositional_kb = [
['~P', 'Q'],
['P', '~Q', 'R'],
['~R', 'S']
]
# Example query to prove/disprove using resolution
query = 'S'
# Use resolution to prove or disprove the query
result = resolution(propositional_kb, query)
if result:
print(f"The query '{query}' is PROVED.")
else:
print(f"The query '{query}' is DISPROVED.")
```

Given the `propositional_kb`

and `query`

:

**Knowledge Base (**:`propositional_kb`

)- If
`P`

is false, then`Q`

is true (`~P`

implies`Q`

). - If
`P`

is true and`Q`

is false, then`R`

is true (`P`

and`~Q`

imply`R`

). - If
`R`

is false, then`S`

is true (`~R`

implies`S`

).

- If
**Query (**:`query`

)`'S'`

- We want to determine whether the proposition
`S`

can be proven (`True`

) or disproven (`False`

) using the knowledge base and the resolution principle.

- We want to determine whether the proposition

### Applying Resolution:

The `resolution`

function will use the `propositional_kb`

and the negated `query`

(`'~S'`

) to try to derive a contradiction or prove the query `S`

using resolution steps. It iteratively applies resolution on pairs of clauses from the knowledge base (`propositional_kb`

) to derive new clauses until no new clauses can be derived or a contradiction (empty clause) is found.

### Running the Code:

When running the provided code:

- The
`resolution`

function will attempt to prove or disprove the query`'S'`

using the propositional knowledge base (`propositional_kb`

) and the resolution principle. - If the query
`S`

can be proven (`True`

), it means that`S`

logically follows from the clauses in the knowledge base. - If the query
`S`

is disproved (`False`

), it means that`S`

cannot be logically derived from the knowledge base and its negation (`~S`

) cannot be refuted.

This example demonstrates how resolution can be used for automated theorem proving in propositional logic, providing insights into logical inference and reasoning based on given rules and facts. Adjusting the clauses and queries allows for exploring different logical scenarios and testing the effectiveness of the resolution principle in logical reasoning tasks.

### Output

```
$ python 08_fopl.py
The query 'S' is DISPROVED.
```

## Question 9

**Tic-Tac-Toe game**

**Tic-Tac-Toe game**

**Implement Tic-Tac-Toe game using Python.**

### Python Code

```
def print_board(board):
""" Print the current state of the Tic-Tac-Toe board """
for row in board:
print(" | ".join(row))
print("-" * 9)
def check_winner(board, player):
""" Check if the specified player has won the game """
for row in board:
if all(cell == player for cell in row):
return True
for col in range(3):
if all(board[row][col] == player for row in range(3)):
return True
if all(board[i][i] == player for i in range(3)):
return True
if all(board[i][2-i] == player for i in range(3)):
return True
return False
def is_full(board):
""" Check if the board is completely filled """
return all(cell != ' ' for row in board for cell in row)
def tic_tac_toe():
""" Main function to run the Tic-Tac-Toe game """
board = [[' ' for _ in range(3)] for _ in range(3)]
current_player = 'X'
while True:
print_board(board)
print(f"Player {current_player}'s turn.")
row = int(input("Enter row (1-3): "))
col = int(input("Enter column (1-3): "))
row -= 1
col -= 1
if board[row][col] == ' ':
board[row][col] = current_player
else:
print("Invalid move! Try again.")
continue
# Check if the current player has won
if check_winner(board, current_player):
print_board(board)
print(f"Player {current_player} wins!")
break
# Check if the board is full (tie game)
if is_full(board):
print_board(board)
print("It's a tie!")
break
# Switch to the other player
current_player = 'O' if current_player == 'X' else 'X'
if __name__ == "__main__":
tic_tac_toe()
```

### Output

```
$ python 09_Tic_Tac_Toe.py
| |
---------
| |
---------
| |
---------
Player X's turn.
Enter row (1-3): 2
Enter column (1-3): 2
| |
---------
| X |
---------
| |
---------
Player O's turn.
Enter row (1-3): 1
Enter column (1-3): 1
O | |
---------
| X |
---------
| |
---------
Player X's turn.
Enter row (1-3): 1
Enter column (1-3): 2
O | X |
---------
| X |
---------
| |
---------
Player O's turn.
Enter row (1-3): 3
Enter column (1-3): 2
O | X |
---------
| X |
---------
| O |
---------
Player X's turn.
Enter row (1-3): 1
Enter column (1-3): 3
O | X | X
---------
| X |
---------
| O |
---------
Player O's turn.
Enter row (1-3): 3
Enter column (1-3): 3
O | X | X
---------
| X |
---------
| O | O
---------
Player X's turn.
Enter row (1-3): 3
Enter column (1-3): 1
O | X | X
---------
| X |
---------
X | O | O
---------
Player X wins!
```

If you are also looking for other Lab Manuals, head over to my following blog :