PRACTICAL-1
Aim
Implement 8 puzzle problem using
a) Breadth first search
Problem Statement
The 8-puzzle consists of a 3×3 grid with 8 numbered tiles and one blank space. The goal is to
transform a given initial state into a desired goal state by sliding tiles into the blank space. BFS is
used to explore all possible states level by level to find the shortest solution.
Algorithm (BFS)
1. Start
2. Take the initial puzzle state as input
3. Initialize a queue and a list to store visited states
4. Add the initial state to the queue
5. Repeat until queue becomes empty:
a. Remove the first element from the queue
b. Check if it matches the goal state
c. If yes, display result and stop
d. Otherwise, generate all valid moves
e. Add only those states which are not visited
6. If queue becomes empty, no solution exists
7. Stop
Flow Diagram
Code
from collections import deque
GOAL = [1,2,3,4,5,6,7,8,0]
# display puzzle nicely
def show(state):
for i in range(0, 9, 3):
print(state[i], state[i+1], state[i+2])
print()
# find position of blank (0)
def find_zero(state):
return [Link](0)
# generate possible moves
def generate_moves(state):
zero = find_zero(state)
possible = []
# moves: up, down, left, right
shifts = [-3, 3, -1, 1]
for shift in shifts:
new_pos = zero + shift
# boundary conditions
if shift == -3 and zero < 3:
continue
if shift == 3 and zero > 5:
continue
if shift == -1 and zero % 3 == 0:
continue
if shift == 1 and zero % 3 == 2:
continue
# swap
temp = state[:]
temp[zero], temp[new_pos] = temp[new_pos], temp[zero]
[Link](temp)
return possible
def solve_bfs(start):
visited = set()
q = deque()
[Link]((start, []))
[Link](tuple(start))
while q:
current, path = [Link]()
if current == GOAL:
return path + [current]
for nxt in generate_moves(current):
if tuple(nxt) not in visited:
[Link](tuple(nxt))
[Link]((nxt, path + [current]))
return None
# -------- MAIN --------
if __name__ == "__main__":
start_state = [1,2,3,4,0,6,7,5,8]
print("Start State:\n")
show(start_state)
result = solve_bfs(start_state)
if result:
print("Solution Found!\n")
step_no = 0
for step in result:
print("Step", step_no)
show(step)
step_no += 1
else:
print("No solution found.")
OUTPUT
Result
The 8-puzzle problem was successfully solved using Breadth First Search (BFS).
The algorithm explored all possible states level by level and found the optimal (shortest) path
from the initial state to the goal state.
All intermediate steps from the start state to the goal state were generated and displayed
correctly. The use of BFS ensures that the solution obtained is the minimum number of moves
required to reach the goal configuration.
Aim
To implement the Depth First Search (DFS) algorithm to solve the 8-puzzle problem.
Problem Statement
The 8-puzzle problem consists of a 3×3 grid with one empty space. The goal is to transform the
initial arrangement into the target configuration by moving tiles into the blank space. DFS
explores possible states by going deeper into the search tree.
Algorithm (DFS)
1. Start
2. Input the initial puzzle state
3. Create a stack and a visited list
4. Push the initial state into the stack
5. Repeat until stack becomes empty:
o Pop the top element
o Check if it is the goal state
o I f yes, print result and stop
o If not visited, mark it visited
o Generate possible next states
o Push them into stack
6. If stack becomes empty, no solution found
7. Stop
Flowchart
Code
# Goal state
goal_state = [1,2,3,4,5,6,7,8,0]
# print puzzle
def print_puzzle(state):
for i in range(0, 9, 3):
print(state[i:i+3])
print()
# find blank (0)
def get_blank_index(state):
return [Link](0)
# generate neighbors
def get_neighbors(state):
neighbors = []
index = get_blank_index(state)
moves = [-3, 3, -1, 1] # up, down, left, right
for move in moves:
new_index = index + move
# boundary conditions
if move == -3 and index < 3:
continue
if move == 3 and index > 5:
continue
if move == -1 and index % 3 == 0:
continue
if move == 1 and index % 3 == 2:
continue
new_state = state[:]
new_state[index], new_state[new_index] = new_state[new_index], new_state[index]
[Link](new_state)
return neighbors
# DFS function with depth limit
def dfs(start, max_depth=20):
stack = [(start, [], 0)] # (state, path, depth)
visited = set()
while stack:
current, path, depth = [Link]()
if current == goal_state:
return path + [current]
if depth > max_depth:
continue
[Link](tuple(current))
for neighbor in get_neighbors(current):
if tuple(neighbor) not in visited:
[Link]((neighbor, path + [current], depth + 1))
return None
# -------- MAIN --------
if __name__ == "__main__":
initial_state = [1,2,3,4,5,6,0,7,8]
print("Initial State:\n")
print_puzzle(initial_state)
solution = dfs(initial_state, max_depth=20)
if solution:
print("Solution Found!\n")
step = 0
for s in solution:
print("Step", step)
print_puzzle(s)
step += 1
else:
print("No solution within depth limit")
Output
Result
The 8-puzzle problem was successfully solved using Depth First Search (DFS) with a depth limit.
The algorithm explores states deeply along each branch before backtracking and eventually
reaches the goal state within the specified depth.
All intermediate steps from the initial state to the goal state are displayed correctly. However,
unlike BFS, DFS does not guarantee the shortest path, but it is effective in exploring solutions
within a limited depth.
PRACTICAL-2
Aim
To solve the N-Queens problem using the A* search algorithm.
Problem Statement
The N-Queens problem involves placing N queens on an N×N chessboard such that no two
queens attack each other. A* algorithm is used with a heuristic function to efficiently search for
a valid arrangement.
Algorithm (A*)
1. Start
2. Define board size (N)
3. Represent state as positions of queens
4. Define heuristic = number of conflicts between queens
5. Create a list (or priority queue) to store states
6. Insert initial state
7. Repeat:
a. Select state with lowest cost
b. If no conflicts → solution found
c. Otherwise generate new states
d. Calculate cost = path + heuristic
e. Add new states to list
8. Stop
Flowchart
Code
# N-Queens using simple A* style approach
import heapq
N = 4 # you can change value
# count conflicts (heuristic)
def count_conflicts(board):
conflicts = 0
for i in range(len(board)):
for j in range(i+1, len(board)):
if board[i] == board[j] or abs(board[i] - board[j]) == abs(i - j):
conflicts += 1
return conflicts
# generate next states
def next_states(board):
states = []
for col in range(len(board)):
for row in range(N):
if board[col] != row:
new_board = board[:]
new_board[col] = row
[Link](new_board)
return states
def solve():
start = [0] * N # initial state
pq = []
[Link](pq, (count_conflicts(start), start))
visited = []
while pq:
cost, current = [Link](pq)
if current not in visited:
[Link](current)
if count_conflicts(current) == 0:
print("Solution found:")
print(current)
return
for state in next_states(current):
if state not in visited:
h = count_conflicts(state)
[Link](pq, (h, state))
print("No solution found")
solve()
Output
Result
The N-Queens problem was successfully solved using a heuristic-based search approach.
The algorithm evaluated different board configurations and selected the one with minimum
conflicts.
For N = 4, a valid solution [2, 0, 3, 1] was obtained where no two queens attack each other. The
solution correctly satisfies all constraints of the N-Queens problem.
PRACTICAL-3
Aim
Implement vertex coloring problem using constraint satisfaction problem.
Problem Statement
Given a graph, the objective is to assign colors to each vertex such that no two adjacent vertices
share the same color. This problem is solved using CSP techniques with backtracking to satisfy
constraints.
Algorithm
1. Start
2. Represent the graph using adjacency list or matrix
3. Define available colors
4. Initialize all vertices as unassigned
5. Pick a vertex that is not yet colored
6. Assign a color from the available set
7. Verify that no neighboring vertex has the same color
8. If the assignment is valid, proceed to the next vertex
9. If not valid, try another color or backtrack
10. Continue the process until all vertices are colored
11. If all vertices are successfully colored, display solution
12. Otherwise, report failure
13. Stop
Flowchart
Code
# Graph Coloring using Backtracking
def is_valid(node, graph, color_map, color):
for neighbor in graph[node]:
if neighbor in color_map and color_map[neighbor] == color:
return False
return True
def solve_coloring(graph, colors, color_map, nodes, index):
if index == len(nodes):
return True
node = nodes[index]
for color in colors:
if is_valid(node, graph, color_map, color):
color_map[node] = color
if solve_coloring(graph, colors, color_map, nodes, index + 1):
return True
# backtrack
del color_map[node]
return False
# -------- MAIN --------
if __name__ == "__main__":
graph = {
'A': ['B', 'C', 'D'],
'B': ['A', 'C'],
'C': ['A', 'B', 'D'],
'D': ['A', 'C']
}
colors = ['Red', 'Green', 'Blue']
color_map = {}
nodes = list([Link]())
if solve_coloring(graph, colors, color_map, nodes, 0):
print("Coloring Solution:\n")
for node in nodes:
print(node, "->", color_map[node])
else:
print("No solution found")
Output
Result
The Decision Tree Classification algorithm was successfully implemented using a sample
dataset.
The model was trained on a portion of the data and tested on unseen data.
The predictions were generated correctly, and the accuracy of the model was calculated. The
accuracy may vary due to random data splitting, but the model demonstrates correct
classification behavior.
PRACTICAL-4
Aim
To implement a regression model using Linear Regression and analyze prediction accuracy.
Problem Statement
Linear Regression is used to model the relationship between dependent and independent
variables. The task is to train a model on a dataset and evaluate its performance using metrics
such as MAE, MSE, RMSE, and R² score.
Algorithm
1. Start
2. Import necessary libraries
3. Load the dataset from CSV file
4. Remove unwanted columns (such as identifiers or names)
5. Convert categorical values into numerical format
6. Define input features (X) and target variable (y)
7. Divide the dataset into training and testing data
8. Initialize Linear Regression model
9. Fit the model using training data
10. Predict values using test dataset
11. Compare predicted results with actual values
12. Compute performance metrics (MAE, MSE, RMSE, R² score)
13. Display the final output
14. Stop
Flowchart
Code
import pandas as pd
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LinearRegression
from [Link] import mean_absolute_error, mean_squared_error, r2_score
data = pd.read_csv("car [Link]")
data = [Link](columns=["Car_Name"])
data = pd.get_dummies(data, drop_first=True)
features = [Link]("Selling_Price", axis=1)
target = data["Selling_Price"]
X = [Link]
y = [Link]
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=1)
lr = LinearRegression()
[Link](X_tr, y_tr)
predictions = [Link](X_te)
print("Sample Predictions:", predictions[:5])
print("Actual Values:", y_te[:5])
mae_val = mean_absolute_error(y_te, predictions)
mse_val = mean_squared_error(y_te, predictions)
rmse_val = [Link](mse_val)
r2_val = r2_score(y_te, predictions)
print("\nMAE:", mae_val)
print("MSE:", mse_val)
print("RMSE:", rmse_val)
print("R2 Score:", r2_val)
Output
Result
The Linear Regression model was successfully implemented to predict car selling prices using
the given dataset.
The data was preprocessed by removing unnecessary columns and converting categorical values
into numerical form.
The model was trained on training data and tested on unseen data. The predictions were
generated and compared with actual values. Evaluation metrics such as MAE, MSE, RMSE, and
R² score were calculated, indicating that the model performs well in predicting car prices.
PRACTICAL-5
Aim
To implement the K-Nearest Neighbor (KNN) algorithm for classification and evaluate model
performance.
Problem Statement
KNN is a supervised learning algorithm that classifies data points based on the majority class
among its nearest neighbors. The objective is to train the model on a dataset and evaluate its
accuracy and performance.
Algorithm (KNN)
1. Start
2. Import necessary libraries
3. Load the dataset from CSV file
4. Define input variables (X) and output variable (y)
5. Apply feature scaling to normalize data
6. Divide the dataset into training and testing sets
7. Select the value of K (number of nearest neighbors)
8. Initialize the KNN classifier
9. Train the model using training dataset
10. Predict the class labels for test data
11. Evaluate results by comparing predictions with actual values
12. Calculate performance measures (accuracy, confusion matrix, classification report)
13. Display the results
14. Stop
Flowchart
Code
import pandas as pd
from sklearn.model_selection import train_test_split
from [Link] import StandardScaler
from [Link] import KNeighborsClassifier
from [Link] import accuracy_score, confusion_matrix, classification_report
data = pd.read_csv("[Link]")
print("Data Preview:\n")
print([Link]())
X = [Link](columns=["Outcome"])
y = data["Outcome"]
X = [Link]
y = [Link]
sc = StandardScaler()
X = sc.fit_transform(X)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=1)
knn = KNeighborsClassifier(n_neighbors=5)
[Link](X_tr, y_tr)
pred = [Link](X_te)
print("\nPredicted:", pred[:10])
print("Actual:", y_te[:10])
accuracy = accuracy_score(y_te, pred)
matrix = confusion_matrix(y_te, pred)
report = classification_report(y_te, pred)
print("\nAccuracy:", accuracy)
print("\nConfusion Matrix:\n", matrix)
print("\nClassification Report:\n", report)
Output
Result
The K-Nearest Neighbors (KNN) classification algorithm was successfully implemented on the
diabetes dataset.
The data was preprocessed using feature scaling to improve model performance.
The model was trained and tested, and predictions were generated. The accuracy, confusion
matrix, and classification report were calculated, showing that the model performs effectively in
classifying diabetic and non-diabetic cases.
PRACTICAL – 6
Aim
To implement the Naïve Bayes algorithm for classification and evaluate model performance.
Problem Statement
Naïve Bayes is a probabilistic classifier based on Bayes’ theorem with an assumption of feature
independence. The task is to apply it on a dataset and evaluate its performance using accuracy
and other classification metrics.
Algorithm (Naïve Bayes)
1. Start
2. Import necessary libraries
3. Read the dataset from CSV file
4. Define input features (X) and output label (y)
5. Apply normalization to scale the feature values
6. Split the dataset into training and testing parts
7. Initialize the Naïve Bayes classifier
8. Train the model using training data
9. Predict class labels for testing data
10. Compare predicted results with actual values
11. Compute evaluation metrics (accuracy, confusion matrix, classification report)
12. Display the output
13. Stop
Flow Diagram
Code
import pandas as pd
from sklearn.model_selection import train_test_split
from [Link] import StandardScaler
from sklearn.naive_bayes import GaussianNB
from [Link] import accuracy_score, confusion_matrix, classification_report
data = pd.read_csv("[Link]")
print("Data Preview:\n")
print([Link]())
X = [Link](columns=["Outcome"])
y = data["Outcome"]
X = [Link]
y = [Link]
sc = StandardScaler()
X = sc.fit_transform(X)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=7)
nb = GaussianNB()
[Link](X_tr, y_tr)
pred = [Link](X_te)
print("\nPredicted:", pred[:10])
print("Actual:", y_te[:10])
accuracy = accuracy_score(y_te, pred)
matrix = confusion_matrix(y_te, pred)
report = classification_report(y_te, pred)
print("\nAccuracy:", accuracy)
print("\nConfusion Matrix:\n", matrix)
print("\nClassification Report:\n", report)
Output
Result
The Naive Bayes classification algorithm was successfully implemented on the diabetes dataset.
The data was preprocessed using feature scaling to improve model performance.
The model was trained using the Gaussian Naive Bayes classifier and tested on unseen data. The
predictions were generated and compared with actual values. Evaluation metrics such as
accuracy, confusion matrix, and classification report were calculated, showing that the model
performs effectively in classifying diabetic and non-diabetic cases.