Name : Mitesh Rathod Enrollnment No.
: 210420107503
Subject Code : 3170716 Date : 12/10/23
Practical - 6
Aim : Write a program to Implement A* Algorithm.
Program/Solution :
#Write a program to Implement A* Algorithm.
import heapq
class Node:
def __init__(self, position, parent=None):
self.position = position
self.parent = parent
self.g = 0 # Cost from start node to current node
self.h = 0 # Heuristic (estimated cost from current node to goal)
self.f = 0 # Total cost (g + h)
def __lt__(self, other):
return self.f < other.f
def astar(grid, start, goal):
# Define possible movement directions (up, down, left, right)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# Create the start and goal nodes
start_node = Node(start)
goal_node = Node(goal)
# Create open and closed lists
open_list = []
closed_set = set()
# Add the start node to the open list
heapq.heappush(open_list, start_node)
while open_list:
# Get the node with the lowest f value
current_node = heapq.heappop(open_list)
# Mark the current node as visited
closed_set.add(current_node.position)
# If we have reached the goal, reconstruct the path
if current_node.position == goal_node.position:
path = []
while current_node:
path.append(current_node.position)
current_node = current_node.parent
return path[::-1] # Return the reversed path
for direction in directions:
x, y = direction
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 15
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 12/10/23
new_position = (current_node.position[0] + x, current_node.position[1] + y)
# Check if the new position is within the grid
if (0 <= new_position[0] < len(grid)) and (0 <= new_position[1] < len(grid[0])):
# Check if the new position is not an obstacle and has not been visited
if grid[new_position[0]][new_position[1]] == 0 and new_position not in closed_set:
new_node = Node(new_position, parent=current_node)
new_node.g = current_node.g + 1
new_node.h = abs(new_node.position[0] - goal_node.position[0]) +
abs(new_node.position[1] - goal_node.position[1])
new_node.f = new_node.g + new_node.h
# Check if the new node is already in the open list with a lower f value
for node in open_list:
if new_node.position == node.position and new_node.f >= node.f:
break
else:
heapq.heappush(open_list, new_node)
return [] # No path found
# Example usage:
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)
path = astar(grid, start, goal)
print(path)
Output :
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 16
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 12/10/23
Practical - 7
Aim : Write a program to implement mini-max algorithm for any game development.
Program/Solution :
#Write a program to implement mini-max algorithm for any game development.
import math
def minimax(board, depth, is_maximizing):
if check_winner(board, "X"):
return -1
if check_winner(board, "O"):
return 1
if is_board_full(board):
return 0
if is_maximizing:
best_score = -math.inf
for i in range(3):
for j in range(3):
if board[i][j] == "":
board[i][j] = "O"
score = minimax(board, depth + 1, False)
board[i][j] = ""
best_score = max(score, best_score)
return best_score
else:
best_score = math.inf
for i in range(3):
for j in range(3):
if board[i][j] == "":
board[i][j] = "X"
score = minimax(board, depth + 1, True)
board[i][j] = ""
best_score = min(score, best_score)
return best_score
def find_best_move(board):
best_score = -math.inf
best_move = None
for i in range(3):
for j in range(3):
if board[i][j] == "":
board[i][j] = "O"
score = minimax(board, 0, False)
board[i][j] = ""
if score > best_score:
best_score = score
best_move = (i, j)
return best_move
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 17
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 12/10/23
def check_winner(board, player):
for i in range(3):
if all(board[i][j] == player for j in range(3)):
return True
for j in range(3):
if all(board[i][j] == player for i in range(3)):
return True
if all(board[i][i] == player for i in range(3)) or all(board[i][2 - i] == player for i in range(3)):
return True
return False
def is_board_full(board):
return all(cell != "" for row in board for cell in row)
def print_board(board):
for row in board:
print(" ".join(row))
print()
def main():
board = [["" for _ in range(3)] for _ in range(3)]
while True:
print_board(board)
if is_board_full(board) or check_winner(board, "X") or check_winner(board, "O"):
break
row, col = map(int, input("Enter your move (row and column): ").split())
if board[row][col] != "":
print("Invalid move. Try again.")
continue
board[row][col] = "X"
if is_board_full(board) or check_winner(board, "X"):
break
best_move = find_best_move(board)
print("Computer's move:", best_move)
board[best_move[0]][best_move[1]] = "O"
print_board(board)
if check_winner(board, "X"):
print("You win!")
elif check_winner(board, "O"):
print("Computer wins!")
else:
print("It's a draw!")
if __name__ == "__main__":
main()
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 18
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 12/10/23
Output :
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 19
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 20/10/23
Practical - 8
Aim : Write a program to solve Tower of Hanoi problem using Prolog.
Program/Solution :
hanoi(N) :- move(N, left, right, center).
move(1, A, B, _) :-
write('Move top disk from '), write(A), write(' to '), write(B), nl.
move(N, A, B, C) :-
N1 is N - 1,
move(N1, A, C, B),
move(1, A, B, _),
move(N1, C, B, A).
Output :
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 20
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 20/10/23
Practical - 9
Aim : Write a program to solve N-Queens problem using Prolog.
Program/Solution :
:- use_module(library(clpfd)).
n_queens(N, Qs) :-
length(Qs, N),
Qs ins 1..N,
all_distinct(Qs),
safe_queens(Qs),
labeling([], Qs).
safe_queens([]).
safe_queens([Q|Qs]) :-
no_attack(Q, Qs, 1),
safe_queens(Qs).
no_attack(_, [], _).
no_attack(Q, [Q2|Qs], D) :-
Q #\= Q2,
Q #\= Q2 + D,
Q #\= Q2 - D,
D1 is D + 1,
no_attack(Q, Qs, D1).
Output :
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 21
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 20/10/23
Practical - 10
Aim : Write a program to solve 8 puzzle problem using Prolog.
Program/Solution :
% Define the predicate move, which takes a list of integers representing the current state of the
puzzle and a list of integers representing the new state of the puzzle
move([X1,0,X3,X4,X5,X6,X7,X8,X9], [0,X1,X3,X4,X5,X6,X7,X8,X9]).
move([X1,X2,X3,0,X5,X6,X7,X8,X9], [X1,X2,X3,X5,0,X6,X7,X8,X9]).
move([X1,X2,X3,X4,0,X6,X7,X8,X9], [X1,X2,X3,X4,X6,0,X7,X8,X9]).
move([X1,X2,X3,X4,X5,0,X7,X8,X9], [X1,X2,X3,X4,X5,X7,0,X8,X9]).
move([X1,X2,X3,X4,X5,X6,0,X8,X9], [X1,X2,X3,X4,X5,X6,X8,0,X9]).
move([X1,X2,X3,X4,X5,X6,X7,0,X9], [X1,X2,X3,X4,X5,X6,X7,X9,0]).
move([X1,X2,X3,X4,X5,X6,X7,X8,0], [X1,X2,X3,X4,X5,X6,X7,0,X8]).
move([X1,X2,X3,X4,X5,X6,X7,X8,X9], [X1,X2,X3,X4,X5,X6,X7,X9,X8]).
% Define the predicate solve, which takes a list of integers representing the current state of the puzzle
and a list of integers representing the goal state of the puzzle
solve(State, Goal) :-
% Define the predicate bfs, which takes a list of lists representing the frontier, a list of integers
representing the explored set, and a list of lists representing the path to the goal
bfs([[State]], [], Path),
% Reverse the path to get the correct order of moves
reverse(Path, Goal).
% Define the predicate bfs, which takes a list of lists representing the frontier, a list of integers
representing the explored set, and a list of lists representing the path to the goal
bfs([[State|Path]|_], _, [State|Path]) :-
% Check if the current state is the goal state
State = [0,1,2,3,4,5,6,7,8].
bfs([Path|Paths], Explored, Solution) :-
% Get the last state in the path
last(Path, State),
% Find all possible moves from the current state
findall([NewState, State|Path], (move(State, NewState), \+ member(NewState, Explored)),
NewPaths),
% Add the new paths to the frontier
append(Paths, NewPaths, Frontier),
% Add the current state to the explored set
append(Explored, [State], NewExplored),
% Continue the search with the new frontier and explored set
bfs(Frontier, NewExplored, Solution).
% Define the predicate find_solution, which takes a list of integers representing the current state of
the puzzle and prints the solution
find_solution(State) :-
% Define the goal state
Goal = [0,1,2,3,4,5,6,7,8],
% Solve the puzzle
solve(State, Solution),
% Print the solution
write('Solution: '), nl,
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 22
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 20/10/23
print_solution(Solution).
% Define the predicate print_solution, which takes a list of lists representing the path to the goal and
prints the solution
print_solution([]).
print_solution([State|Path]) :-
% Print the current state
print_state(State), nl,
% Print the rest of the path
print_solution(Path).
% Define the predicate print_state, which takes a list of integers representing the current state of the
puzzle and prints the state
print_state([X1,X2,X3,X4,X5,X6,X7,X8,X9]) :-
write([X1,X2,X3]), nl,
write([X4,X5,X6]), nl,
write([X7,X8,X9]), nl, nl.
Output :
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 23
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 20/10/23
Practical - 11
Aim : Write a program to solve travelling salesman problem using Prolog.
Program/Solution :
% Define the distance between cities
distance(city(a, 0, 0), city(b, 1, 1), 2).
distance(city(b, 1, 1), city(c, 2, 2), 2).
distance(city(c, 2, 2), city(d, 3, 3), 2).
distance(city(d, 3, 3), city(e, 4, 4), 2).
distance(city(e, 4, 4), city(a, 0, 0), 4).
% Define the cities
city(a, 0, 0).
city(b, 1, 1).
city(c, 2, 2).
city(d, 3, 3).
city(e, 4, 4).
% Find the shortest tour
tsp(Cities, Tour, Distance) :-
permutation(Cities, Tour),
calculate_total_distance(Tour, Distance).
calculate_total_distance([_], 0).
calculate_total_distance([City1, City2 | Rest], TotalDistance) :-
distance(City1, City2, Distance),
calculate_total_distance([City2 | Rest], RemainingDistance),
TotalDistance is Distance + RemainingDistance.
% Find the optimal tour and distance
find_optimal_tour(OptimalTour, OptimalDistance) :-
setof([Tour, Distance], tsp([city(a,0,0),city(b,1,1),city(c,2,2),city(d,3,3),city(e,4,4)], Tour, Distance),
Tours),
min_distance_tour(Tours, OptimalTour, OptimalDistance).
min_distance_tour([[Tour, Distance]], Tour, Distance).
min_distance_tour([[Tour1, Distance1], [Tour2, Distance2] | Rest], OptimalTour, OptimalDistance) :-
(Distance1 < Distance2 ->
min_distance_tour([[Tour1, Distance1] | Rest], OptimalTour, OptimalDistance);
min_distance_tour([[Tour2, Distance2] | Rest], OptimalTour, OptimalDistance)
).
% Find the optimal tour and print the result
find_and_print_optimal_tour :-
find_optimal_tour(OptimalTour, OptimalDistance),
write('Optimal Tour: '), write(OptimalTour), nl,
write('Optimal Distance: '), write(OptimalDistance), nl.
% Run the program
find_and_print_optimal_tour.
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 24
Name : Mitesh Rathod Enrollnment No. : 210420107503
Subject Code : 3170716 Date : 20/10/23
Output :
SCET/AI/2023-24/Odd/BE Div I/Sem-VII 25
