EX NO 1A
import heapq
import copy
class PuzzleNode:
def __init__(self, state, parent=None, action=None, cost=0):
self.state = state
self.parent = parent
self.action = action
self.cost = cost
self.heuristic = self.calculate_heuristic()
def __lt__(self, other):
return (self.cost + self.heuristic) < (other.cost + other.heuristic)
def calculate_heuristic(self):
# Manhattan distance heuristic
goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
heuristic = 0
for i in range(3):
for j in range(3):
if self.state[i][j] != 0:
goal_i, goal_j = divmod(self.state[i][j] - 1, 3)
heuristic += abs(i - goal_i) + abs(j - goal_j)
return heuristic
def get_blank_position(state):
for i in range(3):
for j in range(3):
if state[i][j] == 0:
return i, j
def get_neighbors(node):
i, j = get_blank_position(node.state)
neighbors = []
moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for action in moves:
new_i, new_j = i + action[0], j + action[1]
if 0 <= new_i < 3 and 0 <= new_j < 3:
new_state = copy.deepcopy(node.state)
new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]
neighbors.append(PuzzleNode(new_state, node, action, node.cost + 1))
return neighbors
def a_star(initial_state):
start_node = PuzzleNode(initial_state)
frontier = []
heapq.heappush(frontier, start_node)
explored = set()
while frontier:
node = heapq.heappop(frontier)
if node.state == [[1, 2, 3], [4, 5, 6], [7, 8, 0]]:
return get_solution_path(node)
explored.add(tuple(map(tuple, node.state)))
for neighbor in get_neighbors(node):
neighbor_state_tuple = tuple(map(tuple, neighbor.state))
if neighbor_state_tuple not in explored:
heapq.heappush(frontier, neighbor)
return None
def get_solution_path(node):
path = []
while node.parent:
path.append((node.state, node.action))
node = node.parent
path.append((node.state, node.action)) # initial state
path.reverse()
return path
def print_solution_path(path):
for i, (state, action) in enumerate(path):
print(f"Step {i + 1}:")
print_state(state)
if action:
print(f"Action: Move blank {action_direction(action)}\n")
def action_direction(action):
if action == (0, 1):
return "right"
elif action == (0, -1):
return "left"
elif action == (1, 0):
return "down"
elif action == (-1, 0):
return "up"
def print_state(state):
for row in state:
print(row)
print()
if __name__ == "__main__":
initial_state = [[1, 2, 3], [4, 0, 5], [7, 8, 6]]
print("Initial State:")
print_state(initial_state)
solution_path = a_star(initial_state)
if solution_path:
print("Solution Path:")
print_solution_path(solution_path)
else:
print("No solution found.")
OUTPUT
Initial State:
[1, 2, 3]
[4, 0, 5]
[7, 8, 6]
Solution Path:
Step 1:
[1, 2, 3]
[4, 0, 5]
[7, 8, 6]
Step 2:
[1, 2, 3]
[4, 5, 0]
[7, 8, 6]
Action: Move blank right
Step 3:
[1, 2, 3]
[4, 5, 6]
[7, 8, 0]
Action: Move blank down
EX.NO.1B
class EightQueensProblem:
def __init__(self, size=8):
self.size = size
self.solution = [None] * size
def is_safe(self, row, col):
for prev_row in range(row):
prev_col = self.solution[prev_row]
if prev_col == col or \
prev_col - prev_row == col - row or \
prev_col + prev_row == col + row:
return False
return True
def solve_queens(self, row=0):
if row == self.size:
return True
for col in range(self.size):
if self.is_safe(row, col):
self.solution[row] = col
if self.solve_queens(row + 1):
return True
self.solution[row] = None
return False
def print_solution(self):
for row in range(self.size):
line = ""
for col in range(self.size):
if col == self.solution[row]:
line += "Q "
else:
line += ". "
print(line.strip())
if __name__ == "__main__":
queens_problem = EightQueensProblem()
if queens_problem.solve_queens():
print("Solution Found:")
queens_problem.print_solution()
else:
print("No solution exists.")
OUTPUT
EX.NO:1C
def is_valid(puzzle, mapping):
# Check if all words satisfy the cryptarithmetic sum condition:
# sum of addends equals the result
def word_value(word):
val = 0
for letter in word:
if letter not in mapping or mapping[letter] is None:
return None
val = val * 10 + mapping[letter]
return val
addends = puzzle[:-1]
result = puzzle[-1]
# No leading zero allowed
for word in puzzle:
if mapping.get(word[0], -1) == 0:
return False
add_sum = 0
for word in addends:
val = word_value(word)
if val is None:
return True # partial mapping, no contradiction yet
add_sum += val
result_val = word_value(result)
if result_val is None:
return True # partial mapping, no contradiction yet
return add_sum == result_val
def solve_cryptarithmetic(puzzle):
letters = set("".join(puzzle))
if len(letters) > 10:
print("Invalid puzzle. Too many unique letters.")
return None
letters = list(letters)
def backtrack(mapping, used_digits, index=0):
if index == len(letters):
return is_valid(puzzle, mapping)
letter = letters[index]
for digit in range(10):
if digit not in used_digits:
mapping[letter] = digit
if is_valid(puzzle, mapping):
if backtrack(mapping, used_digits | {digit}, index + 1):
return True
del mapping[letter] # backtrack
return False
mapping = {}
if backtrack(mapping, set()):
return mapping
else:
print("No solution found.")
return None
def print_solution(mapping, puzzle):
addends = puzzle[:-1]
result = puzzle[-1]
def word_value(word):
return "".join(str(mapping[letter]) for letter in word)
print(" + ".join(word_value(word) for word in addends) + " = " + word_value(result))
if __name__ == "__main__":
puzzle = ["SEND", "MORE", "MONEY"]
print("Cryptarithmetic Puzzle:")
for word in puzzle:
print(word)
solution = solve_cryptarithmetic(puzzle)
if solution:
print("\nSolution:")
print_solution(solution, puzzle)
else:
print("\nNo solution found.")
OUTPUT:
Cryptarithmetic Puzzle:
SEND
MORE
MONEY
Solution:
9567 + 1085 = 10652
EX:NO:2A
import heapq
def heuristic(node, goal):
# Euclidean distance heuristic
return ((node[0] - goal[0]) ** 2 + (node[1] - goal[1]) ** 2) ** 0.5
def astar_search(start, goal, graph):
open_set = [(0, start)]
closed_set = set()
came_from = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}
while open_set:
current_f, current = heapq.heappop(open_set)
if current == goal:
path = reconstruct_path(came_from, current)
return path
closed_set.add(current)
for neighbor in graph.get(current, []):
if neighbor in closed_set:
continue
tentative_g = g_score[current] + 1 # assuming all edges have cost=1
if neighbor not in g_score or tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
return None
def reconstruct_path(came_from, current):
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return path[::-1]
if __name__ == "__main__":
# Example usage
graph = {
(0, 0): [(1, 0), (0, 1)],
(1, 0): [(0, 0), (2, 0)],
(0, 1): [(0, 0), (1, 1), (0, 2)],
(1, 1): [(0, 1), (2, 1)],
(0, 2): [(0, 1), (1, 2)],
(2, 0): [(1, 0), (2, 1)],
(2, 1): [(1, 1), (2, 0), (2, 2)],
(1, 2): [(0, 2), (2, 2)],
(2, 2): [(1, 2), (2, 1)]
start_node = (0, 0)
goal_node = (2, 2)
result = astar_search(start_node, goal_node, graph)
if result:
print(f"Shortest Path from {start_node} to {goal_node}: {result}")
else:
print("No path found.")
OUTPUT:
Shortest Path from (0, 0) to (2, 2): [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
EX.NO:2B
import heapq
def heuristic(node, goal):
# Manhattan distance heuristic
return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
def memory_bounded_astar(start, goal, graph, memory_limit):
open_set = [(0, start)]
closed_set = set()
came_from = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}
while open_set:
current_f, current = heapq.heappop(open_set)
if current == goal:
return reconstruct_path(came_from, current)
closed_set.add(current)
for neighbor in graph.get(current, []):
if neighbor in closed_set:
continue
tentative_g = g_score[current] + 1
if neighbor not in g_score or tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
# Prune open_set if exceeding memory limit
if len(open_set) > memory_limit:
# Keep only the best 'memory_limit' nodes
open_set = heapq.nsmallest(memory_limit, open_set)
heapq.heapify(open_set)
return None
def reconstruct_path(came_from, current):
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return path[::-1]
if __name__ == "__main__":
graph = {
(0, 0): [(1, 0), (0, 1)],
(1, 0): [(0, 0), (2, 0)],
(0, 1): [(0, 0), (1, 1), (0, 2)],
(1, 1): [(0, 1), (2, 1)],
(0, 2): [(0, 1), (1, 2)],
(2, 0): [(1, 0), (2, 1)],
(2, 1): [(1, 1), (2, 0), (2, 2)],
(1, 2): [(0, 2), (2, 2)],
(2, 2): [(1, 2), (2, 1)]
start_node = (0, 0)
goal_node = (2, 2)
memory_limit = 5 # Maximum nodes in open set
result = memory_bounded_astar(start_node, goal_node, graph, memory_limit)
if result:
print(f"Shortest Path from {start_node} to {goal_node}: {result}")
else:
print("No path found.")
OUTPUT:
Shortest Path from (0, 0) to (2, 2): [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
